More Hat Puzzles

By /
⏱ 3 min read

I buried four fishermen up to their necks in the sand on the beach at low tide for keeping their fishing spot a secret from me. I put a hat on each of their heads and told them that one of them must shout out the correct color of their own hat or they will all be drowned by the incoming tide. I give them 10 minutes to do this. Fisherman A and B can only see the sand dune I erected. Fisherman C can see that fisherman B has a white hat on. Fisherman D can see that C has a black hat, and B has a white hat. The fisherman have been told that there are four hats, two white and two black, so they know that they must have either a white or a black hat on. who shouts out the color of their hat and how do they know?

Solution

Fisherman C shouts out.

Fishermen A and B are in the same situation – they have no information to help them determine their hat colour so they can’t answer. C and D realise this.

Fisherman D can see both B and C’s hats. If B and C had the same colour hat then this would let D know that he must have the other colour.

When the time is nearly up, or maybe before, C realises that D isn’t going to answer because he can’t. C realises that his hat must be different to B’s otherwise D would have answered. C therefore concludes that he has a black hat because he can see B’s white one.

2026 Update: Hat Puzzles and Distributed Coordination

Hat color guessing puzzles — where prisoners wearing hats must guess their own color without communication — are a beautiful model of distributed coordination under uncertainty. They remain asked at Google, quantitative finance firms, and CS theory interviews.

The key variants and their solutions:

  • 2 prisoners, 2 hat colors: No strategy guarantees better than 50% — it’s equivalent to guessing a fair coin
  • N prisoners, 2 colors, line arrangement: Optimal strategy — first prisoner announces parity of all hats seen; remaining prisoners use parity to deduce their own hat with certainty. N-1 of N survive guaranteed.
  • Infinite prisoners with choice to pass: Using the axiom of choice, almost all can guess correctly — but the proof is non-constructive

The parity strategy for N-1 guaranteed correct:

def hat_parity_strategy(hats):
    """
    hats: list of 0/1 values, hats[0] is at the back (first to guess).
    First prisoner announces XOR of all hats they see — sacrifices themselves.
    Each subsequent prisoner uses running parity to deduce their own hat.
    Returns list of guesses (first may be wrong; rest are correct).
    """
    n = len(hats)
    guesses = [0] * n
    known_parity = 0

    # First prisoner: announce XOR of all visible hats (hats[1:])
    announced_parity = 0
    for h in hats[1:]:
        announced_parity ^= h
    guesses[0] = announced_parity  # May or may not be correct

    known_parity = announced_parity ^ hats[0]  # Update with actual first hat

    # Each subsequent prisoner deduces from running parity
    for i in range(1, n):
        guesses[i] = known_parity  # My hat must be this value to match parity
        known_parity ^= guesses[i]  # Update running parity with confirmed hat

    correct = sum(g == h for g, h in zip(guesses[1:], hats[1:]))
    return guesses, correct  # At least n-1 correct

hats = [1, 0, 1, 1, 0, 1]
guesses, correct = hat_parity_strategy(hats)
print(f"Correct: {correct}/{len(hats)-1} guaranteed")

Connection to distributed systems: The hat puzzle models Byzantine consensus — how do nodes agree on a value with limited communication? The parity strategy is a simplified error-correcting code (Hamming code). Real distributed consensus protocols (Raft, Paxos) solve the same fundamental problem with more complex “hat color” analogs.

Scroll to Top