7 Prisoners and Colors Puzzle

You find yourself in a closed room with 6 strangers. A guard comes in and says that some time later you are all going to be moved into separate cells and you won’t be able to communicate with one another. Then each of you will be assigned 1 of the 7 colors of the rainbow (red, orange, yellow, green, blue, indigo, violet). However, each of you will be told only the colors of the other 6 prisoners in random order.

If at least one of you guesses their color correctly, then all of you will be freed. However, if none of you guesses correctly, each of you will be tossed in a dark cell and you will not see rainbow ever again. Each of you is given only one chance to guess the color.

After the guard leaves the room, discussion starts:

Everyone now waits for your opinion on the matter. Is there a strategy (without breaking the rules of the game) which can guarantee you freedom? If yes, present the strategy and prove that it works. If not, show the best possible strategy (in terms of probability of winning) and that there doesn’t exist a better one.

Hints

Hint 1: There exists a perfect strategy.

Hint 2: Replace colors with unique integers in range 00 to 66 (for example red=0red = 0, orange=1orange = 1, and so on).

Solution

You agree to assign each color a unique number from 00 to 66, for example orange is assigned number 11 and violet is assigned number 66. Each person is also assigned a single unique number from the same range, for example you could get number 66.

Now, when you get information about other colors, sum their assigned numbers together. For example, set {red,red,yellow,blue,violet,indigo}\{red,red,yellow,blue,violet,indigo\} gives sum 0+0+2+4+6+5=170 + 0 + 2 + 4 + 6 + 5 = 17. Add to the sum the smallest number which makes the result divided by 77 your unique number. In the example, 1717 gives remainder of 33 when divided by 7, so you must add 33 in order to get a remainder of 66, your unique number. The number you needed to add represents the color you must tell the guard.

With this strategy, no matter what colors are assigned, exactly one of you will answer correctly and you will all be freed.

Proof

You probably don’t believe the above claim that the described strategy works so I shall provide proof which will give insight on why the strategy works.

In fact, we can even generalize the strategy. Let’s assume the number of prisoners is n>0n > 0 and that the number of colors is not greater than nn (we’ll see why this assumption is necessary later). We assign each prisoner and color a number in range {0,,n1}\{0,\ldots,n-1\}.

Let p0,p1,,pn1p_0, p_1, \ldots, p_{n-1} be colors assigned to prisoners so that pip_i is an integer representing a color assigned to iith prisoner. The sum of them is then S=p0+p1++pn1S = p_0 + p_1 + \cdots + p_{n-1}.

Let’s define a sequence si=Spis_i = S - p_i for each ii in range. It represents the knowledge of each prisoner: the sum of all colors except his own.

Each prisoner then solves exactly one of the following equations for pip_i:

s0+p00(modn),s_0 + p_0 \equiv 0 \pmod n,

s1+p11(modn),s_1 + p_1 \equiv 1 \pmod n,

,\ldots,

sn1+pn1n1(modn)s_{n-1} + p_{n-1} \equiv n - 1 \pmod n.

From the definition of sis_i we know that si+pi=Ss_i + p_i = S in each of the equations, so iith prisoner solves an equation equivalent to Si(modn)S \equiv i \pmod n.

Since ii is in range {0,1,,n1}\{0, 1, \ldots, n-1\} exactly one of the equations is true.

Since pip_i is not greater than nn, it is a unique solution for each of the equations. To see why the assumption about the number of colors is necessary, suppose the number of colors was greater than nn. Then by pigeonhole principle there are at least 22 different possible colors which will be solutions to at least one of the equations (since they give the same reminder when divided by nn). This means that at least one prisoner has to guess from more than one possible colors and the probability of winning is less than 11. \blacksquare

The puzzle is not mine, I stumbled upon the puzzle while browsing Quora.