I am certainly not alone when I say that interest in mathematics was sparked by Martin Gardner’s Mathematical Games column in Scientific American. I have a strong memory of many boring physics classes in high school which I whiled away reading through the stack of Scientific Americans in the corner. Those columns led to mathematics in university (where I probably not coincidently received a “D” in physics) and onward through my interest in discrete optimization.
While Gardner has long since stopped writing the column, his influence remains strong. Every year, a group of mathemeticians, magicians, jugglers, puzzle makers and so on meet at a “Gathering for Gardner“, a get-together that looks to be a blast!
Last year, Peter Winkler, formerly of Lucent and now at Darmouth, put together a set of puzzles, cleverly and correctly entitled “7 Puzzles You Think You Must Not Have Heard Correctly”. Here is one I particularly like:
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed. Find a strategy for them which which has probability of success exceeding 30%. Comment: If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable 1/2^100 = 000000000000000000000000000008. They could do worse if they all look in the same 50 boxes, their chances drop to zero. 30% seems ridiculously out of reach but yes, you heard the problem correctly.