SimReal: Mathematics - Game - Prison UiA Logo


[SimReal] [Library]
The director of a prison offers n prisoners on death row, which are numbered from 1 to n, a last chance.
In a room there is a cupboard with n drawers (boxes or doors).
The director puts in each drawer the number of exactly one prisoner in random order and closes the drawers afterwards.
The prisoners enter the room one after another.
Each prisoner may open and look into n/2 drawers in any order and the drawers are closed again afterwards.
If during this search each prisoner finds his number in one of the drawers, all prisoners are pardoned.
If just one prisoner does not find his number, all prisoners have to die.
Before the first prisoner enters the room, the prisoners may discuss their strategy, afterwards no communication of any means is possible.
What is the best strategy for the prisoners?

If there are n = 100 prisoners and every prisoner selects n/2 = 50 drawers at random the probability that a single prisoner finds his number is 50%. Therefore, the probability that all prisoners find their numbers is the product of the single probabilities which is 0.5100 = 0.0000000000000000000000000000008, a vanishingly small number.
In the simulation application there are 8 prisoners, but also now it's a very small number:
0.58 = 0.0390625.
The situation appears hopeless for the prisoners.

Surprisingly, there is a strategy which gives the prisoners a survival probability of more than 30%.


MatRIC Logo