Math Mondays

A work in progress.

Posts

The Mathematical Hydra

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.

Safes and Keys

November 26, 2018

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

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.

Wedderburn's Little Theorem

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.

Sylow Theorems

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?

The Heawood Number

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?

Linearity of Expectation

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.

Expected Density of Pigeons

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?

Cauchy Residue Theorem

October 1, 2018

$ \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 going on here?

Monsky's Theorem

September 24, 2018

$ \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, his proof relies primarily on number theory and combinatorics! Despite the level of machinery involved, his proof is quite accessible, and we will describe it below.

Doubling Loaves, in Two Ways

September 17, 2018

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?

The Multiplicative Structure of $\Bbb Z / n \Bbb Z$

September 10, 2018

$ \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, giving a total of $\phi(n)$ generators. The multiplicative structure, on the other hand, is far less apparent.

Not all elements of $\ZZn{n}$ can participate in the multiplicative group, because not all of them have inverses. For example, 4 has no inverse in $\ZZn{6}$; there’s no integer $a$ such that $4a \equiv 1 \pmod 6$. Elements that do have inverses are called units, and we’ll denote the group of units in $\ZZn{n}$ as $U_n$.

Since an element $a \in \ZZn{n}$ is a unit iff $a$ and $n$ are coprime, there are $\phi(n)$ units, where $\phi$ is the totient function. But the size of the group alone doesn’t nail down the group structure.

For example:

  • $U_5 = \{ 1, 2, 3, 4 \}$:
    • generated by $2$: $2^0 = 1$, $2^1 = 2$, $2^2 = 4$, $2^3 = 8 = 3$
    • also generated by $3$: $3^0 = 1$, $3^1 = 3$, $3^2 = 4$, $3^3 = 2$
    • this group is isomorphic to $\ZZn{4}$
  • $U_8 = \{ 1, 3, 5, 7 \}$
    • every element squares to $1$
    • this group is isomorphic to $\ZZn{2} \times \ZZn{2}$

Is there a way to find the structure of $U_n$?