Some puzzle solutions are so beautiful and so vastly superior to the commonsense approach that they can seem like a miracle. The solution to the third question in our most recent Insights puzzle, for example, exhibited some of these qualities. The question — about the best way to use three balance scales, including a broken one that gives random results, to find a counterfeit coin — could be cleverly solved in four weighings, even though the problem seems at first to require at least six.
Today we present a puzzle whose best solution improves upon the more obvious solution by an astonishing 60 times or more! The famous Hungarian mathematician Paul Erdős referred to beautiful proofs as being from the Book — a divine volume where God stores the perfect proofs of all math problems. Well, if the Book contains any puzzles, this one has to be in it.
In honor of the actor and activist Nichelle Nichols, who passed away last month, our puzzle imagines a Star Trek adventure in which her character, Lieutenant Uhura, faces a life-and-death conundrum:
As the Enterprise approached a hitherto unknown planet in the Necklace Nebula system, Lieutenant Uhura was given her sixth surface mission. Her landing party of eight crew members were transported to the planet’s surface for exploration. Unfortunately, the Enterprise was drawn away to respond to a distress call, and the landing party was on its own.
Even though the crew had failed to detect any traces of intelligent life, the planet was populated by the Catenati, an advanced civilization with an advanced cloaking technology. The Catenati captured Uhura’s landing party and tried them for trespassing.
“You have a high probability of being guilty of this crime, which is punishable by death,” said the Catenati judge. “But our laws, in their wisdom, recognize that all doubt can never be eliminated, and hence all our punishments are probabilistic. You will be held in a common room, while we ready a separate roulette chamber. This chamber will have eight buttons arranged in a row, each of which will respond biometrically to one of you. However, to confuse you, each button will be randomly labeled with one of your names, so the button that has your name need not be yours. In fact, it will most likely not be yours.
“Once the chamber is ready, we will lead you there one at a time in an order of our choosing. There, each of you will get the chance to find your true button. When you press a button, a display will tell you who the button really belongs to. You can each press up to four of the buttons, in any order. Each of you must find your own button. If any one of you fails, or if anyone tries to press a fifth button, all of you will be executed. Only if all of you succeed will you be set free.
“Once a person is done with the chamber, they will be led away to their own solitary cell with no way to communicate with anyone else. You have a few hours together until the chamber is ready.” With that, the landing party was left alone.
Consternation abounded. “Well, at least we have a small chance,” said Chekov. “But much as I would like to be optimistic, things don’t look good. We each have a 1 in 2 chance of finding our button. The chance that all eight of us will do it is just 1 in 256, or about 0.4%. Nyet, nyet! This is far worse than the old Russian roulette — it is exponential astronomical roulette.”
Another crew member chimed in. “But we have to try. If we all press the buttons randomly, true, our chances of survival will be only 0.4%. But what if we come up with a strategy among ourselves to make sure all the buttons get pressed the same number of times? Won’t that improve our chances?”
Uhura considered this for a moment. “Yes, that may make some difference, but I suspect that the improvement will be small. We still may not break 1%.”
Puzzle 1
By how much can the crew’s survival probability be improved if they make sure each button is pressed equally often (instead of pressing any four buttons randomly)?
Puzzle 2
Our story continues:
Uhura frowned in concentration. Then she suddenly seemed to have an inspiration. She made a sketch that looked like a Star of David. “I remember a game we used to play as children,” she said. “I think it holds a clue.”
“Six children play this game, which develops both running and memory skills,” she said. “It’s played on a six-cornered playground whose points are labeled A to F. Each corner corresponds to the home base of one of the six players, who are labeled a to f. In other words, A is the home base of player a. To start a round, the children select a random letter from A through F. They position themselves on the corner labeled with the letter they picked. Then player a runs and tags the player whose home base she was on, displacing him. That child, in turn, runs and displaces the player whose home base he was on, and so on, until the player who was on a’s home base runs to the empty base that player a vacated, and thus completes a cycle. Play then passes clockwise to the next player who has not yet run. If a child is already on their own home base, that child doesn’t have to run. The round is completed when play has been passed to all eligible players.”
(For example, in the figure shown above, player a is initially on base C, so she runs and displaces c who was on E. Next, c runs and displaces e. Since e was on A, he goes to the empty base C where player a was, thus completing a cycle of length 3. It turns out that the other three players, b, d and f, form another cycle of length 3. This completes the round. In this case, their running paths form a six-pointed star, but lots of other patterns are possible.)
“While we often had cycles of four, five or six legs, there were plenty of rounds with no cycles of more than three legs,” Uhura recalled.
In a given round, if the children play correctly, what is the probability that there will be no cycle that’s greater than length 3?
If you get stuck, click below to reveal a hint.
Click for Hint:
Puzzle 3
Back to the story:
“Yes, that’s it!” exclaimed Uhura. “If my calculations are correct, we have a better than 35% chance of going free.”
Can you explain what strategy was suggested by the game above and how it improves the landing party’s odds of freedom from less than 1% to over 35%?
Puzzle 4
As our story continues, it turns out that one of the Catenati has taken a special dislike to the Enterprise crew and is remotely monitoring them. He suspects that they have come up with some effective strategy based on Uhura’s diagram. He is determined to foil their plan by slipping into the chamber and deliberately changing the order of the button labels before the roulette starts. Can he successfully thwart the plan? What does the landing party have to be especially careful to conceal?
Puzzle 5
What limit does the maximum percentage of success approach as the size of the landing party increases indefinitely? Can you explain why this method is so much more efficient than random button pressing?
As chronicled in the Annals of Future History, Uhura’s plan was executed, and with a little bit of good fortune (but not too much), the crew escaped and continued to explore other strange and dangerous worlds.
That’s it for our space adventure. Happy puzzling, and may your brain attain warp speed.
Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt or one of the two Quanta books, Alice and Bob Meet the Wall of Fire or The Prime Number Conspiracy (winner’s choice). And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION.” (It will not appear online, so solutions to the puzzle above should be submitted separately.)
