This does make it considerably harder in the sense that each prisoner needs much more information, yet also it becomes easier in the sense that with 7 color names, each prisoner can also pass on much more information. As before, parity is the way to go, I think, because each prisoner only needs to make a binary decision for each of the colors. Therefore, passing forward parity information for each color will solve the problem.Seven colors is almost enough to pass forward 3-bit parity, but not quite. A simple scheme to pass 2-bit parity forward would be to number the colors ROYGBIV = 0123456, think of the numbers expressed as binary digits, and let the first prisoner call out a number that encodes the parity of R and O, so the guess would mean:
R = 000 --> R even, O even
O = 001 --> R odd, O even
Y = 010 --> R even, O odd
G = 011 --> R odd, O odd
B = 100 --> R even, O even
I = 101 --> R odd, O even
V = 110 --> R even, O odd
The last 3 are redundant, so one could set up an interpretation under which ROY indicate that Y is even and BIV indicate that Y is odd parity. G cannot be used to tell the parity of Y, because there is no possibility of sending the message 111, so the highest bit of G cannot convey any information. In this way, the first prisoner would convey the parity of R and O every time, and in 3/4 of cases (assuming a random distribution of hat colors) would also convey the parity of Y. One could say, in a probabilistic sense, that he passes 2.75 parity bits forward.
What does the next prisoner do? He counts the hats he sees, and if he notices a difference from one of the conveyed parities, he knows his hat is what made the difference, so that is his color. He states his color, and all further prisoners update their knowledge of the parity of that color. The prisoners continue in this way until it happens that a prisoner does not note any parity differences. In that case, he must have a hat color for which parity information is not yet available, so he is in the same position as the first prisoner.
There is one difference: he knows he does not have one of the colors with parity information, so he is not going to guess one of those unless he is very altruistic, because he would forfeit his own chance at freedom. There is nothing he can do to improve his own chances, but he can again guess a color that will encode the parity of the next 2 hat colors, by naming one of the remaining 5 (or, 3/4 of the time, 4) hat colors. The other prisoners further along the line know the list of colors that have defined parities, so as soon as they hear this prisoner state a color name that is not on the list, they know that new information is coming, and they know how to interpret it:
If 4 colors remain,
G = 000 --> G even, B even
B = 001 --> G odd, B even
I = 010 --> G even, B odd
V = 011 --> G odd, B odd ;
while if 5 colors remain,
Y = 000 --> Y even, G even, B even
G = 001 --> Y odd, G odd
B = 010 --> Y even, G even
I = 011 --> Y odd, G even
V = 100 --> Y even, G odd, B odd .
Therefore, this prisoner can pass on 2 (or, 1/4 of the time, 3) bit parity. At this point, either there are 2 colors left without parities, I and V, which happens (3/4)*1 + (1/4)*(1/4) = 13/16 of the time; or else there are 3 colors left without parities, B, I, and V, which happens of course 3/16 of the time.
The next unlucky prisoner who doesn't note a parity difference has either 2 or 3 hat colors to work with. The case of 2 colors is just the original problem at the start of this thread, and the solution there is clearly just a special case of this solution: if the prisoner sees an even number of I=indigo hats, he calls out "indigo." Note that it is not necessary to encode parity for the last color, V=violet, because at this point, if a prisoner does not detect any parity differences in ROYGBI, the color of his hat must not be on that list, so it must be V. Prisoners further along the line do not need to update their parity lists when they hear "violet" for this reason, so V is treated just like "black" in the original problem.
If there are still 3 colors, the prisoner can say:
B = 00 --> B even, I even
I = 01 --> B odd
V = 10 --> B even, I odd,
which will define the parity of B and 1/2 of the time also the parity of I. The remaining 1/2 of the time, one more prisoner will be unlucky and have to determine the parity of I.
I have deliberately gone into lots of detail here, to illustrate the process. The summary answer is this:
If there are n hats without parity yet assigned, number them 0 through n-1, and encode parities for the next m hats by the digits of a binary number c, and call out the color with number c. What is m? Let k = integer part of log_2(n), and let l = n - 2^k. Then m is either k or k+1, depending on whether the bit pattern differing from that of c in just the highest bit also occurs among the binary numbers from 0 to n-1. If it does, then m=k+1 because an additional parity bit can be passed. This will happen in l cases out of 2^k. (Note: the ability to pass information in the highest bit is conditioned on the pattern of the lower bits, so the probability is NOT 2l/n. We are not looking at the whole bit pattern; the probability question is: for a given pattern of lower bits, are there or are there not two different high bits in our number list? There are exactly l bit patterns for which this is true.)
All prisoners further down the line can therefore deduce both which parities have been defined thus far, and what those parities are. If a prisoner detects no difference between the parities he deduces from the previous prisoners' choices, he uses the method above to choose a hat color. If he does detect a difference, the parity that differs is his hat color, and he calls it out.
Some notes about assumptions:
1) I have assumed that no prisoner will willingly sacrifice himself, but is happy to pass on as much information as he can. If the first few prisoners are willing to sacrifice themselves, then there is a simpler strategy: for n hat colors, the first prisoners each encode k parities until all but one color has a parity, then all prisoners just look for parity changes. This will sacrifice 1 + integer part of n/k prisoners with probability (n-1)/n, which gives an expected number of int((n+k)/k)*(n-1)/n, which for large n is roughly n/k.
2) In the actual strategy, the expected number of prisoners lost is harder to compute in general, because the formula is recursive. In each particular case, however, it is easy to calculate: Assume all 7 colors actually occur. Then one can make a decision tree, where the nodes are the number of hats without parity yet, parentheses are probabilities that that prisoner will be lost, and branches are labeled with probabilities of reducing the parity that much:
7 (6/7)
/ \
1/4 / \ 3/4
/ \
/ \
/ \
5 (4/5) 4 (3/4)
/ \ /
/ \ /
3/4 / \ / 1
/ 1/4 \ /
/ \ /
(2/3) 3 --------- 2 (1/2)
\ 1/2 /
\ /
1/2 \ / 1
\ /
\ /
1 (0)
In this case, the expected number lost is
6/7 + 1/4*4/5 + 3/4*3/4 + 1/4*3/4*2/3 + 1/4*1/4*1/2 + 3/4*1*1/2 = 2.151. Those lost are only among the unlucky prisoners who do not see parity differences; all other prisoners are saved. It'should be clear that the number of unlucky prisoners is roughly log_2(n), each of whom has a probability of being lost which is less than 1 (in fact it is 1- 1/(current number of hats without parities)). This gives an approximate upper bound of log_2(n) on the number of prisoners lost, independent of the total number of prisoners.
Well, I must say that this was considerably more elaborate than the first solution. I do not know whether this is optimal in terms of number of prisoners saved, but it must be pretty close, since it passes the maximum amount of information forward (or at any rate, the maximum amount that I can see how to pass).
--Stuart Anderson