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

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

But what is a residue? What are the \(a_k\)? What’s really going on here?

\(\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! There is a small amount of algebraic machinery involved, but his proof is quite accessible, and we will describe it below.

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?

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