I don’t believe in any event that more than one prisoner should make a guess. The problem requires at least one, and if one is wrong, everyone dies, so it would seem that any correct solution would have three prisoners writing “pass” and the remaining one guessing.
[spoiler]Again, the idea is to concentrate badness. They can’t die twice, so their wrong guesses should overlap.
Imagine a deterministic version where they have to apply the same ruleset to all 16 combinations, and they get a million dollars for however many they win. They are handed 16 cards which can say any of WIN, LOSE, or PASS, but with the restriction that the number of WIN cards has to match the LOSE cards. They distribute the cards among the combinations and tally things up at the end.
The ideal, then, is for each of the prisoners to put their LOSE cards on the same combinations, but spread out the WINs (with the rest filled out with PASS). Ideally, each losing combo would get all four LOSE cards but this isn’t quite possible.
Incidentally, I just realized that there is a simpler solution. Tell player 4 to just always pass. For the remainder, play opposite to the others if they both play the same (otherwise pass). Still wins 3/4 of the time.[/spoiler]
No rule against touching your paper to your still wet for head paint and writing the color next to it?
M r puppies
o no a r not
o s a r
m r not puppies
s a r
m r not puppies
o s a r – c m p n?
L i b, m r puppies!
[spoiler] Maybe I am just being daft, but I am not seeing it. A pass never gets anyone killed unless all four prisoners pass. Likewise, two passes, one win, and one loss kills them all.
A correct choice does nothing unless the other choices are also correct or passes. The best strategy has to be to take three passes and try to maximize the chances on the one choice. And that one choice, no matter if the prisoner sees three reds, three blues, or any combination is a random 50/50 chance for his own color.[/spoiler]
[spoiler]Let’s simplify the puzzle to a totally equivalent one (the presented puzzle has a bit of a red herring in it). Same rules, but with 3 prisoners.
The solution is for each prisoner to vote opposite if the two others have the same color; otherwise pass. Let’s enumerate all eight possibilities, what the rule tells them to vote (in 123 order), and if they live/die:
RRR: BLUE BLUE BLUE (DIE)
RRB: PASS PASS BLUE (LIVE)
RBR: PASS BLUE PASS (LIVE)
RBB: RED PASS PASS (LIVE)
BRR: BLUE PASS PASS (LIVE)
BRB: PASS RED PASS (LIVE)
BBR: PASS PASS RED (LIVE)
BBB: RED RED RED (DIE)
75% chance to live. Note that each prisoner voted RED twice, BLUE twice, and PASS four times. Furthermore, note that of the times they voted, they were wrong half the time–exactly as we’d expect from probability. Specifically, they encountered all four combinations of R-wrong, R-right, B-wrong, and B-right.
But the wrongs were concentrated into just two of the combinations (RRR and BBB), while the rights were spread out among the remaining six. It only takes one error to die, so if you are going to make errors you want everybody to make them at once.[/spoiler]
You’re both in good company. Many top puzzle solvers reached this same conclusion, … including septimus. :eek: :o
Yes, I’m a sadist. 
I didn’t know that! Can you confirm you’ve double-checked this before I tax what little remains of my brain to understand it?
As it turns out, we’ve both repeated the puzzle. It felt familiar but only when I found the red herring did it all come back!
[spoiler]The solution is in Hamming codes. For any 2[sup]n[/sup]-1 bit length, there is a Hamming code–which is perfect (no unused combinations), and so provably the best you can do.
A Hamming code gives you numbers that are a minimum Hamming distance (think: number of flips to get from one code to another) of three. This guarantees a solution for that prisoner count.
Consider N=7. There are 128 possible combinations. Among these, we can pick 16 codes, each of which has 7 flipped codes clustered around it. The flipped codes are winners; the original 16 losers. Hence we can win 112/128=87.5% of the time.
For cases where N != 2[sup]n[/sup]-1, one can always ignore some prisoners and pretend that it’s a smaller code. So that’s a lower bound (and also the best you can do for N=4). What I don’t know is if there are intermediate bounds for higher N. Can one do >75% but <87.5% for N=6?[/spoiler]
Clicking the link I see I called you Brilliant for that solution!
… Well, you’re still brilliant, Dr. Strangelove !
Yep, that’s what I came up with. A quick Google search yielded this similar puzzle:
2 17 3 19 7 16 8 11 14 9 12 5
Damn i have one but don’t know how to post a spoiler.
Can anyone help?
[ s p o i l e r ] SOME HIDDEN TEXT HERE [ / s p o i l e r ]
Use the above, but remove the spaces.
I tried that earlier but neither of my browsers (chrome.firefox) allow me to enter any symbols in my reply. It only allows text. I have never had that happen before.
You can’t do brackets? That’s bizarre.
Finally.
What can go up a chimney down,
But can’t go down a chimney up?
an umbrella
What goes on 8 for one year
4 for 19 years
2 for the rest of its life?
Fred & George