Math Puzzle - 7 Hats - Page 5

Let's say three colors, color 1, color 2, and color 3. The prisoners arrange themselves as prisoner 1, 2 and 3. Each prisoner has a different strategy, which combined will let them live.

Case 1: both hats you see are same color (11, 22, or 33)
prisoner 1 writes down the same color
prisoner 2 writes down color of one greater
prisoner 3 writes down color of two greater

for example, if you see that the other hats are both color 1, (if you see 11):
--prisoner 1 writes down hat 1 (same)
--prisoner 2 writes down hat 2 (one greater)
--prisoner 3 writes down hat 3 (two greater)

If you see 22
--prisoner 1 writes down 2 (same)
--prisoner 2 writes down 3 (one greater)
--prisoner 3 writes down 1 (two greater)

If you see 33
--prisoner 1 writes down 3
--2 writes down 1
--3 writes down 2


Case 2: if the hats you see are different color (12, 23, or 31)
prisoner 1 writes down the remaining color
prisoner 2 writes down the the left color
prisoner 3 writes down the right color

*note i don't mean traditional left and write.

for example if you see 12
--1 writes down 3
--2 writes down 1
--3 writes down 2

if you see 23
--1 writes down 1
--2 writes down 2
--3 writes down 3

if you see 31
--1 writes down 2
--2 writes down 3
--3 writes down 1


This strategy will cover all 3^3 = 27 possibilities.

for cases where all numbers are same, prisoner 1 guesses right
111, 222, 333

for cases where all numbers are different, prisoner 1 guesses right
123, 231, 312
132, 213, 321 (symmetrical to first)

for cases where two numbers are same, then either prisoner 2 or prisoner 3 will guess right
(prisoner 2 first case, prisoner 3 second case)
121, 113 (prisoner 2 sees 11, so he guesses 2. prisoner 3 sees 11, so he guesses 3)
232, 221
313, 332

112, 131 (prisoner 2 sees 12, so he guesses 1. prisoner 3 sees 31, so he guesses 1)
223, 212
331, 323

211, 311 (symmetrical to case above, since person 2 still sees 12, person 3 still sees 31)
322, 122
133, 233

And those are all the cases.

before sitting down, everyone agrees to only consider one person's hat, person A. Then, they will each assign each other a color based on the 7 colors available. If person A is wearing red, person B will be the first to give his paper to the king; it doesn't matter what person B guesses. Then person A knows his hat is red. If person A's hat is orange, person C will be the first to give his paper to the king, and person A will know his hat is orange, and so on. If person A is wearing the 7th color that is assigned to him, nobody will turn in the paper to the king and person A will know his hat is the 7th color.

modulo 2

We assign each color a number from 0-6

Now we can say that the prisoners are essentially getting a number, c0,c1,c2,c3,c4,c5,c6.

S = (c0 + c1 + c2 + c3 + c4 + c5 + c6) modulo 7

S has seven possible values, 0-6

At this point, what each prisoner is doing is trying to guess what S is, and solving for their own number to match S.

Prisoner 0 assumes S = 0, and solves the equation c0 = S - (c1+c2+c3+c4+c5+c6)
Prisoner 1 assumes S = 1, and solves the equation c1 = S - (c0+c2+c3+c4+c5+c6)
and so on..

At least one of the 7 prisoners will assume the correct S value. That prisoner will be able to guess the correct number for their own hat.

Assign each color a value 0-6. Each person takes sum of all the colors he sees and says the result in mod 7 (says the corresponding color to the sum). If you let a_1 be the first person's color, a_2 second guy's, etc, and S the sum of all, the first person will say S-a_1 (mod 7), second S-a_2, etc. Now it is possible to express all a_2, a_3, ... a_7 in terms of a_1. Add all values (expressed in terms of a_1) and you get 7a_1 + X, for some X. X = S (mod 7). Now the only thing the last person has to do is subtract and get his color.