The fact that there are so many mathematical puzzles and games around 'prisoners' and people condemned to a bad fate, makes us (puzzle lovers) sound like sadists - however gentle and well meant we may be. The fact is, that there are certain stories which convey a concept more strongly than others. 'An individual with a certain payoff associated with his actions' certainly doesn't get the reader's attention as easily as 'A prisoner condemned to death, who can achieve freedom if he succeeds at something'.
So again, we have a round number of prisoners and a crazy warden. But trust me, this problem is more perplexing than any other prisoner problem you would have read so far.
There are 100 prisoners. Each of them wants freedom (well, obviously!). Every year, the
warden lets them play a strange game which may let them win their freedom. The game is set like this. There is a room with 100 closed boxes in it. Each box has a number. The names of all of the 100 prisoners are placed in these boxes, one name in each box. All prisoners are allowed to enter the room, one by one. The aim of each prisoner is to find the box with his own name in it. Each prisoner may open at most 50 boxes, look in them, and then close them again. He is then expected to leave the room. He cannot communicate with other prisoners after leaving the room, nor can he leave any sign in the room indicating or communicating any message to the next prisoners.
All the prisoners will be set free if every single prisoner is able to find his name in the room. Yes, the condition is that each and every prisoner should succeed. If even one of them fails, they have to wait another year for the game to be played again - with the boxes and names shuffled (an independent game).
The prisoners can communicate prior to the start of the game and devise their strategy.
Let us focus on only one game right now. What strategy can the prisoners plot so that they have the highest chance of success?
Discussion:
The chance of success for each prisoner is (1/2) if he plays randomly without any strategy. Hence the probability of success for all 100 prisoners playing randomly is (1/2)^100, which is a very small number.
There exists a strategy for which the team has a probability of success exceeding 30%.
So again, we have a round number of prisoners and a crazy warden. But trust me, this problem is more perplexing than any other prisoner problem you would have read so far.
There are 100 prisoners. Each of them wants freedom (well, obviously!). Every year, the
warden lets them play a strange game which may let them win their freedom. The game is set like this. There is a room with 100 closed boxes in it. Each box has a number. The names of all of the 100 prisoners are placed in these boxes, one name in each box. All prisoners are allowed to enter the room, one by one. The aim of each prisoner is to find the box with his own name in it. Each prisoner may open at most 50 boxes, look in them, and then close them again. He is then expected to leave the room. He cannot communicate with other prisoners after leaving the room, nor can he leave any sign in the room indicating or communicating any message to the next prisoners.
All the prisoners will be set free if every single prisoner is able to find his name in the room. Yes, the condition is that each and every prisoner should succeed. If even one of them fails, they have to wait another year for the game to be played again - with the boxes and names shuffled (an independent game).
The prisoners can communicate prior to the start of the game and devise their strategy.
Let us focus on only one game right now. What strategy can the prisoners plot so that they have the highest chance of success?
Discussion:
The chance of success for each prisoner is (1/2) if he plays randomly without any strategy. Hence the probability of success for all 100 prisoners playing randomly is (1/2)^100, which is a very small number.
There exists a strategy for which the team has a probability of success exceeding 30%.
Posts
0 comments:
Post a Comment