This puzzle comes from a video about Magic the Gathering that my brother sent me, which you can watch here.

The video is more about the specific rules of Magic, but this isn’t a Magic blog, so let’s get to the math as soon as possible.

“Prisoner puzzles” are a popular kind of mathematical puzzle, in which a large group of cooperative players (“prisoners”) play a game against an adversarial supervisor (often “the warden”), with limited communication. Some classic examples are here and here (there’s frequent overlap with “hat problems”).

Recently, I ran across a very difficult prisoner puzzle, which required an intricate solution from the prisoners to win. I’ve rephrased the problem and a few solutions below, along with an interactive demonstration of the strategies.

The inevitable has happened – all the mathematicians in the world have been gathered up and arrested for being huge nerds.

The mathematicians are housed in a custom prison, which has \(n\) identical, isolated cells, arranged in a large circle, each containing a single occupant (no empty cells). Inside each cell is a light switch and a light bulb, but the electrical wiring is unusual. If the light switch in a cell is on at noon, the bulb in the adjacent cell will briefly flash. Otherwise, and at all other times, the light bulb is off¹.

In order to prevent communication, every midnight, the warden fills the cells with knockout gas, flips all the switches to “off”, and rearranges the prisoners however he wants. (Still only one prisoner per cell though.)

One day, the warden enters your cell and issues you a challenge to win your freedom, and that of your colleagues. At any point, any one of the prisoners can announce “There are \(n\) prisoners!”. If they are correct, then everyone is free. Otherwise, everyone will be executed. He allows you to send a message to all of your colleagues, describing the game and the plan, to which they are not allowed to reply. The warden, of course, will read your message, and shuffle everyone to thwart your strategy.

What plan would you devise?

\(\newcommand{W}{\square} \newcommand{B}{\blacksquare}\)

Hat puzzles are super popular among mathematicians. Most of them have cute and clever solutions. Here’s one that, at the time of writing, is still an open problem.

Alice and Bob sit facing each other, each with an infinite tower of hats on their heads. Each hat is either black or white, with equal probability. Alice can see all of Bob’s hats, but not her own, and vice versa. On the count of three, both players must name a natural number, which is used to index into their own hat tower. If the two hats match, then the players win, otherwise they lose. (Also, they’re not allowed to talk, cough, wink, or otherwise communicate.)

As an example, say Alice’s hats are \(\W\W\B\W\W\B\cdots\) and Bob’s hats are \(\B\W\B\W\W\B\cdots\). If Alice says 3 and Bob says 1, then since Alice’s third hat and Bob’s first hat are both black, then they win. If they both say 1, their first hats do not match, so they lose.

What’s the best possible strategy, and how often does it win? No one knows! I have some conjectures here, and some (probably unoriginal) strategies that do pretty well.

Imagine you’re tasked with killing a hydra. As usual, the hydra is defeated when all of its heads are cut off, and whenever a head is cut off, the hydra grows new ones.

However, this mathematical hydra is much more frightening than a “traditional” one. It’s got a tree-like structure – heads growing out of its heads – and it can regrow entire groups of heads at once! Can you still win?

Also, this post is the first one with interactivity! Feel free to report bugs on the GitHub issues page.

Here’s a few similar puzzles with a common story:

I have n safes, each one with a unique key that opens it. Unfortunately, some prankster snuck into my office last night and stole my key ring. It seems they’ve randomly put the keys inside the safes (one key per safe), and locked them.

We’ll play around with a few different conditions and see what chances we have of getting all safes unlocked, and at what cost.

\(\DeclareMathOperator{\res}{Res}\)

This one’s another puzzle from work:

Consider a pigeon coop with \(n\) pigeonholes, arranged in a straight line. When a pigeon arrives at the coop, it will roost in a pigeonhole only if it is empty, and both neighboring pigeonholes are also empty. It selects such a pigeonhole uniformly at random, enters the pigeonhole, and does not leave. At some point, the coop will fill up, but not every pigeonhole will be occupied. What is the expected density of pigeons in the coop, as \(n\) grows large?

If you run a few simulations, you get that it’s about \(0.432332\ldots\). But this isn’t any easily recognizable number. What is it in closed form?

This one comes from a puzzle that a coworker gave me.

There’s a miracle in the Gospels in which Jesus feeds a crowd of 5000, using only a few loaves of bread and some fish. As he breaks the food apart and hands it out, it does not diminish, and eventually the entire crowd is fed.

In our puzzle, we have a prophet who is not quite so saintly. He starts with a single loaf of bread, and has to feed a crowd of \(N\) people. But he also wants to be able to feed himself. Furthermore, our guy’s got a bit of a gambling problem: at each step, he flips a fair, unbiased coin.

• If it comes up heads, he duplicates one of his loaves.
• Otherwise, he hands out a loaf of bread to someone in the crowd.

He only stops when he runs out of bread, or he creates \(N\) new loaves (at which point, the entire crowd can be fed, and he can eat the original loaf).

The question is: what is the probability that he can successfully feed everyone?