Sunday, November 1, 2026

10 Sailors in Hats

The 10 sailors washed ashore after a shipwreck, only to learn that a monster was waiting for them. The monster lined the sailors up, numbered 1 (at the front) to 10 (at the back), and placed a black or white hat on each one. Each sailor can see only the hats of the sailors in front of him. He cannot see his own hat or the hats of those behind him. The monster questions the sailors one at a time, starting with sailor 10, who can see all the hats except his own, and then proceeds forward to sailor 1. Each sailor must name the color of his own hat. Those who guess correctly survive, and the others die. The sailors may agree on a strategy in advance, but they cannot communicate once the monster begins questioning them. They must find a strategy that guarantees at least 6 of them survive, regardless of how the hats are arranged.

The answer: The sailors must agree on a checksum that depends on the colors of all the hats. The simplest one is a parity check. Sailor 10 counts the black hats among sailors 1 to 9. He says “black” if the count is odd and “white” if it is even. Sailor 10 may die, since his own hat is not part of the count. Each following sailor can then deduce the color of his own hat from the announced parity and the hats he sees in front of him, and then announce it. Each correct guess gives the next sailor the information he needs.

Another option is an XOR checksum. Treat black as 1 and white as 0. Combine the hats of sailors 1 and 2 with XOR, then combine that result with sailor 3’s hat, and continue recursively until all of hats 1 to 9 are included. Sailor 10 calculates this checksum and announces the result. Each sailor after him then applies the same function. He knows the checksum and all the hats in front of him, so he can compute his own hat’s color and announce it.


No comments:

Post a Comment