Brainteasers · Logic and deduction · Medium
Eight hats in a line
Eight prisoners stand in a line, all facing the same way, so that each sees the hats of everyone in front and no others, not even their own. A black or a white hat is put on each head by a warder who knows the prisoners' plan and chooses the colours to defeat it. Starting from the back of the line and moving forward, each prisoner in turn calls out "black" or "white", once. Everyone hears every call, and nothing else may be communicated. A prisoner who calls the colour of their own hat goes free. The prisoners agree a plan beforehand. What is the largest number of prisoners that a plan can be certain to free?
Answer and solution
Answer
7
Solution
The back prisoner calls the parity of the white hats in front; everyone else recovers their own colour from that parity, the calls since and the hats they see.
The back prisoner calls "white" for an odd number of white hats in front. The next prisoner counts the white hats in front: if the parity differs from the call, their own hat is white. Each later prisoner does the same after allowing for the hats already called correctly behind them. Those seven are always right. The back prisoner cannot be certain: no one sees that hat, so the call is the same for both of its colours. The answer is 7.
Logic and deduction comes up in 6 firms' roundsD. E. Shaw · Tower Research · Millennium · +3
These 7 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.