How Star Trek’s Lieutenant Uhura Overcame Astronomical Odds

Our puzzle task last month was to save a Star Trek surface party of eight led by the Enterprise Communications Officer Lieutenant Uhura (played by the late Nichelle Nichols). The crew is imprisoned by an alien race, the Catenati, on a planet in the Necklace Nebula. To escape, they have to maximize their probability of performing a task that at first seems to offer only a dismal probability of success.

The crew of eight is informed of the task while being temporarily held in a common room where they are free to communicate and strategize. In a few hours, they will be led, one at a time, to a room called the roulette chamber. This room has eight buttons arranged in a row, each of which is programmed to respond to a different crew member. To mislead the crew, each button is randomly mislabeled with another crew member’s name. Each crew member is allowed to press up to four of the buttons, in any order. Whenever they press a button, they will see who the button really belongs to. Within their four tries, they have to find the button assigned to them. For the crew to go free, all of them have to succeed in this task. If even one of them fails, all will be executed. After a crew member completes their attempt, they are to be isolated with no way to pass information to any of their crew mates.

The chances of success seem minuscule. If crew members choose buttons randomly, each will have a 1 in 2 chance of finding their button. The chance of all eight succeeding is just 1 in 256, or about 0.4%.

But they don’t have to press buttons randomly. One way to increase the probability of success could be to even out all the button presses in some way. This brings us to our first puzzle question.

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)?

Rob Corlett and JPayette answered this well, as they did all the other questions. As for the elusive central idea behind the puzzles in this column, Rob Corlett, JPayette and Jouni Seppänen described it beautifully, while Sacha Bugnon contributed a computer solution.

Here is Rob Corlett’s answer:

One way of ensuring that each button is pressed an equal number of times is to separate the prisoners into two equal sized groups of 4.

Each group only presses the buttons corresponding to the members of their group. Thus, if A, B, C and D are all in the same subgroup they only press the buttons for A, B, C and D.

This changes the problem into asking for the probability that every prisoner is allocated to the correct group as then they are guaranteed to press their button in four or less presses.

The number of ways of populating the first group (and therefore the second group as well) with four people is the number of ways of choosing 4 from 8 which is C(8, 4) = 70. Therefore, the total number of ways of allocating everyone into the two groups is 70.

There is only one allocation that correctly allocates each prisoner to the right group and so the probability of everyone being in the right group and all the prisoners surviving is 1/70 which is 3.66 times better than the 1/256 of the previous strategy. [But it is still very small: just a 1.4% chance.]

Puzzle 2

There is a way of improving the original dismal odds over 90-fold, to about 36.5%, which seems miraculous! This strategy involves the use of loops or chains of guesses — hence the references to the Necklace Nebula and the Catenati (catena is Latin for chain). In the basic form of the strategy, each crew member starts by pressing the button bearing their name, then goes on to the button bearing the name of the crew member the first button actually belonged to, and so on, creating a chain of names.

Let’s see how this works in practice. In the diagram, the buttons are shown with their labels in white. The blue letters below show the true owners of the buttons. When the first crew member, A, enters the roulette chamber, she presses button A first. This is C’s button, so she presses button C next, then button E and finally button F, which is in fact A’s own button, so she has successfully found it in four tries. Note that the buttons A-C-E-F form a closed loop of four buttons. When crew members C, E and F take their turns, they will also go around the same closed loop, starting from their own respective places, and also find their own buttons in four tries.

This arrangement also has two smaller loops of two buttons each: B-D and G-H. These four crew members will find their own buttons within two tries. So, with this arrangement, all the crew members will be successful, and they will have earned their freedom. It is clear that if the arrangement only contains loops of length 4 or less, all the crew members will be successful and will be freed. If, on the other hand, there is a single loop of 5 or more, then all the crew members on that loop will fail to find their button in four tries, and the crew will be executed. In order to find the probability of success, we can find the probability of having a loop of 5, 6, 7 or 8, add them up, and subtract that sum from 1. This is easier to calculate than the other way because for eight buttons, there can be only a single loop having 5, 6, 7 or 8 members.

There are 8! different ways to arrange eight buttons. But when we make loops, the same loop accounts for eight of these arrangements (ABCDEFGH forms the same loop as BCDEFGHA, which is the same as CDEFGHAB, etc.). So the probability of having a loop of size 8 is (8!/8)/8!, which is simply 1/8. Similarly, the probability of having a loop of size 7 is 1/7, of size 6 is 1/6, and of size 5 is 1/5. Therefore, the probability of success for our intrepid crew is 1 − (1/5 + 1/6 + 1/7 + 1/8), or 36.5%, as mentioned earlier.

The above strategy works for any number of prisoners, and the improvement in the odds over the random approach rapidly increases as that number increases. It is about sevenfold for four prisoners, 24-fold for six, 93-fold for eight and an astonishing (3.8 × 10²⁹)-fold for 100 prisoners. The key to understanding this enormous increase is that the method binds the success or failure of each member of the group to that of the others. To a very large extent, they all succeed or fail together. The group’s probability of success doesn’t drop too much from that of a single person, falling only from 50% for a single prisoner to 30.69% as the number of prisoners is increased without limit. On the other hand, the probability of a random approach or even an “even-button presses” approach succeeding declines rapidly to very close to zero for even a small number of prisoners.

If the logic behind this strategy still seems fuzzy, here’s an analysis of the 100-prisoner problem in this excellent video by Veritasium.

Puzzle 3

This puzzle was about Lieutenant Uhura remembering a childhood game, which was essentially the same puzzle, but for six people. As a hint, I suggested working out the problem for four people. Now that we have the formula, we can easily calculate the probabilities.

For four people, the probability that the longest loop is just 2 or 1 is: 1 − (1/3 + 1/4) or 41.7% with a sevenfold gain over random choice.

For six people, the probability that the longest loop is 3, 2 or 1 is: 1 − (1/4 + 1/5 + 1/6) or 38.3% with more than a 24-fold gain over random choice.

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?

Very early in the crew’s strategy discussion, Uhura’s eyes suddenly narrowed. She gave a signal to her crew, and she switched to speaking in Nicholese, announcing, “All further discussion in Nicholese, please.” Nicholese was a new language Uhura had invented early in her career for just this kind of situation, to circumvent the use of universal translators. “You must have noticed that suspicious Catenati,” she continued. “He could try to sabotage us, so we need to modify our plan. Here’s what we need to do … ”

Uhura outlined the new plan until she was satisfied that every member of her crew knew it perfectly well. Then she mused, with a faraway look in her eyes, “I named Nicholese after an iconic 20th-century actress. I’m glad I insisted that Starfleet make it standard on all our ships.”

She turned back to the crew. “That’s all, officers. You know what to do!”

We don’t know exactly what Uhura told her team. But JPayette and Rob Corlett had a pretty good idea. Here’s Rob Corlett again:

If the evil Catenati hears that they are employing this strategy then he can switch the names shown on the display to ensure that there is a cycle longer than 4.

To break this then the prisoners need to agree to a secret ordering which randomizes the sequence. They do this by saying something like “if you see Uhura’s name, then go to the button marked Chekov. If you see Chekov’s name displayed go to the button marked Smith, etc.”

This way, the reordering by the Catenati does not matter as it only works if you know the way in which the crew will respond to the names on the displays. They need to keep any reordering secret though, otherwise it can again be broken.

As we saw, Uhura ensured that the secret would be kept safe. Each member of the crew just needed to use the same secret ordering and ensure that the evil Catenati didn’t know what it was. In fact, the changed order by the evil Catenati actually increased the crew’s probability of succeeding!

This is what happened. Uhura was the first to be taken to the roulette chamber. She pressed three buttons. None were hers. Should she be sad or glad? She held her breath and pressed her fourth. She had found her true button!

She knew they were all going to be saved.

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?

JPayette wrote:

All the above generalizes straightforwardly to a crew of 2n members each allowed to press at most n buttons. From Puzzle 2, we deduce that their chance of success is

1 − (sum over k between n + 1 and 2n of 1/k).

The sum can be compared with the integral of 1/x over the interval [n, 2n], which allows us to prove that as n grows to infinity, the above probability decreases to converge to an astonishing 1 − ln(2) ≈ 30.6%. [Actually 30.69% to two decimal places.]

Rob Corlett added:

If you don’t know the integration, you can quickly get to an approximate answer by calculation using a spreadsheet. I got to 0.307 once n reached about 750 which is accurate to 3 decimal places.

We’ve already explained above why this method works. All loops longer than 1 are shared by multiple crew members. So their successes and failures are highly correlated. It’s an illustration of the principle “All for one, and one for all.” Straight out of the Starfleet manual!

Thank you to all our contributors. JPayette and Rob Corlett both submitted prizeworthy answers that made this solution column seem almost redundant. Alas, I must stick to our rule of picking one winner per puzzle column. The Insights prize goes to JPayette in recognition of contributions here and in the previous puzzle. Congratulations! Rob Corlett, your contributions will not be forgotten.

See you next month for new Insights!