Puzzles/Logic puzzles/10 Hats/Solution

Puzzles | Logic puzzles | 10 Hats | Solution

---

Solution 1

The 10th student says white if she sees an even number of white hats and red if she sees an odd number of white hats (she will be the only one that could make a mistake). The 9th student now sees 8 hats in front of her. Say X of them are white. Now there are four possibilities:

• 10th student said white and X is even: She wears a red hat
• 10th student said white and X is odd: She wears a white hat
• 10th student said red and X is even: She wears a white hat
• 10th student said red and X is odd: She wears a red hat

The 9th student can figure out which case occurs and tell her correct hat color. From then on the students have to subtract the correctly guessed hats from the total and apply the even/odd reasoning again (using what the 10th student has said and counting the number of white hats in front of them).

Solution 2

There is a slight variation on this solution by transformation: instead of wearing red and white hats, the students wear hats labeled 0 or 1. Let x1,...,x10 be the numbers on the students' hats. Let a1,...,a10 be the students' answers. The students answer in decreasing order as in the first solution. The answers are defined recursively as

• a10 = (x1+...+x9) mod 2
• a9 = (x1+...+x8+a10) mod 2
• a8 = (x1+...+x7+a9+a10) mod 2
• ...

These equations can be succinctly described as follows: each student sums up the numbers they see and the numbers they've heard. The student says one if the grand total is odd and zero otherwise. To prove that ai === xi mod 2, let si = x1+...+xi and use induction.

Base case: a9 === x9 mod 2

Proof:

• s8 + x9 === a10 mod 2
• x9 === a10 + s8 mod 2
• x9 === a9 mod 2

Inductive step: Assume ai === xi mod 2 for i = n+1,..., 9 Then

• an === s(n-1) + a(n+1) +... + a10 mod 2 (by definition)
• an === s(n-1) + (s9 - sn) + a10 mod 2 (by inductive assumption)
• an === xn + s9 + a10 mod 2
• an === xn mod 2 (since s9 + a10 is even)

Thus ai === xi mod 2 for i = n, n+1,..., 9

Therefore ai === xi mod 2 for i = 1,...,9 and at most one answer (a10) is incorrect.

Solution 3

The 10th student will see 9 hats with only one or two colours. One of those colours has to have an odd number showing. The initial setup might be easier for the students if the 10th student just said which colour has an odd number showing. The rest of the students will be correct through the same logical reasoning as in Solution 1.