Here is a great problem a friend of mine found at Math Circle Problem of the Week:
Click on the link and look up the problem from Sunday 12 January 2003.
Summary version: 100 prisoners, isolated from each other. Each day one is selected at random to enter a room with a single light bulb. They can flip the switch, leave it alone, or declare that all 100 prisoners have visited the room. A correct declaration sets all 100 prisoners free, and an incorrect declaration leads to a nastier resolution.
Assuming all 100 want to go free, what strategy can they decide on before the game starts? (They won't be isolated until the game has begun.)
Have fun!
Saturday, March 14, 2009
Math Circles
Subscribe to:
Post Comments (Atom)
Posts
2 comments:
This is easy. Each prisoner has to smuggle in a piece of chalk (as prisoners, they are well adept at the art of smuggling), flip the light on, add a notch in a dry place, and flip the light switch off so that the guards do not see the chalk marks. The 99th prisoner can leave the light on to let the 100th prisoner know that he (or she, let's not be sexist) can avoid wasting time and declare right away. If some prisoners are really thick and cannot reason well (let's say their public schools did not have any math classes) about what to do, the least they need to remember is the instructions to count up notches and to announce if their added notch makes it 100. Also, to prevent repeats, each prisoner is instructed to throw away their chalk after use (we'll tell them it's so that they can avoid getting caught).
The more interesting question is what is the probability that that the prisoners( if they follow instructions perfectly) will be released on the 100th day? It's a question of multiplying the probability from day to day of selecting a different prisoner. My immediate guess is that the probability is 100 factorial over 100 to the 100 so it would be very low. The question is, how can we work out the probability for 101 days? What about 102? Is there a change of rate (calculus stuff) for the probability? At what point does the probability equal 1? Infinity, I guess. But what about for margin of error where delta is 0.2, or 0.3? Hmmmm.....
Post a Comment