Hi! This month, I thought I would take a brief break from writing about gauge theory to share a puzzle which I heard recently. As usual, if you have any riddles or puzzles that you think are interesting, send them to us and we’ll take a look at posting them!
You and nine other friends have been trapped by an evil hat-maker (who is a recurring character in these sorts of riddles). As part of his evil plan, the hat-maker has assigned each one of you a distinct hat color. These ten colors and their assignments are public knowledge, in the sense that they are known to both you and all of your friends. In order to test your affinity for your assigned color, the hat-maker has hidden ten hats of the prescribed colors in ten different boxes (one hat per box). The boxes are also colored with the ten different colors, but the hat contained inside a box may or may not correspond to the color of the box. Your group is now offered the chance to recover their hats, by participating in the following game.
One by one, each of you will be allowed to look inside up to five of the ten boxes. If you successfully find the box containing your hat, then the hat-maker will make a note of this and move on to the next person. (The hat itself is not yet removed from the box in this situation.) If all ten of you succeed, then (as a group) you win the game and are rewarded with the hats! However, if even one person fails to find their hat, then all of you are sentenced to bareheadedness. You are allowed to strategize with your friends before beginning the game, but no communication is allowed once the game starts. (Thus you cannot communicate what you find in your five boxes to your friends, and you can’t be sure which boxes your friends have looked inside unless you agree on this beforehand.) Note, however, that the boxes are inspected one after the other, so that an individual may decide which boxes to inspect based on the results of boxes that he or she has already inspected.
The simplest strategy is of course to simply have each member of the group inspect five random boxes. This obviously results in a $1/2^{10}$ chance of the group winning. Can you come up with a better strategy to stave off bareheadedness? What if instead of ten people (and hat colors), there are twenty people (and hat colors)? Can you come up with a strategy that gives a non-negligible chance of winning, even as the number of people grows to infinity?
This month’s puzzle was communicated by H. Dai.
Start with the box that is your color. If the hat inside is yours, great! Otherwise, move on to the box that matches the color of the hat inside the box. Continue until you find your hat. Repeat this with everyone!
I really wish I could remember the original problem where I encountered this. I think the odds of success approach 1-ln 2 as the number of hats and boxes approaches infinity, which works out to just over 30%. Can anyone point me to the original?
Cool