Question:

There are 7 prisoners sitting in a circle. The warden has caps of 7 different colors (an infinite supply of each color). The warden places a cap on each prisoner’s head – he can choose to place any cap on any other’s head. Each prisoner can see all caps but her/his own. The warden orders everybody to shout out the color of their respective caps simultaneously. If anyone is able to guess her/his color correctly, he sets them free. Otherwise, he sends them into a dungeon to rot and die. Is it possible to devise a scheme to guarantee that nobody dies?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution:

Assign to each of the 7 colors a unique number from 0-6. Henceforth, we will only be doing modular arithmetic.

Assign to each of the 7 prisoners a unique number from 0-6. If the number assigned to prisoner P is N, then P always guesses that the sum of the colors assigned to all prisoners is M (modulo 7). Thus, he calculates his own color under this assumption (`= (M - sum(colours of the 6 prisoners he can see))%7`).

There will always be a prisoner who guesses the correct sum (as the sum lies in 0-6), and this prisoner therefore correctly guesses his own color.

If there is a solution, then exactly one prisoner is correct (no more). This is because there are 7^7 scenarios.

Each prisoner’s response is a function of the colors of the other 6, so if you fix their colors and vary his color, you can see that he will be correct in exactly one-seventh of the cases (=7^6). The sum (across all scenarios) of the number of prisoners who are correct is 7*(7^6)=7^7.

If each scenario is to have at least one person right, this implies that each scenario cannot have more than one person who is right.

Being right about one’s color is equivalent to being right about the sum of colors of all prisoners (modulo 7). (The colors of the other 6 are known.) So guessing one’s color is the same as guessing the sum. How do we make sure that at least one person guesses the correct sum? By making sure that everybody guesses a different sum.