Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



  • Laatste Reacties

Categorieën

Archief

Gevangenen en hoeden


In Puzzels, door Ionica

Over iets meer dan een maand mag ik mijn proefschrift verdedigen, waarover later meer. Lezers die snakken naar meer inhoudelijke stukken, kunnen straks hun hart ophalen met dat prachtige boekje en de delen die ik hier zal plaatsen!

Vandaag alvast één van mijn stellingen. Ik vond dat een proefschrift niet compleet was zonder een stelling over gevangenen met hoeden.


rode hoed

Drie gevangenen krijgen een kans om vrij te komen. Ze worden geblinddoekt naar een kamer gebracht waar ze elk een rode, blauwe of groene hoed op hun hoofd krijgen. De kleur van de hoeden wordt willekeurig gekozen: voor elk van de gevangenen is de kans op een rode hoed 1/3 (en idem voor een blauwe en groene hoed). De blinddoeken worden afgedaan en iedere gevangene ziet de kleuren van de hoeden van de twee anderen, maar niet die van zichzelf. Elk van hen moet op een vel papier schrijven welke kleur zijn eigen hoed heeft. De gevangenen mogen niet met elkaar communiceren en kunnen ook niet van tevoren een strategie afspreken. Als ze alledrie de juiste kleur opschrijven, dan komen ze vrij. Als minstens één van hen het fout heeft, dan worden ze alledrie geëxecuteerd.

Er is een strategie waarbij de gevangen een kans van 1 op 3 hebben om vrij te komen.

De vraag is natuurlijk wat die strategie is!

13 reacties op “Gevangenen en hoeden”

  1. Peter:


    Er zijn 27 mogelijke combinaties (permutaties?) van hoedenkleuren. Bij drie daarvan zijn alle hoeden dezelfde kleur, bij zes ervan zijn ze allemaal verschillend. De overige 18 hebben twee hoeden van dezelfde kleur en één afwijkende. Het lijkt voor de hand te focussen op de laatste mogelijkheid die in eerste aanzet 67% kans biedt. Als iedere gevangene aanneemt dat er twee gelijk zijn, moet hij echter nog steeds gokken: ziet hij twee dezelfde, dan moet hij aannemen dat hij één van de andere kleuren heeft. Ziet hij twee verschillende dan moet hij aannemen dat hij één van die twee heeft. Maar in beide gevallen weet hij niet genoeg. Dus de kans wordt dan (1/2)^3*(2/3)=1/12.
    Daarom kan beter iedere gevangene aannemen dat dit geval zich niet voordoet, m.a.w. dat ofwel alle drie gelijk, ofwel alle drie verschillend zijn. Dus: ziet hij twee dezelfde hoeden, dan vult hij die kleur in, ziet hij twee verschillende, dan vult hij de ontbrekende kleur in.
    En dan maar hopen dat z'n collega's net zo slim zijn!

  2. Sjoerd Visscher:

    Kunnen ze het beter doen als ze wel van tevoren een strategie mogen afspreken?

  3. Miguel:

    Dit doet me denken aan de russische tsaar die honderd hoedjes verdeelt onder honderd ministers die in een lange rij staan, met elk hoedje willekeurig wit of zwart gekleurd.

    Dan moet de laatste persoon (die dus alle hoedjes behalve het zijne kan zien) beginnen met het raden naar zijn kleur vervolgens de voorlaatste (die alle hoedjes behalve het zijne en dat van de laatste kan zien), etc...
    Ze mogen vooraf een strategie afspreken, en iedereen die fout raadt wordt neergeschoten :-)
    Er bestaat een strategie zodat minstens 99 van de ministers overleven.

  4. HJ:

    Mevrouw de kandidaat, gefeliciteerd met uw fraaie proefschrift. Ik zou graag met u van gedachten wisselen over één van de bijgevoegde stellingen, die met de drie gevangenen met hoedjes. Kan één van uw paranimfen de stelling voorlezen?
    [..]
    Laten we het probleem uit uw blog veralgemeniseren. Een willekeurig aantal gevangenen met n kleuren hoedjes, uitgedrukt als getallen 0,1,..,n-1. In zekere zin bestaat de oplossing eruit om de som van de kleur van alle hoedjes modulo n te weten te komen: elke gevangene kan uit die som en de kleuren van de overige hoedjes zijn eigen kleur bepalen. Die som kan met kans 1/n goed gegokt worden, onafhankelijk van het aantal gevangenen. In de oplossing uit de blog raadt elke gevangene dat de som nul is en bepaalt op die manier zijn eigen kleur. Mijn vraag aan u is nu: hoe weten de gevangenen (zonder overleg) dat zij elk de som nul moeten aannemen? Is niet elke som even waarschijnlijk en gokt iedereen maar wat?

  5. Jan Paul:

    Ik vind het wel een zware straf hoor, geëxecuteerd worden wegens het niet zo sterk zijn in statistiek. Maar ja, ze zeggen altijd dat je in het land zelf geweest moet zijn om er over te kunnen oordelen. Dus misschien is het toch terecht.

  6. Gerhard:

    @Peter.
    Here is a simpler way of formulating the same idea: In 9 of the 27 possible situations, all three colors are identical or are all pairwise different. The prisoners hope for these 9 cases, and behave accordingly.

  7. Sponzen Ridder:

    Het mysterie wordt ook vergroot door het gegeven dat ze geblinddoekt de kamer worden binnen gebracht en dan pas een hoed op krijgen!

    Mooi raadsel. De eerste kiest voor zichzelf inderdaad de ontbrekende kleur als de andere twee verschillende hoeden hebben, zo kunnen die hun eigen kleur juist opschrijven. Als de andere twee gelijke kleur hebben, dan kiest de eerste die kleur. De anderen merken dat dat logischerwijze onmogelijk de 'ontbrekende' kan zijn, dat ze dus dezelfde kleur op hebben en schrijven hun kleur juist op. De 1/3 onzekerheid zit dus bij gevangene één.

    Maar dat bewijst nog niet dat de kans werkelijk 1/3 is. Want als er *twee* strategieën zouden bestaan, dan moet je nog rekening houden met de kans dat alle drie de gevangenen dezelfde strategie hanteren (ongeveer 1/4) :-)

    Dus eigenlijk moet je extra bewijzen dat er geen tweede strategie kan bestaan. Dat is gelukkig niet veel werk.De enige informatie die gevangene 1 kent is: de hoeden die ik zie zijn gelijk/verschillend. De enige communicatie mogelijkheid aan gevangene 2 is: ik schrijf de juiste kleur op van die hoed 3 of niet. Er zijn dus maar twee mogelijkheden waarvan er slechts ééntje werkt.

  8. Koen:

    @Sjoerd Visscher
    Ze kunnen het niet beter doen als ze van tevoren een strategie mogen afspreken, want dat zou in het bijzonder betekenen dat de eerste gevangene vaker dan 1 van de 3 keer de kleur van zijn hoed goed heeft. Dit kan niet, want de kleur van de andere twee hoeden geeft geen informatie over de eigen hoed. (Als we aannemen dat de kleuren van de hoeden onafhenkelijk van elkaar zijn.) (De hierboven beschreven strategie zorgt er alleen maar voor dat als een gevangene goed 'gokt' dat dan de andere 2 ook goed 'gokken' gokken.)

  9. Sjoerd Visscher:

    @Koen Goed punt!

    @HJ Bij de som 0 is de strategie onafhankelijk van welk nummer je aan welke kleur toekent, anders niet.

  10. Sjoerd Visscher:

    Met 4 gevangenen en 4 kleuren is de kans ook 1/4e!

  11. Peter B:

    Hier is een andere versie van het probleem die de laatste tijd de ronde doet. Deze versie heeft wel het nadeel dat hij op nog minder punten geloofwaardig is dan de meeste versies, en dat je meer verzamelingenleer nodig hebt dan de vraagstelling misschien suggereert...

    Er zijn oneindig veel gevangenen. Ze weten dat het "proces" als volgt zal verlopen. Alle gevangenen krijgen een rode of een witte hoed op. Ze zien welke kleur hoed elke andere gevangene heeft, maar natuurlijk niet welke kleur hun eigen hoed heeft. Op een gegeven moment wordt er een signaal gegeven. Op dat moment moet iedereen tegelijk een kleur noemen. Degenen die hun eigen kleur noemen, worden vrijgelaten; degenen die het fout hebben, worden terechtgesteld.

    De gevangenen mogen van tevoren overleggen over een strategie. Gelukkig zijn de gevangenen enorm goede wiskundigen en kunnen ze onbeperkt efficiënt communiceren. De vraag is nu: kunnen ze een strategie bedenken waarbij altijd alle gevangenen op eindig veel na worden vrijgelaten?

  12. Michelle R:

    De beste strategie is natuurlijk om te weigeren om dit spel te spelen. Vrijkomen met een kans van maximaal 1/3 weegt niet op tegen ge-executeerd worden met een kans van minstens 2/3.
    Stel je voor dat je medegevangenen geen wiskundemeisjes zijn, dan ben je helemaal kansloos.

  13. Groenger:

    De strategie is heel eenvoudig.
    In totaal zijn er 2 tot de macht 3 = 27 mogelijkheden.

    De strategienis:
    Als de gevangene twee verschillende kleuren ziet, kiest hij de derde ontbrekende kleur, als hij twee dezelfde kleuren ziet, kiest hij de kleur die hij ziet.

    Uitleg:
    1) stel er zijn drie verschillende kleuren, de kans hierop is 6/27. Elke gevangene ziet twee kleurenen kiest de derde kleur. De gevangenen worden vrijgelaten.
    2) stel er zijn drie dezelfde kleuren, de kans hierop is 3/27. Elke gevangene kiest nu die kleur. De gevangenen worden vrijgelaten.
    3) in alle andere gevallen (21 van de 27) zijn er twee dezelfde en een afwijkende kleur. In deze gevallen leidt de strategie tot een verkeerd resultaat. De gevangenen worden nu geëxecuteerd.

    Totaal aantal successen is dus 6/27 + 3/27 = 9/27 = 1/3

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.