A Cooperative Hat Game

\(\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.

The Dehn Invariant, or, Tangrams In Space

\(\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.

Tangrams in square and cat configurations

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

The Mathematical Hydra

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.

Safes and Keys

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.

Ax-Grothendieck Theorem

\(\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: Let \(f: \CC^n \to \CC^n\) be a polynomial map; that is, each coordinate \(f_i: \CC^n \to \CC\) is a polynomial in the \(n\) input variables. Then, if \(f\) is injective, it is surjective.

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

Wedderburn's Little Theorem

\(\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.

Sylow Theorems

\(\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 Heawood Number

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?

Linearity of Expectation

To introduce this topic, let’s start with an innocuous problem:

You have \(10\) six-sided dice. If you roll all of them, what is the expected sum of the faces?

Your intuition should tell you that it’s \(35\). But what’s really going on here is an example of a slick principle called linearity of expectation.

Expected Density of Pigeons


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?

Page 1 / 2