Een verzameling kabouters, laten we zeggen 40, dragen allemaal een muts:
blauw of rood. Deze kabouters zien uiteraard de kleur van hun soortgenoten,
maar ze weten zelf niet welke kleur muts ze dragen (kunnen ze niet zien).
Wat ze wel allemaal weten is dat er minimaal één kabouter met een rode
muts in hun midden moet zijn.
Alle kabouters zijn slim en denken op dezelfde wijze. Ze handelen derhalve
ook hetzelfde, maar ze kunnen niet met elkaar communiceren (doof-stom
o.i.d.).
Om erachter te komen welke kleur muts een bepaalde kabouter heeft, gaat hij
elke dag naar een bepaalde ontmoetingsplaats waar alle kabouters die niet
weten welke kleur muts ze dragen bij elkaar komen. Als een kabouter weet
welke kleur muts hij zelf draagt, is er geen noodzaak meer om naar de
verzamel-
plaats te komen, en hij zal dan ook wegblijven. Zoals gezegds communiceren
de kabouters niet met elkaar, dus ze kunnen van elkaar niet zeggen welke
kleur ze dragen.
Vraag: Hoelang moeten kabouters bij elkaar komen om te weten te komen
wat de kleur van hun eigen muts is???
N.a.v. de antwoorden zal ik een alternatief antwoord geven waarvan ik nog
niet zeker weet of het geldig is...
Groeten,
Jeroen
: Een verzameling kabouters, laten we zeggen 40, dragen allemaal een muts:
: blauw of rood. Deze kabouters zien uiteraard de kleur van hun soortgenoten,
: maar ze weten zelf niet welke kleur muts ze dragen (kunnen ze niet zien).
: Wat ze wel allemaal weten is dat er minimaal één kabouter met een rode
: muts in hun midden moet zijn.
: Alle kabouters zijn slim en denken op dezelfde wijze. Ze handelen derhalve
: ook hetzelfde, maar ze kunnen niet met elkaar communiceren (doof-stom
: o.i.d.).
: Om erachter te komen welke kleur muts een bepaalde kabouter heeft, gaat hij
: elke dag naar een bepaalde ontmoetingsplaats waar alle kabouters die niet
: weten welke kleur muts ze dragen bij elkaar komen. Als een kabouter weet
: welke kleur muts hij zelf draagt, is er geen noodzaak meer om naar de
: verzamel-
: plaats te komen, en hij zal dan ook wegblijven. Zoals gezegds communiceren
: de kabouters niet met elkaar, dus ze kunnen van elkaar niet zeggen welke
: kleur ze dragen.
: Vraag: Hoelang moeten kabouters bij elkaar komen om te weten te komen
: wat de kleur van hun eigen muts is???
Als ze ECHT slim zijn, neemt een kabouter de leiding en zet alle rode
mutsjes aan een kant, en alle blauwe aan de andere kant, daarna
gaat hij zelf ergens staan, de andere laten dan wel weten of dat goed is of
niet: Als hij b.v. in de blauwe groep gaat staan en hij heeft zelf een
rood mutsje kunnen de blauwe een stap naar achteren doen.
Als ik deze oplossing vertel vinden mensen hem vaak flauw, het is mij echter
nooit duidelijk geworden waarom, volgens mij is er niets mis mee.
Iemand?
Groeten,
Bas
n dagen, waarbij n het aantal kabouters met een rode muts is.
Proof with induction left to the reader.
++ Als ze ECHT slim zijn, neemt een kabouter de leiding en zet alle rode
++ mutsjes aan een kant, en alle blauwe aan de andere kant, daarna
++ gaat hij zelf ergens staan, de andere laten dan wel weten of dat goed is of
++ niet: Als hij b.v. in de blauwe groep gaat staan en hij heeft zelf een
++ rood mutsje kunnen de blauwe een stap naar achteren doen.
++
++ Als ik deze oplossing vertel vinden mensen hem vaak flauw, het is mij echter
++ nooit duidelijk geworden waarom, volgens mij is er niets mis mee.
Jouw oplossing voldoet niet aan de opgave.
"Alle kabouters zijn slim en denken op dezelfde wijze."
^^^^^^^^^^^^^^^^^^^^^^^^
Een kabouter die de leiding neemt kan dus niet. Dan zouden ze allemaal
de leiding willen nemen.
Abigail
On 22 Apr 1997 11:11:43 GMT, b...@biophys.LeidenUniv.nl (Bas van Dijk)
wrote:
>Als ze ECHT slim zijn, neemt een kabouter de leiding en zet alle rode
>mutsjes aan een kant, en alle blauwe aan de andere kant, daarna
>gaat hij zelf ergens staan, de andere laten dan wel weten of dat goed is of
>niet: Als hij b.v. in de blauwe groep gaat staan en hij heeft zelf een
>rood mutsje kunnen de blauwe een stap naar achteren doen.
>
>Als ik deze oplossing vertel vinden mensen hem vaak flauw, het is mij echter
>nooit duidelijk geworden waarom, volgens mij is er niets mis mee.
Je zei wel dat ze allemaal hetzelfde zullen doen, dus als er een de
leiding wil nemen willen ze allemaal tegelijkertijd de leiding nemen.
Verder was gegeven dat ze niet konden communiceren, dus dat links en
rechts wijzen mag ook niet (telt als gebarentaal).
Ik kan deze oplossing dus niet goedkeuren, bij de gegeven opgave. :-)
--
Erik Springelkamp
spri...@noord.bart.nl
http://www.noord.bart.nl/~springel/
> Een verzameling kabouters, laten we zeggen 40, dragen allemaal een muts:
> blauw of rood. Deze kabouters zien uiteraard de kleur van hun soortgenoten,
> maar ze weten zelf niet welke kleur muts ze dragen (kunnen ze niet zien).
> Wat ze wel allemaal weten is dat er minimaal één kabouter met een rode
> muts in hun midden moet zijn.
>
> Alle kabouters zijn slim en denken op dezelfde wijze. Ze handelen derhalve
> ook hetzelfde, maar ze kunnen niet met elkaar communiceren (doof-stom
> o.i.d.).
>
> Om erachter te komen welke kleur muts een bepaalde kabouter heeft, gaat hij
> elke dag naar een bepaalde ontmoetingsplaats waar alle kabouters die niet
> weten welke kleur muts ze dragen bij elkaar komen. Als een kabouter weet
> welke kleur muts hij zelf draagt, is er geen noodzaak meer om naar de
> verzamel-
> plaats te komen, en hij zal dan ook wegblijven. Zoals gezegds communiceren
> de kabouters niet met elkaar, dus ze kunnen van elkaar niet zeggen welke
> kleur ze dragen.
>
> Vraag: Hoelang moeten kabouters bij elkaar komen om te weten te komen
> wat de kleur van hun eigen muts is???
>
> N.a.v. de antwoorden zal ik een alternatief antwoord geven waarvan ik nog
> niet zeker weet of het geldig is...
Simpel...
Kabouters met rode mutsen noem ik even kortweg rode mutsen..
Stel r rode mutsen kunnen in r dagen uitvinden DAT er r rode mutsen zijn.
Induktiestap:
Als r rode mutsen in r dagen kunnen uitvinden dat er r rode mutsen zijn, dan
kunnen r+1 rode mutsen in r+1 dagen uitvinden dat er r rode mutsen zijn.
Bewijs:
Kabouter x heeft een rode muts op maar dat weet 'ie niet. Hij ziet dus r rode
mutsen. Na r+1 dagen weten die r rode mutsen nog niet dat er r+1 rode mutsen
zijn. Dus komen ze op dag r+1 terug. Als kabouter r+1 op dag r+1 dus rode mutsen
terug ziet komen moeten er dus meer dan r rode mutsen zijn. Dus heeft hij een
rode muts op. Omdat het probleem (r+1)voudig symmetrisch is, geldt dit voor
alle r+1 rode mutsen.
Bewijs voor r=1
Als r=1, dus als er precies 1 rode muts is, dan ziet deze rode muts op de vergadering
uitsluitend blauwe mutsen. Dus heeft hij een rode muts en blijft weg op dag 2.
qed.
Algorithme voor een kabouter:
Ga naar de vergadering en tel het aantal rode mutsen. Noem dit n.
Als n=0, dan heb je een rode muts.
Kom anders nog n dagen terug. Komen er op de laatste dag nog rode
mutsen, dan heb je zelf ook een rode muts. Anders heb je een blauwe.
M. vr. gr.
E.A. Nijboer.
"Jeroen E.R. Kuijlen" <jeroen....@cmg.nl> wrote:
>Vraag: Hoelang moeten kabouters bij elkaar komen om te weten te komen
>wat de kleur van hun eigen muts is???
Volgens mij net zolang als het duurt totdat ze de spiegel uitvinden.
Matthijs
Hmmmm....
Het wegblijven van de ontmoetingsplaats is een manier om te communiceren,
hiermee laat een kabouter aan de anderen weten dat hij de kleur van zijn
muts weet. Dit mag niet, dus kabouters blijven nooit weg. Tot in de eeuwig-
heid blijven de kabouters elke dag bij elkaar komen, en niemand zal ooit
de kleur van zijn muts weten.
--
>> Keep the net clean! Don't also e-mail followups posted in newsgroups! <<
___ _
Q : | #| yrozijn : \|/ http://www. : [_]_
-<_>- Yvon : | ==| @xs4all.nl : >WWW< xs4all.nl/ : === ) Amiga
/ \ Rozijn : `---' @noord.bart.nl : /|\ ~yrozijn : O 4000
Zodra ze de muts afzetten zijn ze kleurenblind.
Abigail -- Eenhoorntjes zetten hun staart ook nooit af.
>
>Abigail -- Eenhoorntjes zetten hun staart ook nooit af.
Maar ze wassen hun staart wel !
Anton
Hai,
Ik heb het hele probleem niet gelezen (kijk nu voor het eerst op deze
nieuwsgroep), maar denk dat dit het bekende smurfen/kabouters probleem
is. Als je N kabouters hebt, durrt het N perioden voordat alle kabouters
tegelijk weten wie welke kleur petje heeft.
Een probleem dat te maken heeft met zgn. 'common knowledge'. Zo zijn er
nog een paar.
Groeten,
Xander Tieman
Tie...@tinbinst.nl
: On 22 Apr 1997 11:11:43 GMT, b...@biophys.LeidenUniv.nl (Bas van Dijk)
: wrote:
: >Als ze ECHT slim zijn, neemt een kabouter de leiding en zet alle rode
: >mutsjes aan een kant, en alle blauwe aan de andere kant, daarna
: >gaat hij zelf ergens staan, de andere laten dan wel weten of dat goed is of
: >niet: Als hij b.v. in de blauwe groep gaat staan en hij heeft zelf een
: >rood mutsje kunnen de blauwe een stap naar achteren doen.
: >
: >Als ik deze oplossing vertel vinden mensen hem vaak flauw, het is mij echter
: >nooit duidelijk geworden waarom, volgens mij is er niets mis mee.
: Je zei wel dat ze allemaal hetzelfde zullen doen, dus als er een de
: leiding wil nemen willen ze allemaal tegelijkertijd de leiding nemen.
Ja, dat is waar, echter kunnen ze wel allemaal hetzelfde DENKEN
(dat was gegeven) en tot de conclusie komen dat het beter is dat 1 de
leiding op zich neemt, dat heet democratie geloof ik :-)
: Verder was gegeven dat ze niet konden communiceren, dus dat links en
: rechts wijzen mag ook niet (telt als gebarentaal).
: Ik kan deze oplossing dus niet goedkeuren, bij de gegeven opgave. :-)
MMMMmm, maar de officiele goedgekeurde oplossing gaat er van uit dat
kabouters die eenmaal weten welke kleur hoedje hij/zij op heeft niet meer
terugkomt naar de ontmoetingsplaats: Dat is dus net zozeer communicatie,
hij laat de andere weten dat hij weet welke kleur hoedje hij opheeft.
Mijn oplossing is dus net zo (on)geldig als de officiele.
Groeten,
Bas
Bas van Dijk tel:+00 31 71 527 5966
Department of Biophysics fax:+00 31 71 527 5819
Leiden University
Leiden, The Netherlands
Zeker. En nu denken ze allemaal ofwel dat zij de leiding moeten
nemen (en dus is iedereen de leider) of ze denken allemaal dat
een ander dat moet doen (en dus is niemand de leider).
++ : Verder was gegeven dat ze niet konden communiceren, dus dat links en
++ : rechts wijzen mag ook niet (telt als gebarentaal).
++
++ : Ik kan deze oplossing dus niet goedkeuren, bij de gegeven opgave. :-)
++
++ MMMMmm, maar de officiele goedgekeurde oplossing gaat er van uit dat
++ kabouters die eenmaal weten welke kleur hoedje hij/zij op heeft niet meer
++ terugkomt naar de ontmoetingsplaats: Dat is dus net zozeer communicatie,
++ hij laat de andere weten dat hij weet welke kleur hoedje hij opheeft.
++ Mijn oplossing is dus net zo (on)geldig als de officiele.
Deze vorm van communicatie is toegestaan in de probleem stelling.
Ik zie je probleem niet.
Abigail
Alle kabouters die het weten zullen tegelijk wegblijven. Als er 1 rode
muts is, ziet die kabouter alleen maar blauw om zich heen, hij weet dan
dat hij zelf de enige rode is, dus blijft na dag 1 weg (regel 1).
Stel er zijn 2 rode mutsen. Zo'n roodmuts ziet dus 1 rode muts, dus hij
verwacht dat die na 1 dag wegblijft (regel 1). Maar dat doet-ie niet!
Dus er moet nog een rode muts zijn, die hij niet ziet. Dus moet hij zelf
een roodmuts zijn (regel 2).
De andere roodmuts weet op precies dezelfde manier dat hij een roodmuts
is.
Algemeen: een kabouter die N roodmutsen ziet verwacht dat ze na N dagen
wegblijven. Gebeurt dat niet, dan is hij zelf ook een roodmuts, en
blijft dus de volgende dag weg.
Peter
Er is niet een eerste kaboutertje dat wegblijft. Alle kabouters met
rode mutsjes blijven gelijktijdig weg.
Het algoritme is simpel:
Als je n rode mutsjes ziet, dan blijf je na n + 1 dagen weg.
Ofwel je hebt een blauw mutsje, en na n dagen zie je geen rode
mutsjes. Ofwel je hebt een rood mutsje, en na n + 1 dagen
weten alle kabouters met rode mutsjes dat.
Abigail
>Een verzameling kabouters, laten we zeggen 40, dragen allemaal een muts:
>blauw of rood. Deze kabouters zien uiteraard de kleur van hun soortgenoten,
>maar ze weten zelf niet welke kleur muts ze dragen (kunnen ze niet zien).
>Wat ze wel allemaal weten is dat er minimaal één kabouter met een rode
>muts in hun midden moet zijn.
>
>Alle kabouters zijn slim en denken op dezelfde wijze. Ze handelen derhalve
>ook hetzelfde, maar ze kunnen niet met elkaar communiceren (doof-stom
>o.i.d.).
>
>Om erachter te komen welke kleur muts een bepaalde kabouter heeft, gaat hij
>elke dag naar een bepaalde ontmoetingsplaats waar alle kabouters die niet
>weten welke kleur muts ze dragen bij elkaar komen. Als een kabouter weet
>welke kleur muts hij zelf draagt, is er geen noodzaak meer om naar de
>verzamel-
>plaats te komen, en hij zal dan ook wegblijven. Zoals gezegds communiceren
>de kabouters niet met elkaar, dus ze kunnen van elkaar niet zeggen welke
>kleur ze dragen.
>
>Vraag: Hoelang moeten kabouters bij elkaar komen om te weten te komen
>wat de kleur van hun eigen muts is???
Kan iemand de oplossing nog een keer begrijpelijk geven, want die van
E.A. Nijboer snapte ik niet helemaal.
Waar ik vooral mee zit: Waneer zal de eerste kabouter wegblijven?
Matthijs