Modular Arithmetic: Prisoners Hat 3

Now suppose there are 100 prisoners and each prisoner is assigned a hat of one of three colors: red, green, or blue. Each prisoner can see everyone else's hat but not their own. They will be called in random order to guess their own hat color, and if they guess correctly, they are freed. The prisoners can plan a strategy the night before to maximize the number saved. What is the best strategy they can adopt and how many prisoners can they guarantee to save?

Answer

The prisoners can still guarantee that at least 99 of them will be saved, though the first prisoner now has only a 1/3 chance of survival. They assign scores to the colors: red = 0, green = 1, and blue = 2.

The first prisoner observes the colors of the other 99 prisoners and calculates the total score $$ s $$ of those hats modulo 3. Specifically: if the remainder $s \% 3 = 0$ , he announces "red"; if $s \% 3 = 1$ , he announces "green"; if $s \% 3 = 2$ , he announces "blue".

This announcement communicates the remainder of the sum of scores of all 100 hats modulo 3 to the others. The first prisoner has a 1/3 chance of survival because his own hat color might match his announcement.

Each subsequent prisoner (among the remaining 99) can see all hats except their own and they ignore the first prisoner’s hat (obvious why). They calculate the total score $$ x $$ of the other 98 prisoners they can see. Knowing the remainder announced by the first prisoner, each prisoner can determine their own hat color because:

(x + \text{their hat score}) \% 3 = \text{remainder announced}.

Now, $(x + 0) \% 3$ , $(x + 1) \% 3$ , and $(x + 2) \% 3$ are all distinct (see comment below), hence the prisoner can uniquely determine their hat color.

Thus, while the first prisoner has a 1/3 survival chance, all subsequent 99 prisoners will guess correctly, guaranteeing that at least 99 prisoners are saved.

Notes and comments

Comment 1: If $x_1 \% y = x_2 \% y$ , then $(x_1 - x_2) \% y = 0$ . From this property, we can also show that $x \% y$ , $(x+1) \% y$ , $\ldots$ , and $(x+y-1) \% y$ are all different numbers.