February 15, 2021

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

March 30, 2020

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

September 29, 2019

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.

November 16, 2018

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

I have

nsafes, 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.

November 12, 2018

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

Ax-Grothendieck Theorem

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.

November 5, 2018

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

October 29, 2018

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

October 22, 2018

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?

October 15, 2018

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**.

October 8, 2018

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