The Hat-Parity Puzzle, math that surprises you lesson

A hundred people stand in a line, each wearing a red or a blue hat. Everyone sees the hats in front of them but not their own, and they answer one at a time from the back, each allowed to say only one color. Can a plan agreed in advance make sure that nearly everyone names their own hat correctly, whatever the hats are? This page gives a plan that is always right for at least 99 people, built on one odd or even fact, and shows why no plan can promise all 100.

Key terms

Prisoners and hats puzzle

Definition The prisoners and hats puzzle, in the version on this page, has the following rules. Before any hats appear, the 100 people agree on a plan. Then each person gets a red or a blue hat. The hats may be arranged in any way at all, even by someone who knows the plan, but they do not change once the answers begin. The people stand in a line facing the front, and each person sees every hat in front of them and no other hat, so not their own and none behind them. Starting at the back and moving forward one place at a time, each person says exactly one word, “red” or “blue”, and everyone hears every answer correctly. Nothing else passes between them, so tone of voice, pauses and gestures carry no information. A person is correct when the color they say is the color of their own hat. The puzzle asks how many correct answers a plan can guarantee for every arrangement of hats, and the answer is 99. In the parity plan, the person at the back says “red” if the number of red hats they see is odd and “blue” if it is even. Every later person works out their own color from that first answer, the answers given after it and the hats they see, and is always right. The person at the back is right exactly when their own hat has the color they announced, so the plan gives 99 or 100 correct answers and never fewer than 99. No plan can guarantee all 100, because the person at the back has heard nothing and sees the same 99 hats whichever color their own hat is. Their answer is therefore the same in both cases, and in one of the two cases it is wrong.

In plain words The person at the back cannot know their own hat, so they spend their one word on a message about the hats ahead. Each later person knows every one of those 99 hats except their own, some from what they see and the rest from the answers behind them, so one fact about the count, odd or even, settles their own hat.

Example Take four people, called A, B, C and D from back to front, where B wears red, C blue and D red, and A’s hat may be either color. Speaker A sees two red hats, an even number, and says “blue”. From then on the three hats of B, C and D are known to hold an even number of reds, so each later speaker counts the red hats among those three that they know about. An odd count means their own hat must be red, and an even count means it is blue.

Speaker	Known from earlier answers	Seen ahead	Red hats counted	Answer
A	nothing	red, blue, red	2, even	blue
B	nothing	blue, red	1, odd	red
C	B red	red	2, even	blue
D	B red, C blue	nothing	1, odd	red

Speakers B, C and D are all right. Speaker A is right only if A’s own hat is blue. If the hats were given out by independent fair coin tosses, the person at the back would be right with probability $1/2$ , but the guarantee for the other three needs no randomness at all.

Parity

Definition The parity of an integer, a whole number such as $7$ , $0$ or $-3$ , says whether it is even or odd. An integer is even when it is 2 times an integer and odd when it is 1 more than an even integer, so its parity can be recorded as one digit, 0 for even and 1 for odd. For an integer that is 0 or more, this digit is its remainder after division by 2. Parity follows simple rules under addition and subtraction. Even plus even and odd plus odd are even, while even plus odd is odd, and subtraction follows the same rules. So adding or subtracting 1 always switches the parity, and adding or subtracting an even number never changes it. Two integers $a$ and $b$ have the same parity exactly when $a - b$ is even, and this is written $a \equiv b \pmod 2$ , read ” $a$ is congruent to $b$ modulo 2”. Every $\equiv$ on this page means congruence modulo 2.

In plain words Parity keeps only one fact about a count, odd or even. If you know the parity of a total and the exact values of all its parts but one, the parity of the last part is forced. When that part can only be 0 or 1, as one hat’s red count can, the part itself is forced.

Example In the full line of 100, suppose 47 of the 99 hats in front of the back person are red. That count is odd, so the back person says “red”. The second person sees 98 hats. If 46 of them are red, the count they see is even while the full count is odd, so their own hat must be the extra red, because $46 + 1$ is odd and $46 + 0$ is even. If instead 47 of the 98 are red, the parity already matches and their own hat is blue.

Parity bit

Definition A parity bit is one extra binary digit attached to a list of binary digits $x_1, x_2, \ldots, x_m$ , each 0 or 1, that records the parity of the number of 1s in the list. With the even parity convention it is the digit $p$ , 0 or 1, with

p \equiv x_1 + x_2 + \cdots + x_m,

so that the list together with $p$ always holds an even number of 1s. Suppose exactly one digit $x_j$ of the list is unknown, its position $j$ is known, and $s$ is the sum of the other digits. Then the parity bit recovers the unknown digit, because $x_j$ is the one digit, 0 or 1, with

x_j \equiv p - s.

If some digits of the list are changed while the parity bit is kept, the parity no longer matches exactly when an odd number of digits changed. So a parity bit detects one changed digit, misses any even number of changes and never shows where a change happened.

In plain words A parity bit cannot point to a wrong digit. But when you already know which digit is missing, it tells you that digit’s value. In the line of hats, every person knows that the missing digit is their own hat.

Example Write 1 for a red hat and 0 for a blue one, and number the people from 1 at the back to 100 at the front, with $h_k$ the digit of person $k$ ‘s hat. The first answer is the parity bit $p$ of the 99 digits $h_2, \ldots, h_{100}$ , with “red” meaning 1 and “blue” meaning 0. For each $k$ from 2 to 100, let $b_k$ be the number of red hats among persons 2 to $k - 1$ , known from their answers, and $f_k$ the number of red hats person $k$ sees ahead. Both are 0 when there is nobody to count. The 99 hats split into those of persons 2 to $k - 1$ , person $k$ ‘s own and those ahead, so $p \equiv b_k + h_k + f_k$ and

h_k \equiv p - b_k - f_k .

Since $h_k$ is 0 or 1, this fixes it. Person 2 stands right in front of the back person, so $b_2 = 0$ and their answer is right. Then person 3 knows person 2’s hat, so $b_3$ is right and so is person 3’s answer, and so on to the front, each correct answer making the next count correct. In the four-person line above, speaker C is person 3, with $p = 0$ , $b_3 = 1$ for B’s red hat and $f_3 = 1$ for D’s. So C’s digit has the parity of $0 - 1 - 1 = -2$ , which is even, and C’s hat is blue.

Check yourself

Five people stand in a line, called A, B, C, D and E from back to front. Speaker B wears red, C red, D blue and E red. What does each person say under the parity plan, and who is sure to be right?

Show the answer

Speaker A sees three red hats, an odd number, and says “red”. The four hats of B, C, D and E therefore hold an odd number of reds, so a later speaker whose own count of known red hats among those four is even must wear red, and one whose count is odd must wear blue.

Speaker B sees C, D and E, with two reds, so B says “red”. Speaker C knows B is red and sees D blue and E red, again two reds, so C says “red”. Speaker D knows B and C are red and sees E red, three reds, so D says “blue”. Speaker E knows B and C are red and D blue, two reds, so E says “red”.

Speakers B, C, D and E are all right. Speaker A is right exactly when A’s own hat is red.

In the same five-person line, B gives the wrong color by mistake, and everyone else follows the plan and treats each answer they hear as true. Who else ends up wrong?

Show the answer

Speaker A still says “red”, announcing an odd count, and B says “blue” although B wears red.

Speaker C now counts B as blue, sees D blue and E red, and finds one red, an odd number, so C says “blue”. That is wrong, because C wears red. Speaker D counts B and C as blue, sees E red, finds one red and says “blue”, which is right. Speaker E counts B, C and D as blue, finds no red, an even number, and says “red”, which is right.

Only C is dragged into error. Speaker C’s count is off by B’s hat, which switches C’s conclusion. Speaker D’s count is off by two hats, B’s and C’s, and two errors of one hat each leave the parity unchanged. The same happens in any line. One mistaken answer by a speaker other than the first makes the next speaker wrong as well, if there is a next speaker, and everyone after that is right again.

Extend the puzzle to three colors. Each hat is red, blue or green, and each person may say any one of the three colors. Find a plan that guarantees every person except the one at the back, and test it on four people A, B, C and D from back to front, where B wears green, C blue and D green.

Show the answer

Give the colors the codes red 0, blue 1 and green 2, and replace parity by the remainder after division by 3. The person at the back adds the codes of the hats they see and says the color whose code is the remainder of that sum. Each later person adds the codes they know, from the answers behind them after the first and from the hats they see ahead, and names the code that brings the total to the announced remainder. Exactly one of 0, 1 and 2 does this, so each later person is right, and as before each correct answer makes the next person’s sum correct.

In the test, A sees codes $2 + 1 + 2 = 5$ , which leaves remainder 2, so A says “green”. Speaker B sees $1 + 2 = 3$ , remainder 0, and needs 2 more, so B says “green”. Speaker C knows B’s 2 and sees D’s 2, a total of 4 with remainder 1, and needs 1 more to reach remainder 2, so C says “blue”. Speaker D knows $2 + 1 = 3$ , remainder 0, and needs 2, so D says “green”. All three later answers are right. The same plan works for any number of colors, with remainders after division by that number, provided each person may say any of the colors.