The prisoners dilemma

A few weeks ago Taso (new fancy homepage), Tony and I organised the Sydney Theory Day. Among the invited speakers were Peter Bro Miltersen who gave a talk on "Names in boxes". The abstract of the talk can be found here. The short version is:

"The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it"

If each prisoner examines a random set of 50 boxes, their probability of survival is close to zero. It turns out that there is a very simple schedule that gives the prisoners a 30% chance of surviving. It sounds almost impossible but there's a simple proof that anyone can understand in "7 Puzzles You Think You Must Not Have Heard Correctly" by Peter Winkler.

This semester I've been teaching computational geometry at USyd and I find it hard to get them to properly understand the beauty of expected running times. However, this year I started the lecture by discussing the "Prisoners dilemma" for 20 minutes before I talked about the expected running time of low dimensional LP. And I really believe it had a positive effect. The students seemed to appreciate the simplicity of the arguments a bit more than usual.

Now the challenge is to find a puzzle like this for each lecture. Any tips?