Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Honderd gevangenen


In Puzzels, door Ionica

Peter Winkler maakte een lijst met puzzels waarvan je denkt dat je ze niet goed gehoord hebt. Ze lijken te moeilijk of juist te makkelijk om op te lossen. Veelgehoorde reacties op deze puzzels zijn "Klopt dit wel echt?" en "Wacht, volgens mij heb ik het verkeerd verstaan". Hierbij mijn favoriete puzzel uit deze lijst, misschien volgen er later meer.

De zware jongens

In een ver land staat een gevangenis met een wiskundig onderlegde directeur. Hij biedt honderd gevangen een kans om vrij te komen. Hij zet een rij van honderd houten kistjes in een kamer. Hij stopt in elk kistje de naam van één van de gevangenen, elke naam komt precies één keer voor. De gevangenen worden één voor één naar deze kamer gebracht. Elke gevangene mag maximaal vijftig kistjes openmaken en kijken welke naam erin zit. Hij moet de kamer daarna precies zo achterlaten als hij binnenkwam en hij mag niet meer met de andere gevangenen praten.

De gevangenen mogen vooraf een strategie verzinnen en die zullen ze hard nodig hebben. Want ze worden alleen vrijgelaten als elke gevangene de kist met zijn eigen naam erin openmaakt. Als dat níet lukt, dan worden ze allemaal onthoofd. Er is een strategie, waarbij de gevangenen meer dan 30% kans hebben om vrij te komen. Wat is deze strategie?

Merk op dat als elke gevangene vijftig willekeurige dozen openmaakt, de kans dat ze vrij komen gelijk is aan (1/2)100 en dat is heel wat kleiner dan 30%.

p.s. Je hebt het echt goed gelezen: meer dan 30%!

65 reacties op “Honderd gevangenen”

  1. Vincent:

    @ronnie ja dat klinkt goed! Dankjewel! (leuk zo'n conversatie in geheimtaal...)

  2. han:

    Wat een moeilijk puzzeltje!

  3. Aitrus:

    Wanneer wordt de oplossing geplaatst? Ik ben nou wel heel nieuwsgierig geworden!

  4. Bruno van Wayenburg:

    @Aitrus: Je kunt hem vinden via de site van Peter Winkler. Maar ik heb hem nog niet gelezen, ook al weet ik dat ik er niet meer denktijd in wil steken.

  5. Ionica:

    Een andere lezer had ons gemaild met de smeekbede om de oplossing nog niet te plaatsen, omdat hij er nog langer over na wilde denken. Maar via de site van Winkler kun je zelf al het antwoord vinden. Hier staat de pdf:
    http://www.math.dartmouth.edu/~pw/solutions.pdf

  6. Bruno van Wayenburg:

    Nu wel gelezen (er moet hier nog meer gebeuren). Heel mooi.

  7. Arnout Jaspers:

    Wie de oplossing tot in detail beschreven wil zien, kan die opzoeken in het juninummer (2007) van Pythagoras. Daar heet het 'Het kluisjesprobleem'. Daar gaat het om tien kluisjes met portemonnees erin, maar de winstkans hangt nauwelijks af van het aantal, mits dit niet al te klein is.
    Het probleem is overigens - voorzover wij van Pythagoras weten - voor het eerst vorig jaar gepubliceerd in The Mathematical Intelligencer (vol.28, no 1, 2006)

  8. Bruno van Wayenburg:

    Idioot: als de eerste drie gevangenen hun naam vinden, is de kans dat de volgende 47 hun naam vinden al 97 procent.

  9. Rinse:

    Zie ook het laatste nr (sept. 2007) van de Nieuwe Wiskrant over een soortgelijk probleem.
    "Honderd gevangenen en een gloeilamp", van H. van Ditmarsch.

  10. Gerhard:

    Apropos "gevangen".
    The November 2007 issue of Pythagoras contains
    the "gevangen viervlak" puzzle of Wim Zwaan:

    http://www.pythagoras.nu/pyth/pdf/artikel_181_blz%2020-21%20gevangen%20viervlak%20november%202007.pdf

    --Gerhard

  11. Proeme:

    geweldige opgave! :)

  12. jaap:

    jullie zijn allemaal ziek in je hoofd met je rotpuzzels

  13. Wiskundemeisjes » Mr. K.J. Cath-prijs voor de wiskundemeisjes!:

    [...] de gevangenen hun onthoofding misschien kunnen vermijden: klik op een van de volgende links voor de puzzel over de gevangenen, het grapje over meisjes en wiskunde, de favoriet van Roger Penrose en Vallende Ster Galois. En [...]

  14. Anneke:

    Hoi Allemaal,

    Ik kreeg van een van mijn jongere op mijn werk het onderstaande raadsel, nadat ik een spel met ze gedaan had, waarin ze ook verschillende raadsels moesten oplossen. Ik heb aan verschillende mensen gevraagd of ze me konden helpen, en ben vervolgens op internet gaan zoeken. Toen kwam ik op deze site uit. Mogelijk dat jullie me kunnen helpen?

    In een gevangenis in de Verenigde Staten zitten 100 gevangenen die de doodstraf gekregen hebben en vandaag geexecuteerd zullen worden.
    Een nogal sadistische bewaker heeft besloten ze een kans te geven, als ze eerst een spel met hem spelen.
    Het werkt als volgt:

    Ze worden allemaal in een rij gezet, achter elkaar, zodat ze alleen de gevangenen voor zich kunnen zien.
    Ze krijgen allemaal een hoed op gezet, een rode of een zwarte.
    Deze worden willekeurig uitgedeeld, dus er zit geen patroon in de volgorde of aantallen van elke kleur De gevangenen kunnen alleen de hoeden van de gevangenen voor hun waarnemen, de kleur van hun eigen hoed en de hoeden achter zich niet.
    De bewaker zal achteraan de rij beginnen, en de betreffende gevangene om de kleur van zijn hoed vragen.
    Noemt hij de goede kleur, dan mag hij gaan, noemt hij de verkeerde, dan wordt hij geexecuteerd.
    Er is genoeg bewaking aanwezig om te zorgen dat er niet vals gespeeld kan worden.

    Dit wordt de gevangenen allemaal vantevoren uitgelegd, en ze krijgen even tijd om hun laatste gebedje te doen.
    Nu is het aan jou om een oplossing te bedenken waarbij zoveel mogelijk gevangenen mogen blijven leven.
    Je moet dus ongeacht welke hoeden aan wie uitgedeeld worden een plan bedenken dat werkt, ze laten gokken is dus zinloos.

  15. Tonnie:

    Stel de gevangenen op in een rij. Een gevangene vindt de kist met zijn naam gaat naar buiten en gaat op de plaats staan van zijn kist. Hij heeft zijn naam gevonden in kist 25 en gaat in de rij op plaats 25 staan. Zo weten de gevangenen die nog moeten kijken welke kist(en) ze niet meer hoeven te bekijken. Is dat toegestaan? En verhoogt dat de kansen?

Plaats een reactie


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