The 100 Prisoners Problem and a New Card Game

Today's math lesson is about probability, one of my favorite topics. The problem we are looking at is couched in terms of executing prisoners, so we are going to look at it from a less violent point of view. I should point out that this (roughly 10 year old problem) is not an easy problem to solve and I am not giving it to you to see how good at math you are. I thought the solution was very interesting and was reminded of it when I was killing time playing solitaire the other day. So you are going to see some interesting math and learn a new card game in the process. 

Suppose 100 people have been selected at random, lined up, and given a number based on their spot in line. First person in line is number 1, second is number 2 and so on until the last person is given number 100. The first person is sent into a room which has 100 boxes in a row, each containing a dollar bill numbered from 1 to 100 also. The person's job is to find the box with the dollar bill that matches their number. So person number 1 will keep opening boxes until they find the dollar bill that has the number 1 on it. Here's the catch. The person is only allowed to open 50 boxes. If, after 50 boxes they have not found their dollar bill, the game is over and everybody is sent away. If they find their dollar bill, they leave it in the box, exit the room out a back door, and person 2 is allowed into the room. Person 2 is now charged with opening up to 50 boxes until they find the dollar bill labeled number 2. And so on. If at any time a person fails to find their dollar bill, the game is over and everybody goes home. If everybody finds their dollar bill, then everybody gets a prize of $1000. So, everybody wins or nobody wins. A significant part of the rules is that although people can speak to each other before they enter the room, there is no communication of any kind between people who have been in the room and those still waiting. That includes doing any writing on the boxes, rearranging the boxes in any way, leaving messages on the wall, etc. Every person entering a room must have the same information about the room that everyone else had, namely that there are 100 boxes with numbered dollar bills.  (Remember each person who finds their dollar bill leaves it in the box looking just as it did before.)  

Now if person 1 enters the room and starts picking boxes at random, there is a 50% probability that they will find their dollar bill. Person 2 also has a 50% probability of finding their dollar bill. The probability of the first two people then finding their dollar bills is 25% - .5 times .5 is .25. For three people, it is (.5) to the third power. And the probability of everyone being successful and therefore everyone winning the prize is (.5)¹⁰⁰ ≈ 0.0000000000000000000000000000008 which is pretty small. In fact there is a clever non-random way to choose the boxes that raises that probability of winning the prize to about 31%. So I will give you some time to think about it (and time for me to write up the math) and come back tomorrow and post the solution here. If you would like a hint and, more importantly, a time-wasting card game to play when you are bored, look at the directions for "clock solitaire" listed here. This version isn't set up the way we played it as kids, but it is the same game. Play a few rounds and see if it leads you to a strategy for the 100 boxes game.