The classic version
n prisoners stand in a line, each wearing a red or blue hat. Each sees every hat in front of them but not their own or those behind. Starting from the back, each says one word - "red" or "blue" - and everyone hears it. A correct guess means survival. They may agree a strategy beforehand.
How many can be guaranteed to survive?
The answer: n - 1
Everyone except the last person in line, who survives with probability 1/2.
The strategy
The prisoner at the back counts the red hats they can see and says "red" if that count is even, "blue" if odd. Their own answer is a coin flip for them, but it broadcasts one bit of information to everyone else.
The next prisoner counts the red hats they can see. If their count has the same parity as announced, their own hat must be blue; if the parity differs, their own hat is red. They answer correctly.
Everyone after that tracks the announced parity, adjusts for every answer already given, and deduces their own hat exactly. Each subsequent guess both saves that prisoner and updates the running parity for the rest.
Why parity
One person can transmit exactly one bit. Parity is the maximally useful bit here because it is a global property that every other prisoner can compare against their own partial view - each of them is missing exactly one hat, so one bit resolves it.
Common variants
Three or more colours. Use arithmetic modulo the number of colours instead of parity. Assign each colour a number 0 to k-1, and the first prisoner announces the sum of what they see, mod k. Same structure, same result: n - 1 survive.
No ordering, simultaneous guesses. Much harder, and the answer depends on whether they may pass. With passes allowed, Hamming-code strategies achieve surprisingly good results - for 3 prisoners a well-chosen strategy wins 75% of the time, versus 50% for naive guessing.
Infinitely many prisoners. Requires the axiom of choice and stops being an interview question.
What is being tested
Whether you can find an encoding. That is the same skill as designing a signal in a constrained channel, and it recurs across information-flavoured puzzles.
More in brainteasers.