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…
\(\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…
\(\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…
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…
\(\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…
\(\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…
\(\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…
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?
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 .
\(\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…
\(\DeclareMathOperator{\res}{Res}\) The Cauchy Residue Theorem is a remarkable tool for evaluating contour integrals. Essentially, it says that, instead of computing an integral along a curve \(\gamma\) , you can replace it with a sum of “residues” at some special points \(a_k\) : $$ \oint_\gamma f(z)~dz = 2 \pi i \sum_k \res(f, a_k) $$ But what is a residue? What are the \(a_k\) ? What’s really…
\(\newcommand{\RR}{\Bbb R} \newcommand{\QQ}{\Bbb Q} \newcommand{\ZZ}{\Bbb Z}\) For which \(n\) can you cut a square into \(n\) triangles of equal area? This question appears quite simple; it could have been posed to the Ancient Greeks. But like many good puzzles, it is a remarkably stubborn one. It was first solved in 1970, by Paul Monsky. Despite the completely geometric nature of the question,…
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…
\(\newcommand{\ZZ}{\Bbb Z} \newcommand{\ZZn}[1]{\ZZ / {#1} \ZZ}\) One of the most familiar rings is the ring of integers modulo \(n\) , often denoted \(\ZZn{n}\) . Like all rings, it has an additive structure and a multiplicative one. The additive structure is straightforward: \(\ZZn{n}\) is cyclic, generated by \(1\) . In fact, every integer \(a\) coprime to \(n\) is a generator for this group,…