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.

\(\newcommand{\ZZ}{\Bbb Z} \newcommand{\QQ}{\Bbb Q} \newcommand{\RR}{\Bbb R}\)

Fans of wooden children’s toys may remember tangrams, a puzzle composed of 7 flat pieces that can be rearranged into numerous different configurations.

As mathematicians, we’re interested in shapes that are slightly simpler than cats or houses.

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.

\(\newcommand{\CC}{\Bbb C} \newcommand{\FF}{\Bbb F} \newcommand{\QQ}{\Bbb Q} \newcommand{\FFx}[1]{\overline{\FF_{#1}}} \newcommand{\ACF}{\mathbf{ACF}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cT}{\mathcal{T}}\)

The Ax-Grothendieck theorem is the statement:

This… doesn’t seem like a particularly exciting theorem. But it has a really exciting proof.

\(\newcommand{\ZZ}{\Bbb Z} \newcommand{\QQ}{\Bbb Q}\)

Some rings are closer to being fields than others. A domain is a ring where we can do cancellation: if \(ab = ac\) and \(a \ne 0\), then \(b = c\). Even closer is a division ring, a ring in which every non-zero element has a multiplicative inverse. The only distinction between fields and division rings is that the latter may be non-commutative. For this reason, division rings are also called skew-fields.

These form a chain of containments, each of which is strict: fields \(\subset\) division rings \(\subset\) domains \(\subset\) rings

Some examples:

• \(\ZZ\) is a domain
• \(\ZZ/6\ZZ\) is not a domain
• the set of \(n \times n\) matrices is not a domain; two non-zero matrices can multiply to zero
• \(\QQ\) is a field (duh)
• the quaternions are a division ring

Wedderburn’s theorem states that this hierarchy collapses for finite rings: every finite domain is a field.

\(\newcommand{\ZZ}{\Bbb Z} \DeclareMathOperator{\Stab}{Stab} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\sgn}{sgn}\)

In group theory, the Sylow theorems are a triplet of theorems that pin down a suprising amount of information about certain subgroups.

Lagrange’s theorem tells us that if \(H\) is a subgroup of \(G\), then the size of \(H\) divides the size of \(G\). The Sylow theorems give us some answers to the converse question: for what divisors of \(|G|\) can we find a subgroup of that size?

The four-color theorem tells us that we can color any map using only four colors, such that no adjacent regions have the same color.

This is true for any map of the world, whether it’s on a globe or laid out flat. But what about maps on other surfaces?