Articles tagged with puzzles

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

Expected Density of Pigeons

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

Doubling Loaves, in Two Ways

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?