I guess this is similar to the original question, in that you have to assume some way to break the inherent symmetry of the situation without the method of doing so being stated by the problem.
Yeah, whichever works best for you.
And I just realized you got the simplified answer already in post #33 (I only saw your last line when I was skimming posts this morning). Lots easier than my original answer!Now that I understand the problem, I propose a small extension. Same rules, except that there are 7 prisoners. What’s the best they can do? How about 31 prisoners?
Brilliant, Dr. Strangelove! I never knew (or had forgotten :smack: ) that you can get arbitrarily high success with sufficiently many prisoners.
[SPOILER]
Number the seven prisoners in a circle so that, e.g. for prisoner #4, the other prisoners appear left-to-right in the order 5,6,7,1,2,3. Each prisoner follows the same prescription:
Write ‘Red’ if you see (with ‘-’ denoting White’)
(a) - - - - - -
(b) R R - R - -
(c) - R R - R -
(d) - - R R - R
(e) R - - - R R
(f) R R R - - R
(g) R - R R R -
(h) - R - R R R
Write ‘White’ if you see
(a) R R R R R R
(b) - - R - R R
(c) R - - R - R
(d) R R - - R -
(e) - R R R - -
(f) - - - R R -
(g) - R - - - R
(h) R - R - - -
Write ‘Pass’ otherwise.
This exhibits 7*16 winning guesses out of 128 for 87.5% success chance.
Verifying by hand that the other six players pass on each of these successes is somewhat easier than it might seem at first glance due to symmetries.
This is related to lattice theory, I think, and error correcting codes.[/SPOILER]
[spoiler]I was hoping you’d be up for the challenge :).
I did not check every part of your answer but it looks equivalent to mine upon a quick skim. You did of course find the correct upper bound.
For what it’s worth, here’s the answer in the form that I thought of it:
We assign 16 “death codes”. They are (in binary, since that’s how I roll):
0000000
1110000
1001100
0111100
0101010
1011010
1100110
0010110
1101001
0011001
0100101
1010101
1000011
0110011
0001111
1111111
If the other colors match one of the death codes, then you guess the opposite of the color in your position of that death code. If anyone sees 000000, for instance, then they guess 1. If there’s no match to a death code, you pass.
As you inferred, these cases completely cover the 128 possibilities, so we can see that they’re optimal. Aside from the death codes, the remaining cases each get exactly one guess, which is correct. As you noticed, the solution has some nice symmetries to it which make it (somewhat) easy to verify.
The 31 prisoner case is evil and I wouldn’t expect anyone to do it (certainly not by hand!). But I know the trick…
[spoiler]As you guessed, it’s related to error correcting codes. Specifically, the Hamming codes.
That’s how I came up with the extended version–I recognized that the 3-prisoner case is equivalent to a simple Hamming[3, 1] code. There is one bit worth of data–which maps to our death codes–and 2 bits of error correction. All codes in our set are exactly one bit position away from one of the death codes (this is called the Hamming distance: the number of bits you have to flip to get from one code to another).
The 7-prisoner case is just the Hamming[7, 4] code. There are 4 bits of data (16 death codes) and 7 bits total (128 codes). (128-16)/128 gives you the 87.5% number.
Finally, the 31-prisoner case uses the Hamming[31, 26] code. The prisoners have a difficult task if they are to memorize 26 bits worth of death codes! There is an easier way, of course (Wikipedia has a good description, if you’re interested). The important part is that you can achieve a 1 - 1/2[sup]31-26[/sup] = 96.9% success rate.
In fact there are Hamming codes for any word size of 2[sup]N[/sup]-1 bits, so we have puzzles for 3, 7, 15, 31, 63, etc. prisoners, each with half the failure rate of the last. They are all optimal codes (they cover every code combination), so we can also be sure that the solution is optimal (though not unique).[/spoiler][/spoiler]