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:
  • The 1st person suggests to overpower the guard when they come back.
  • The 2nd person points out there may be more guards and closed doors outside. Also, one or more of you might get hurt in the process.
  • The 3rd person proposes that everyone should just say a different color. Upon reflection, he decides that it's better if everyone says the same color.
  • The 4th person criticizes the 3rd person idea: the colors are probably not uniquely assigned otherwise it would be easy to tell what color you have after hearing the other 6.
  • The 5th person mumbles something about a spy who will always work against any strategy you'll come up with.
  • The 6th person thinks that you should trust each other or at least assume that everyone will work with the strategy or you will never escape.

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 perfect strategy.

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

Solution

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

Now, when you get information about other colors, sum their assigned numbers together. For example, set $\{red,red,yellow,blue,violet,indigo\}$ gives sum $0 + 0 + 2 + 4 + 6 + 5 = 17$. Add to the sum the smallest number which makes the result divided by $7$ your unique number. In the example, $17$ gives remainder of $3$ when divided by 7, so you must add $3$ in order to get a remainder of $6$, 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 > 0$ and that the number of colors is not greater than $n$ (we'll see why this assumption is necessary later). We assign each prisoner and color a number in range $\{0,\ldots,n-1\}$.

Let $p_0, p_1, \ldots, p_{n-1}$ be colors assigned to prisoners so that $p_i$ is an integer representing a color assigned to $i$th prisoner. The sum of them is then $S = p_0 + p_1 + \cdots + p_{n-1}$.

Let's define a sequence $s_i = S - p_i$ for each $i$ 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 $p_i$:

$s_0 + p_0 \equiv 0 \pmod n$
$s_1 + p_1 \equiv 1 \pmod n$
$\ldots$
$s_{n-1} + p_{n-1} \equiv n - 1 \pmod n$.
 
From the definition of $s_i$ we know that $s_i + p_i = S$ in each of the equations, so $i$th prisoner solves an equation equivalent to $S \equiv i \pmod n$.
Since $i$ is in range $\{0, 1, \ldots, n-1\}$ exactly one of the equations is true.
 
Since $p_i$ is not greater than $n$, 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 $n$. Then by pigeonhole principle there are at least $2$ different possible colors which will be solutions to at least one of the equations (since they give the same reminder when divided by $n$). This means that at least one prisoner has to guess from more than one possible colors and the probability of winning is less than $1$. $\blacksquare$


Cover photo credit: University of Rochester, Interfaith Chapel 1 via photopin (license)
 

Comments