100 hat solution

I suddenly realised that I haven't yet posted the solution to the hundred hat problem. In slightly mathematical language, here's the solution. Replace black by 0 and white by 1. Let the ith prisoner have hat colour c(i). The first person shouts out the value of

The next person does the calculation

and shouts his answer out. In general, since the kth prisoner knows c(2), . . . , c(k-1), (having heard them shouted), c(k+1), . . . , c(100) (being able to see them) and

courtesy of the first prisoner's shout, he can calculate c(k) = (c(k) mod 2). Of course, here we've set the number of prisoners to 100, but this isn't necessary.

For non-mathematically literate folk:

The idea really isn't complicated at all - if it seems so, then I've explained it badly. First of all, knowing if a hat is white or not is equivalent to knowing its colour since there are only two. The first person to go counts up the number of white hats he can see in front of him. If it's odd, he shouts 'white' and if it's even, he shouts 'black'. Prisoner number 2 then counts the number of white hats in front of him. He then figures out if it's odd or even. We know that

• (odd number) - (odd number) = even number
• (odd number) - (even number) = odd number
• (even number) - (odd number) = odd number
• (even number) - (even number) = even number

Prisoner 2 can use prisoner 1's shout as the first number and his own tally as the second. This spits out something on the right hand side. If he gets 'even' he shouts black, if he gets 'odd' he shouts white. Prisoner 3 has heard prisoner 1 and 2 and also knows whether the number of hats in front is even or odd. He then does a similar calculation and shouts out the right answer...and so on.

Perhaps this isn't perfectly explained. Never mind.