gevangenen [30+]

[wnvl]

100 gevangenen die elk een uniek nummer hebben tussen 1 en 100, zijn ter dood veroordeeld. De gevangenisdirecteur geeft hen een laatste kans. Hij heeft een kast met schuiven in zijn bureau aan de buitenkant genummerd van 1 tot 100. In elke schuif zit een munt met een nummer. Elke gevangene mag een voor een binnen komen en 50 schuiven openen en nadien moet hij ze terug sluiten. Hij kan nadien niet meer communiceren met de andere gevangenen. Elke gevangene moet proberen die schuif terug te vinden die de munt bevat met zijn nummer erop. Als alle gevangenen daarin slagen, dan worden ze gespaard. Als er ook maar een gevangene faalt, moten ze allemaal hangen.

Als de gevangenen lukraak schuiven openen, is het duidelijk dat de kans dat ze hangen 1/2^100 is. Door de juiste strategie te gebruiken kunnen ze hun kans verhogen tot meer dan 30%. Zoek zo een strategie.

Niet gemakkellijk.

[Sjoerd Job]

100 gevangenen die elk een uniek nummer hebben tussen 1 en 100, zijn ter dood veroordeeld. De gevangenisdirecteur geeft hen een laatste kans. Hij heeft een kast met schuiven in zijn bureau aan de buitenkant genummerd van 1 tot 100. In elke schuif zit een munt met een nummer. Elke gevangene mag een voor een binnen komen en 50 schuiven openen en nadien moet hij ze terug sluiten. Hij kan nadien niet meer communiceren met de andere gevangenen. Elke gevangene moet proberen die schuif terug te vinden die de munt bevat met zijn nummer erop. Als alle gevangenen daarin slagen, dan worden ze gespaard. Als er ook maar een gevangene faalt, moten ze allemaal hangen.

Als de gevangenen lukraak schuiven openen, is het duidelijk dat de kans dat ze hangen 1/2^100 is. Door de juiste strategie te gebruiken kunnen ze hun kans verhogen tot meer dan 30%. Zoek zo een strategie.

Niet gemakkellijk.

Gevangene 1 opent schuifje 1 en een hele stapel anderen. Als hij zijn munt vindt, legt hij die op plaats 1, en de rest doet hij iets slims mee (sowieso als hij een munt N ziet, en schuif N is open, dan legt hij de munt in die schuif, eventueel nog iets met een andere leuke sortering daarover heen).

Gevangene 2 hoeft alleen nog maar 50 van de 99 schuifjes open te doen (waaronder schuifje 2).
Gevangene 3 hoeft alleen nog maar 50 van de 98 schuifjes open te doen
etc

De kansberekening voor succes heb ik hiervoor niet uitgerekend, maar met gebruik van dit algorithme weten we al dat er wenst is als gevangene 50 aan de beurt is.

[wnvl]

Ik had het misschien niet expliciet gemeld, maar de munten mogen niet van schuif gewisseld worden.

[wnvl]

Hier dan de oplossing. Elke gevangene opent eerst de schuif die correspondeert met zijn nummer. Als zijn nummer zich niet op de munt in die schuif bevindt, gaat hij naar de schuif met het nummer dat zich op de munt in de eerste schuif bevindt. Dan gaat hij naar de schuif met het nummer van de munt in de tweede schuif. In de hoop in minder dan 50 pogingen terug bij de eerste schuif uit te komen, want dan heeft hij de munt met zijn nummer gevonden.

Deze strategie werkt als de permutatie gedefinieerd door de mapping van de nummers van de schuiven op de nummers van de munten in de schuiven cykels heeft van ten hoogste 50.

Wat de kans hierop is laat ik nog open als deel 2 van het raadsel.

[barto]

Toffe strategie. Op zich ook wel logisch dat het iets moest zijn met wat er in de schuif ligt omdat je anders zowiezo op 1/2^100 komt maar je moet er op komen natuurlijk...

De kans op pech is
Dus de kans op geluk is het complement ervan.

Merk op dat


en dat laatste is een Taylorreeks dus de kans zal voor naar naderen.
(Kan je ook zeggen zonder die gelijkheden maar dan met de benadering voor de harmonische som...)

En inderdaad: is net iets meer dan 30%

[wnvl]

Juist, niets aan toe te voegen buiten het feit dat het exacte antwoord 0.3118278206 is.

[Sjoerd Job]

hoe veranderd het als we wel munten van plek mogen wisselen?

[wnvl]

hoe veranderd het als we wel munten van plek mogen wisselen?

Bedoel je dat een gevangene 50 schuiven mag openen en dan alle munten kan verplaatsen binnen deze 50 schuiven met als voorwaarde dat elke schuif exact 1 munt moet bevatten. Ik vraag het maar omdat er veel interpretaties mogelijk zijn.

[Sjoerd Job]

hoe veranderd het als we wel munten van plek mogen wisselen?

Bedoel je dat een gevangene 50 schuiven mag openen en dan alle munten kan verplaatsen binnen deze 50 schuiven met als voorwaarde dat elke schuif exact 1 munt moet bevatten. Ik vraag het maar omdat er veel interpretaties mogelijk zijn.

Dat is inderdaad wat ik bedoel. (De andere interpretaties kunnen we later wel bekijken als we willen).

Wat is de kans dat de eerste persoon niet een laadje opent wat klopt? (Hier kunnen we inderdaad de cyclus volgen, we zouden ook in willekeur kunnen doen). Ik vermoed dat de kans (ongeveer) 50% is.

Het voorstel algorithme:
nummer 1 opent lade 1, en volgt de cyclus totdat hij munt 1 vindt. Hij slaagt met 50% kans. Hij legt nu al deze munten op de juiste plek. Als hij klaar is, heeft hij (waarschijnlijk) nog een aantal lades over die hij mag openen. Hij neemt nu de rol in van speler 2 (als deze lade nog niet geopend is), en volgt de cyclus zover mogelijk. Als hij deze ronde helemaal kan volgen, legt hij alle munten op de goede plek, en doet hetzelfde voor lade 3, etc). Als hij de cyclus niet helemaal heeft kunnen volgen, zorgt hij dat de laatste munt waar hij was in lade twee komt, zodat nummer 2 minder ver hoeft te zoeken, en dus een grotere slagingskans heeft).

Ik vermoed dat deze techniek een exacte slagingskans van 50% heeft, eventueel zelfs meer, zeker wanneer de spelers doorhebben dat ze nooit hoeven te kijken in lagere lades!). Exacte getallen heb ik niet, maar ik ga het zo even coden.

[wnvl]

Mijn algoritme:

De eerste persoon opent de eerste 50 schuiven en verplaatst de munten tussen de schuiven zodat ze geordend zijn.
De tweede persoon zoekt zijn nummer eerst tussen de eerste 50 munten. Hiervoor hoeft hij maar heel weinig schuiven te openen. Misschien maar 10. Met de volgende beurten kunnen dan schuiven 51 tot 90 geordend worden.
De derde persoon zoekt zijn nummer eerst tussen 1 en 50 (geordend), vervolgens tussen 51 en 90 (geordend) en tot slot ordent hij 91 tot 100.

Als persoon 1 en 2 hun nummer vinden dan moet vanaf persoon 3 iedereen zijn nummer terug kunnen vinden. De kans dat ze slagen moet tussen de 45% en 50% liggen denk ik.