One Hat Comes Home

The problem

There are $N$ prisoners in cells arranged in a circle, and $N$ hats, each carrying the name-tag of one prisoner. Before the game starts the prisoners may put the hats on each other’s heads in any order they like, and that is what they wear on day 1. Every night the jailer moves each hat one cell clockwise, so the hat you wear today is worn by your clockwise neighbour tomorrow. On day $N$ the jailer looks back over the record. If at least one prisoner wore his own hat on each of the days $1, 2, \ldots, N$, everyone goes free. One day with nobody correct and nobody goes free.

The prisoners make a single decision and then watch. Everything after the opening arrangement belongs to the jailer, so the question is whether some arrangement can survive all $N$ of its own rotations. Number the cells $0, 1, 2, \ldots, N-1$ clockwise, and give each prisoner and his hat the number of his cell.

Two attempts that fail

The obvious opening is to give every prisoner his own hat. Day 1 could not go better, with all $N$ prisoners correct at once. On day 2 every hat has moved one cell and every prisoner is wearing his anticlockwise neighbour’s hat, so nobody is correct and the game is over. Spending all the luck on one day is the worst thing the prisoners can do.

A scrambled opening does better. Take $N = 5$ and put the hats $2, 4, 0, 3, 1$ in cells 0 to 4.

This plan covers days 1, 3 and 4 and loses on days 2 and 5. The pattern of the failure is more informative than the failure itself. Days 3 and 4 each have two correct hats, and the two wasted hats are exactly the two missing days. Success is bunching up where it is not needed.

So the prisoners need to spread the luck out, one hat per day, for $N$ days. The next step is to find out what controls when a hat arrives.

Following one hat

A prisoner is a poor thing to follow, because the hat on his head changes every night. A hat is a better thing to follow, because it never changes owner and it moves at a steady one cell a night. So ask of each hat the only question that matters: how many nights until it reaches its owner?

Take the hat numbered 4 in the failing plan. It starts in cell 1 and has to reach cell 4, three cells clockwise, so it arrives on day 4. The hat numbered 0 starts in cell 2, with its owner behind it, so it goes the long way round through cells 3, 4, 0 and also takes three nights. Distances on a circle only mean anything modulo $N$, and everything below is written that way.

Waiting numbers

Write the plan as the list $a_0, a_1, \ldots, a_{N-1}$, where $a_k$ is the number on the hat placed in cell $k$ on day 1. The list is a rearrangement of $0, 1, \ldots, N-1$, since every hat is used exactly once.

The hat in cell $k$ is in cell $k + w$ after $w$ nights, so it is on its owner’s head when $k + w \equiv a_k \pmod N$. Exactly one value of $w$ between 0 and $N-1$ satisfies this, and it is the hat’s waiting number:

$w_k \equiv a_k - k \pmod N, \qquad 0 \le w_k \le N-1.$

The failing plan $2, 4, 0, 3, 1$ has waiting numbers $2, 3, 3, 0, 2$. Two observations turn those five numbers into the whole story.

The first is that every waiting number drops by one modulo $N$ overnight, since every hat ends the night one cell closer to its owner, and the hat that was home has just been taken off and must travel the whole circle again. The collection of waiting numbers is therefore the same collection every day, shunted along by one.

The second observation is that on day $d$ every hat has moved $d-1$ cells, so the hat that started in cell $k$ is home on day $d$ exactly when $w_k = d - 1$. Day 1 is covered by the hats with waiting number 0, day 2 by those with waiting number 1, and so on.

Now the earlier table explains itself. The waiting numbers $2, 3, 3, 0, 2$ contain no 1 and no 4, which is why days 2 and 5 went bare, and they contain 2 and 3 twice each, which is why days 3 and 4 had two correct hats. The repeats and the gaps are the same defect counted twice.

Proposition. A plan frees the prisoners exactly when its $N$ waiting numbers are all different, that is, when $w_0, w_1, \ldots, w_{N-1}$ are $0, 1, \ldots, N-1$ in some order.

There are $N$ days to cover and $N$ hats to cover them with. Day $d$ needs a hat with waiting number $d-1$, so the days 1 to $N$ between them need every value from 0 to $N-1$. That is $N$ different values wanted from $N$ hats, leaving no room for a repeat: two hats sharing a waiting number means some value is missing, and the day that value would have covered passes with nobody correct.

Building a plan

The proposition is worth more than a test, because it says what to design. A plan and its list of waiting numbers determine each other:

$w_k \equiv a_k - k, \qquad\text{equivalently}\qquad a_k \equiv k + w_k \pmod N.$

So the prisoners may choose the waiting numbers first, all $N$ of them different, and read the hats off afterwards. The only thing to check is that the hats so obtained are $N$ different hats.

The simplest list of $N$ different waiting numbers is $w_k = k$: the hat in cell 0 is already home, the hat in cell 1 waits one night, the hat in cell 2 waits two, and so on round the circle. Reading off the hats gives

$a_k \equiv k + w_k = k + k = 2k \pmod N.$

The doubling plan is what that choice becomes. It was not guessed: the proposition asked for $N$ different waiting numbers, and the hats followed from the simplest such list.

Whether the plan is legal is now the only question, and it is exactly here that the parity of $N$ enters. If cells $j$ and $k$ received the same hat then $2j \equiv 2k \pmod N$, and an odd $N$ shares no factor with 2, so $j \equiv k$ and the cells are the same. No two cells collide, every hat is used once, and the plan frees the prisoners.

When $N$ is even the cancellation is not available, and the plan collapses in the obvious way: cells 0 and $\tfrac12 N$ both ask for hat 0, since $2 \times \tfrac12 N = N \equiv 0$. The simplest choice of waiting numbers is unusable on an even circle.

For $N = 5$ the plan reads $0, 2, 4, 1, 3$, the last two having come back round the circle.

Handing the hats out needs no arithmetic at all. Walk clockwise from cell 0 and give out the hats $0, 2, 4, \ldots$ in that order, starting again at the beginning of the list when you run off the end. Because $N$ is odd, the second lap picks up exactly the names the first lap skipped. The hat in cell $k$ comes home on day $k+1$ and lands on the prisoner numbered $2k$, so the correct prisoner on day $d$ is the one numbered $2(d-1)$ modulo $N$. The luck advances two cells every morning and goes twice round the circle over the $N$ days.

Other choices of waiting numbers work as well. Taking $w_k \equiv (t-1)k$ gives the plan $a_k \equiv tk$, which is legal when $t$ shares no factor with $N$ and has all its waiting numbers different when $t-1$ shares no factor with $N$. Tripling therefore works whenever $N$ is odd and not a multiple of 3. Shifting a winning plan round the circle also wins, since replacing $a_k$ by $a_k + c$ adds $c$ to every waiting number and leaves them all different.

Why an even N is hopeless

Doubling failed on an even circle. That leaves the harder question of whether some cleverer list of waiting numbers might survive, and the answer is that none can, for a reason that has nothing to do with which list is tried.

Add up all $N$ waiting numbers. Since $w_k \equiv a_k - k \pmod N$,

$\sum_{k=0}^{N-1} w_k \equiv \sum_{k=0}^{N-1} a_k - \sum_{k=0}^{N-1} k \equiv 0 \pmod N,$

because $a_0, a_1, \ldots, a_{N-1}$ are the numbers 0 to $N-1$ in some order and so have the same sum as the cell numbers. Whatever the prisoners choose, the total waiting is a multiple of $N$. Read physically, the hats between them travel a whole number of laps.

A winning plan, by the proposition, has waiting numbers $0, 1, \ldots, N-1$, which add up to $\tfrac12 N(N-1)$. So a winning plan needs $\tfrac12 N(N-1) \equiv 0 \pmod N$. For odd $N$ this holds, since $\tfrac12 (N-1)$ is then a whole number and the total is $N$ times it. For even $N$ write $N = 2h$, and then

$\tfrac12 N(N-1) = h(2h-1) = 2h^2 - h \equiv -h \pmod{2h},$

which is not 0, since $h$ is not a multiple of $2h$. An even circle asks the hats to travel half a lap more than a whole number of laps, and no arrangement of hats can supply it.

The failed cancellation and the missing half lap are the same obstruction seen twice. An odd circle lets a 2 be divided out, which is what makes the simplest list of waiting numbers legal; an even circle refuses, and the half lap is what the refusal leaves behind.

The best an even group can do

Four prisoners can still cover three of their four days.

Which value gets repeated is forced. To cover days 1 to $N-1$ the waiting numbers must include each of $0, 1, \ldots, N-2$, with one value $r$ repeated to make up the count of $N$ hats, and the total must still be a multiple of $N$:

$\tfrac12 (N-1)(N-2) + r \equiv 0 \pmod N.$

Writing $N = 2h$ again, the first term is $(2h-1)(h-1) = 2h^2 - 3h + 1 \equiv 1 - 3h \equiv 1 - h \pmod{2h}$, so $r \equiv h - 1$, and since $r$ lies between 0 and $N-2$ this pins it to $r = \tfrac12 N - 1$. Four prisoners must repeat 1, six must repeat 2, eight must repeat 3.

A plan that achieves it is easy to write down. Give the first half of the circle, cells 0 to $\tfrac12 N - 1$, the hats $0, 2, 4, \ldots, N-2$, and give the second half the remaining hats in the order $N-1, 1, 3, \ldots, N-3$. For eight prisoners that reads $0, 2, 4, 6, 7, 1, 3, 5$, whose waiting numbers are $0, 1, 2, 3, 3, 4, 5, 6$: every day but the last is covered.

How many plans work

The number of arrangements that free the prisoners, counted over all $N!$ openings, runs

$N$	1	2	3	4	5	6	7	8	9
winning plans	1	0	3	0	15	0	133	0	2025

Every count is divisible by $N$, as it has to be, since shifting a winning plan round the circle gives another winning plan. The values for odd $N$ are known: they are sequence A006717 in the OEIS, where they count what algebra calls the complete mappings, or equivalently the orthomorphisms, of a cyclic group of odd order, and equally the ways of placing $N$ non-attacking semi-queens on an $N \times N$ board wrapped into a torus. In that language a winning plan is a rearrangement $a_0, a_1, \ldots, a_{N-1}$ of the residues modulo $N$ for which the differences $a_k - k$ are again all the residues modulo $N$, which is the proposition written in one line.

The puzzle also circulates as the name tag problem, where guests seated round a table keep passing name tags to their neighbour. It has been written up in that form, with the same split by parity and the same multiplication plans, in Christian Carley’s undergraduate thesis at Boise State, Spring 2019. Both sources retrieved 19 September 2026.

A last thought

The puzzle looks as though it should reward cleverness about information, and it rewards none, because the prisoners never learn anything and never act again after the first morning. What they are choosing is a list of $N$ waiting times, and the jailer’s rotation only reads that list out one entry at a time.

The notation shows how little the rotation itself matters. Suppose the jailer moved the hats $s$ cells a night rather than one. On day $d$ every hat would have moved $(d-1)s$ cells, so that day would need a hat with $w \equiv (d-1)s \pmod N$, and as $d$ runs from 1 to $N$ those targets run through every residue exactly when $s$ and $N$ share no factor. When they do share a factor, only some residues are ever asked for, fewer days need covering and an even circle stops being hopeless. Four prisoners facing a two-cell rotation go free with the arrangement $0, 2, 3, 1$, the very arrangement that fails them on the fourth day when the jailer moves one cell at a time.