[adam-f]

This reminds me of a problem I learned in UCSC (and was accused of cheating by the teacher when I figured it out in five minutes).

100 Prisoners are told they will be given white or black hats, but they don't get to see the hat they're wearing, they will be lined up facing the same direction, and they gun-to-the-head, say "black" or "white" and if they guess the color of their hat, they get to live.

They get to speak back to front, i.e., the rearmost prisoner sees all the hats ahead.

One strategy for optimizing the number left is to speak the color of the hat directly in front of you, in which case the prisoner ahead gets to live by repeating that color. This saves 50%, but of course there's a better solution.

[mikeash]

Spoiler ahead! Potential answer!

My solution is that the first prisoner states the color of the hat in front of him, the second prisoner states the color he just heard, and so forth with odd and even numbers until you get to the end. This saves 75% (even numbers are guaranteed to live, odd numbers live with 50% odds).

Is this optimal?

[ssfermoy]

If they decide the guy at the back indicates an odd number of black hats by saying white or an even number of black hats by saying black. Now the remaining prisoners all live and the back guy has a 50/50 shot.

[Ellipsis753]

That's awesome. To me it seems like a parity bit for RAID or an error-correcting code.

[mikeash]

Very nice. It took me a while to see why that works, so I wonder how long it would have taken me to come up with it.

Now that I get it, it seems almost obvious. It's basically the same as my solution, except I'm essentially using this technique on 50 separate lines of 2 people each.

[ssfermoy]

Glad you like it. Heard this as an interview question at a trading company. Gave something similar to your solution and was asked for a better one, eventually work my way to the solution above but was given no indication if it was what they wanted. It wasn't a pleasant experience.