Of Prisoners and Hats

A bored prison warden calls together 100 very smart prisoners and announces that they will be playing the following Sadistic Game.

Each prisoner will be made to wear a hat which they cannot see. The colour of the hat may be black or white. After this they will be lined up in positions marked 1 through 100.
Each prisoner gets to see the hats of everybody in a position higher than his. (So prisoner 1 gets to see all the hats but his own, prisoner 2 sees all hats but his own and prisoner 1’s, etc)

Now starting with prisoner 1, the warden will ask each man the colour of his hat.
He can only answer “Black” or “White”. The answer will be announced on the public address system so that all can hear. The warden, in turn, will announce whether the answer is right or wrong. This, too, is announced on the PA system.
And yeah, by the way, anyone who gets their colour wrong will be executed immediately.
(That’s where the sadism comes in!)
The prisoners are given a day to come up with any scheme they can think of to save themselves.
Question: How many prisoners can be saved for certain?

So, as a first shot, suppose each man simply makes a guess. There’s a 50-50 chance of being right, so on average about half will survive.
But this is not guaranteed. There’s a very small, but non-zero, probability that everyone will be wrong! Guesswork gives zero certainty.

To guarantee that at least 50 people survive, here’s a scheme.
Every odd numbered person calls out the hat colour of the man in front of him. The even numbered people just repeat what they heard from the man behind them.
But can we do better? Yes.

In fact, there’s a scheme which ensures that all but the first prisoner survives for sure!
This is an extremely neat problem, so you might want to think about it yourself.

…………
…………

Still thinking?

…………
…………

Had enough? Giving up??

Ok here goes.
Prisoner 1 looks at the hats of all in front of him. If among them, there are an odd number of white hats, he says “White” else he says “Black”.
Knowing this answer and comparing with how many white hats he can see, prisoner 2 can deduce the colour of his own hat. (For eg: If prisoner 1 says “White” and prisoner 2 sees only an even number of white hats, he can deduce that his own hat is white).
Now knowing prisoner 2’s answer, prisoner 3 can similarly deduce his own hat colour and so on.
Done!
Only prisoner 1 has a 50-50 chance of being executed, but every noble cause needs a martyr.

Let’s Have More Colour:

Flabbergasted by the amazing escape rate, the warden tries another ploy. Maybe adding another hat colour, say, Red will improve the odds (his, not the prisoners’). Of course, he now has to give them the option of saying Black, White or Red in answer to his question, but he reckons that more prisoners will be wrong this time.
Sorry, Mr. Warden, you are still out of luck! Once again, all but the first prisoner get their colour right – this time using some “mod 3 arithmetic”.

The idea is, replace every integer, positive or negative, with its remainder when divided by 3.
So, for example, 9 is 0, 19 is 1 and -1 is 2.
For brevity, for any integer N, we say “N mod 3” to mean “the remainder left when N is divided by 3”.

Now the thing is, you can add numbers “mod 3” – which means simply add the numbers and take the remainder mod 3.
So, (46 + 21) mod 3 = 67 mod 3 = 1

It doesn’t matter if you first add the numbers and go mod 3, or take each number mod 3 and then add. For example:
(46 + 21) mod 3 = (46 mod 3 + 21) mod 3 = (1 + 21) mod 3 = (1 + 21 mod 3) mod 3 = 1

Similarly, one can subtract and multiply mod 3. Division is trickier and we don’t need it here.

So, back to the prisoners. Once again, the plan is ingenious, but elegant.
Black hats are given a “value” of 0, white hats get value 1, and red hats get the value 2.
Prisoner 1 simply calculates the total value of all the hats he sees mod 3.
He calls out Black, White or Red, if his answer is 0, 1 0r 2 respectively.
Using this, the other prisoners can work out the colour of their hat.

To illustrate, suppose prisoner 1 sees 45 black, 39 white and 15 red hats.
The total mod 3 is: (45*2 + 39*1 + 15* 2) mod 3 = 0
So, he calls out “Black”.
Now suppose prisoner 2 is wearing a red hat.
Then he will see, in front of him, 45 black, 39 white and 14 red hats.
His total mod 3 is: (45*2 + 39*1 + 14* 2) mod 3 = 28 mod 3 = 1
Having heard prisoner 1’s answer on the PA system, he simply subtracts his total from prisoner 1’s total mod 3.
This gives: (0 – 1) mod 3 = -1 mod 3 = 2
2 is, of course, the value for a red hat.
Similarly, prisoner 3 can get his hat colour using the answers of prisoner 1 and 2, plus the hats he can see.
Once again, everyone but the first prisoner escapes with certainty.

Our warden is apoplectic!
To his growing frustration, he finds that changing the number of prisoners makes absolutely no difference. A hundred prisoners, or a billion, everyone escapes for sure, except the first (and even he might get lucky sometimes).
Increasing the number of hat colours is similarly futile.
Given a million colours, the prisoners simply use “mod 1 million arithmetic” (plus some very rapid mental calculation), to get the correct answer every time.
With more colours, the likelihood of the first prisoner being executed increases, but that is small consolation for the jailor who was hoping for some serious body count.

The Seriously Sadistic Game:

Despondent at the high prisoner survival rate, which has made him the butt of prison jokes, our warden e-mails his odious cousin in Tyrannistan, detailing his woes.
The reply is swift: “Turn off the public address system. That’s how we play the game in T-stan.”

Success at last!
Without the PA system, the hapless prisoners have no information other than the colours of the hats in front of them. Every one of them faces the same position as the first prisoner in the earlier game. The only option available is to simply guess.
With N colours, this gives a mere 1/N chance of success. If N is significantly bigger than the total number of prisoners, there is a decent chance that everybody dies.
A dismal end indeed for our highly ingenious prisoners.

The story should end here with, perhaps, a denunciation of capital punishment and wanton wardens, but the mathematician in me has one last question.

What if we play this game with infinitely many prisoners?

You may wonder how that could possibly help – after all, the situation is still the same, isn’t it?
Without any information on what others can see, how could anybody do better than just guess?
All I can say is “Have faith in Infinity and read on....”