Working on this problem:
100 people are in a room. In the next room, there are 100 identical boxes. Each box contains one person’s name (and each person’s name is in exactly one box). One at a time, each person can go into the box room and open up to 50 boxes. Then, they must return the box room to its original state (no re-ordering boxes, no marking boxes in any way). They leave the room and don’t communicate with anyone else. Individually, each person is asked, “which box had your name.” Fabulous riches are showered down on the group if all 100 people answer correctly. Are there strategies they can use to improve the odds that they answer right?
This is a very good problem. John Allen Paulos has recently tweet a pointer to an article with clear and well written solution. Here it is:
http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf
You may want to consider another puzzle whose solution depends on developing an upfront strategy:
“N > 1 people sit in a circle clearly seeing all others. They are going to be blindfolded and, while in this state, hats are put on their heads – one per person, naturally. On each hat there is written a number from 0 to N-1. The numbers may be different or some may be equal. Nothing is known about that, except that each is picked up from the set {0, 1, 2, …, N-1}. When blindfolds are removed the numbers are in full display: everyone sees all the numbers except one’s own. Each is tasked with guessing his number. They are not allowed to communicate in anyway. Each is given a piece of paper on which to write his guess. The papers are collected and the responses are examined. The team wins if there is at least one right guess.”
See http://www.cut-the-knot.org/blue/PuzzleWithHats.shtml