by Dennis E. Shasha

Image by Matt Collins

Early in the life of the ferocious Minotaur (the fabled half man/half bull), King Minos of Crete spoke to three of his youthful prisoners who were sharing a cell just outside Daedalus's Labyrinth. "You know that you will die if you fight the Minotaur unarmed. I propose therefore a chance at reprieve. I will separate and blindfold you and place either a red or a blue crown on your head. I will choose the color in each case by flipping one of my lovely Cretan coins, which you can assume to be fair. I will then place you at three spots evenly spaced around my lovely stadium.

"You will be surrounded by a screen that will permit your fellows to see your crown and you to see theirs. The screen will prevent you from sending and receiving any signals. (A guard standing next to you will cut off your head if you try.) So you cannot communicate with one another once you are in the stadium. At that point, I will have the guards remove your blindfolds.

"Here is the proposition: each of you has 10 seconds to tell your guard either 'blue','red' or 'pass' concerning the color of the crown on your head. After 15 seconds, the guard next to someone who guessed correctly will give a thumbs-up. The guard next to someone who guessed incorrectly will present a thumbs-down. A pass, and the guard will keep his hand flat. If you all say 'pass', you all go to the Minotaur. If all who don't pass are correct, you all go free. If some of you who don't pass make a mistake, then again you all go to the Minotaur. If any of you tries to signal another, those still living go to the Minotaur."

(Warm-up: What is the probability that the prisoners will win if they all bet? Answer: Only 1 in 8, because each has a probability of 1 in 2 of being wrong each time.)

"Now," the king continued, "you may think that you have only half a chance of surviving by simply designating one prisoner as the guesser. But if you are clever, you will realize that you can design a strategy such that you have a 3-in-4 chance of winning. The strategy involves a rule that each prisoner must follow but that requires no communication among the prisoners once they are in the stadium. What is that rule?

"We can change the strategy so that each prisoner can 'bet' zero or more points about the color of the crown on his head. The prisoner team wins or loses that many points depending on whether he is right--and the prisoner team wins if it earns more points than it loses. This may improve the chance that the prisoners will win. Can you design a rule to make it so?"

Enumerative Solution

©