100 Lamp solution, 100 Hat problem.

Yesterday, I posted a little puzzle about a hundred blind lamp lighters. Don't read on if you'd like to give this a go for yourself. Here's the solution: The squared number lamps will be on at the end, i.e. 1,4,9,16,25,36,49...etc. We need to find the number of lamps which are on at the end. So let's try and figure out in what circumstances a given lamp will be on. As an example, think about whether the 6th lamp will be on. It's turned on by the 1st guy, off by the 2nd, on by the 3rd, and then off by the 6th. Notice that we've just listed all of the numbers that divide 6, i.e. 1,2,3,6. In general, for a lamp to be off, the button should have been pressed an even number of times; for it to be on, the button should have been pressed an odd number of times. For the kth lamp, the number of times it is pressed is the number of numbers dividing k. Now let's look at another example. The 12th lamp will be pressed by guys number 1, 2, 3, 4, 6, 12. We can split these divisors into pairs: (1,12), (2,6), (3,4) where multiplying the numbers together gives 12. Since we can pair these things up, there is an even number of divisors. Suppose now for example, that we take the number 36. Here we have divisors 1, 2, 3, 4, 6, 9, 12, 18, 36. In this case, we have the pairs (1,36), (2,18), (3,12), (4,9), and 6 is paired with itself. Here we have an odd number of divisors, the reason being that one number (6) is paired with itself. So a general number k has an odd number of divisors if (and only if) one divisor is paired with itself, that is, there is some number which multiplied by itself gives k. In less obtruse words, k is a square number. And there's the proof. (Note that actually, the number of lamps doesn't matter as long as it's the same as the number of lamp lighters.) Last night after the Pure Postgraduate seminar, a post-pub discussion brought up the following hundred hat problem: Here's another problem, this time with a hundred hats. Suppose that there is a strange kingdom where logical prowess is prized above all other things. 100 prisoners languish in prison all sentenced to death. Since the king is a nice sort of fellow, he decides that he will set the following challenge: The prisoners are all lined up facing along the line so that a given prisoner can see all the people infront of him, but not himself or the people behind him. A hat is put on each prisoner, either white or black. The prisoner at the back (who can see everyone else's hat but not his own) then shouts out the colour he thinks his hat is. If he gets the answer right, he is allowed to live. If he gets the answer wrong, he dies. The same process is repeated by the prisoner second from the back and so on. The prisoners are allowed to confer before the whole process and so can decide on a strategy. How many prisoners can defintitely be saved by an appropriate strategy?

(Hint: At least half can be saved. The guy at the back can't be helped: he may as well shout randomly. He could however, help the guy in front of him. If they decide beforehand that the first guy will shout the colour of the hat in front of him, then at least he can save the second guy who will then know his own hat colour. Continuing the process, we can save for certain at least every other man. In fact, they can do a lot better...)