In 2003, Danish computer scientist Peter Bro Miltersen discussed a surprisingly effective technique by which a player might guess the colors of slips of paper hidden in boxes (PDF). As this circulated in the mathematical community it evolved into a puzzle in which a group of 100 prisoners must find their own names on slips of paper. I wrote about it in 2011.
When Eugene Curtin and Max Warshauer wrote about the prisoner puzzle in The Mathematical Intelligencer in December 2006, reader A.S. Landsberg offered a variant called “The Return of Monty Hall.” On a new game show for couples, there are three curtains, which hide a key, a car, and a goat. One member of the couple is the “car-master” — she must find the car. The other is the “key-master” — he must find the key. If both succeed in their tasks, they win the new car. If either fails, they win the goat.
The key-master is led out of the room, where he can’t observe the proceedings, and then the car-master has two tries to find the car (open one curtain, and if the car isn’t there, open another curtain). If she finds the car, then all the curtains are closed again and the key-master is brought on to find the key. No communication at all is permitted between the two at this point. As before, the key-master has two tries to find the key by opening curtains.
If the couple play optimally, their odds of winning the car are a surprising 2/3. They do this using Miltersen’s technique. The car-master is Player #1, the key-master is Player #2, the car is Prize #1, the key is Prize #2, and the goat is Prize #3. The strategy is simply for each player to start by opening the curtain corresponding to his or her own player number, and if unsuccessful to open the curtain number corresponding to the prize number that the first curtain reveals. So, for example, the car-master, who is Player #1, begins by opening Curtain #1. If she finds the car then she’s done; if she finds the key (Prize #2) then she opens Curtain #2, and if she finds the goat (Prize #3) then she opens Curtain #3. When the curtains are reclosed, the key-master begins his turn by opening Curtain #2 (since he’s Player #2) and following the same plan.
That’s it. It’s not guaranteed to work, but it’s a simple strategy that requires minimal preparation and no communication at all once the game has begun. The universe of possibilities is so small that we can simply count them — here are the various arrangements of prizes and the resulting outcomes:
Landsberg’s letter brought a comment by reader Eric Grunwald, who pointed out that a third person can be introduced to the Monty Hall game without reducing the overall chance of success. Replace the goat with a GPS system and add a third contestant, the “GPS-master.” Following the same rules, and again forbidding any communication among the contestants, Miltersen’s strategy ensures a 2/3 probability that all three players find their prizes.