The Game of Hats

Lord Shamsay Snow, Warden of the North in the grim land of Pesteros delights in playing games with his prisoners. Especially games which end with said prisoners being skinned alive. Nothing enhances delight like holding out some hope of escape, then brutally extinguishing it.

Having rounded up a hundred of the miserable wretches, Shamsay announces:

“You will all play the Game of Hats – where you either go free or you die.”

The game will proceed as follows:

All prisoners will be lined up facing the dungeon wall.

Prisoner 100 stands right against the wall, prisoner 99 stands behind him and so on.

Shamsay’s trusty servant, Meek, will place a hat – which may be coloured Black or White – on their heads. Obviously they won’t know the colour of the hat. All they will see is the hats of everyone in front of them.

Now, starting from Prisoner 1, right at the back, Shamsay will ask each one of them the colour of the hat on their heads, one by one.
The only words they can say are “Black” or “White” – which they will shout out for everyone to hear.

Any other word or phrase leads to everyone being fed to the hounds. (This is what Shamsay is secretly hoping for….)

Now, if the word they shout out corresponds to the colour of their own hat, they go free. Otherwise, they are skinned alive. Such is the Game of Hats.

As the prisoners stare at him, hope and apprehension mingling in their eyes, Shamsay offers them a sporting chance – they have till next episode to figure out any way they can to save their sorry selves.

As the camera pans onto Shamsay’s leer and the credits start to roll, can you anticipate what follows? Will the next episode show a procession of prisoners hobbling off to freedom, or will carnage abound? Now may be a good time to go and think….

SPOILER ALERT !!!

At most one prisoner dies, all the rest go free.

How in Pesteros did that happen?

Well, due to the ingenuity of an extremely short prisoner of very high intelligence, who then insisted on standing right at the front of the line.

The solution involves “Arithmetic mod 2” which is much simpler than it sounds.

The basic idea is that every number is replaced by its remainder when divided by 2 - so every even number becomes 0, every odd number is 1.

This applies to negative numbers as well -  -2, -12, - 1000 are all 0, while -1, -25, -117 are all 1.

Now the cool thing is, you can add, subtract and multiply “mod 2” as well, hence “Arithmetic mod 2”.
All you need to do is add, subtract or multiply as you normally do, then divide by two and take the remainder.

To illustrate:

13 + 16 mod 2 = 29 mod 2 = 1

4 x 3 mod 2 = 12 mod 2 = 0

3 – 7 mod 2 = -4 mod 2 = 0

All clear? Good. Now on to the hats.

The strategy starts with assigning a number to each colour: Black = 0, White = 1.

Prisoner 1 adds up the numbers corresponding to the 99 hats he sees in front of him mod 2.

If he gets a 0, he shouts “Black”, if 1, then “White”.

Prisoner 2 does the same for the 98 hats in front of her, then subtracts what she gets from Prisoner 1’s answer. This gives her the colour of her hat and she shouts it out.

What about the rest, say Prisoner 17 ?

Well, prisoner 17 starts off by getting the total of the 83 hats in front of him. Call it X.
Then he hears Prisoner 1’s shout and gets the corresponding number. Call it Y.

Now as Prisoners 2 to 16 call out their colours, he subtracts 1 from Y every time he hears “White” and o when he hears “Black”.

By the time Shamsay gets to him, all the subtraction leaves him with some number, Z.

So “What is the colour of your hat ?”.

Calculate (X – Z ) mod 2. If 0, say “Black”, if 1, say “White”, and he is free !

Was that confusing? Okay, let me give an example with ten prisoners rather than a hundred.

Suppose, this is the sequence of hats on their heads, with prisoner 1 on extreme left and Prisoner 10 on extreme right (B is black, W is white).

B W W B B B B W W W

Now then, Prisoner 1 sees 4 black hats and 5 white hats.

So, following the procedure, he gets (4 x 0 + 5 x 1) mod 2 = 5 mod 2 = 1

Hence, he shouts out “White”. 

Alas, his own hat is black, so he dies, but this is the only casualty.

Prisoner 2 sees 4 black hats and 4 white hats.

So she gets (4 x 0 + 4 x 1) mod 2 = 4 mod 2 = 0

Subtracting from Prisoner 1’s answer gives 1 – 0 = 1, so she says “White”.

And notice that this is the colour of her hat!

Now let’s try it for Prisoner 5.

He sees, 2 black and 3 white hats, so X = (2 x 0 + 3 x 1) mod 2 = 1

Now he hears Prisoner 1, shout out “White”, so Y = 1.

As Prisoners 2 to 4 shout out their answers, he keeps subtracting accordingly.

Easy to verify that:  Z = 1 – 1 – 1 – 0 = -1

Now it’s his turn to answer.

Well, X – Z mod 2 = 1 – (-1) mod 2 = 2 mod 2 = 0. And “Black” it is! J

Note that the number of prisoners makes absolutely no difference.

Be it ten or a hundred or millions, everyone goes free except maybe Prisoner 1. And there’s a 50-50 chance that even he or she gets it right.

So what happens if Shamsay ups the ante by increasing the number of hat colours, to Black, White, Red and Green ?

Makes absolutely no difference.  At worst Prisoner 1 dies or they all go free.

If you followed the argument above, you will quickly see that the solution here  is to use “Arithmetic Modulo 4” where you take remainders by 4 rather than 2.

So, 13 + 16 = 29 mod 4 = 1,  8 -4 = 4 mod 4 = 0, 11 x 2 = 22 mod 4 = 2  etc.

To spell it out further, assign a number from 0 to 3 to each colour, say Black = 0, White = 1, Red = 2 and Green = 3. The strategy is exactly analogous, except you need to do the calculations using the four numbers corresponding to the four different colours and do all the arithmetic mod 4.

Exercise: With 10 prisoners, work out the procedure in detail for the hat sequence below:

B G R R W W B G R G

No matter how many prisoners or hat colours, the worst possible outcome is one death. Thanks to the power of modular arithmetic.

With his approval ratings plummeting wildly -  “At most one death per episode ? Yawn.” -  Lord Shamsay is in despair until he gets a note from a mysteriously named GRRM.

“Don’t let them shout out the answer, dammit ! Have them whisper it in your ear !”

Carnage ensues. With no shouted answer to guide them, each prisoner is reduced to making a guess. With two hat colours about half of them get it wrong, more colours make it worse.

There is much screaming and bloodshed, the fans are ecstatic and the show is destined to continue for many more seasons.

Analytical Interlude

Time to tune out the morbidity and engage in some dispassionate analysis.

If you think about the “shout version” of the game, you realize that in principle, the outcome is not too surprising.

Every prisoner knows the colour of the hats of the people in front, and shouting allows them to communicate information. Yes, it takes a lot of ingenuity to convey all that information in a single word, but ultimately it all boils down to each person getting to know the colour of their hat from the prisoner behind them in a suitably coded form.

It is, therefore, also reasonable that  Prisoner 1 is at risk – after all, there is no one behind him to tell him his colour.

The “whisper version” of the game destroys the information channel and each person must now figure out their hat colour based only on the hats in front of them.

Is this always impossible? Not necessarily.

For instance, if Shamsay put black hats on everyone, or an alternating sequence of black and white hats, then it’s quite possible that prisoners may figure out the pattern. But all hope is lost if he assigns the colours randomly, say by tossing a coin each time.

Surely, if the hat colours are chosen randomly, then it is impossible to figure out the colour of your own hat from the ones in front ? Surely, in such a case, half the prisoners must guess their colour wrong on average ?

In a finite world, yes.

But what if we throw infinity into the mix?

The Infinite Game

In a strange dimension unimaginably distant from Pesteros, yet all too near, R’Holler, the Lord of Might has an infinity of demons at his command.

His command is to play the Game of Hats. (Why ? Do not question the will of R’Holler, puny mortal !)

The rules are the same. Hats are either black or white.

Demon 1 stands behind Demon 2, who stands behind Demon 3 and so on forever.

(Math Alert: This implies that the infinity of demons is a countable infinity.)

All too aware of Shamsay’s initial discomfiture in the mortal realm, R’Holler goes straight for the “whisper version” of the game.

Oh yes, punishments. The penalty for guessing the wrong hat colour is the worst fate imaginable – being born as a commoner in Pesteros.

Based on our analysis above, since this is the whisper version, each demon has  a 50% chance of getting their colour wrong. So, is Pesteros headed for a population explosion of literally infinite proportions?

In fact, even if the demons work out some intricate statistical strategy so that the chance of a wrong answer is 1% or 0.0001%, any fraction of infinity is infinity and Pesteros is doomed.

So, what if I tell you that:

There exists a strategy to ensure that only a finite number of demons get their hat colour wrong – ie, the proportion of demons getting it wrong can be made precisely zero.

All without any communication whatsoever between the demons during the game.

How in the seven heavens and hells ???

This will take a bit of explanation.

Strings and Grouping

Consider any arrangement of black and white hats chosen by R’Holler.

This would correspond to an infinite sequence of the letters B and W.

We will call such a sequence a “string”.

We will call two strings “finitely different” if their values differ in finitely many locations and “infinitely different” otherwise.

To illustrate, consider the four strings below.

S1: B B B B B B B B ..… all black

S2: BWWWBWWB…all black henceforth

S3: BWBWBWBW…alternating B and W

S4: BBBWWWBW…alternating B and W henceforth

You can verify that S1 and S2 are finitely different, as are S3 and S4. However, S1 is infinitely different from both S3 and S4.

To start things off, here’s an Easy Result:

If S1 is finitely different from S2 and S2 is finitely different from S3, then S1 is finitely different from S3.

Quick Proof: Suppose S1 differs from S2 at n different locations and S3 differs from S2 at k different locations. 
Then S1 and S2 differ at at most  k + n different locations.

Now, I am going to break up the set of all possible strings into groups as follows.

Pick any string (the string which is all B for instance), call it S1. Make a group consisting of all strings which are finitely different from S1.

Anything string left over? If so, call it S2. Make another group consisting of all strings which are finitely different from S2.

Anything string left over? If so, call it S3. Make a group…..you get the idea.

We keep repeating this again and again until all possible strings belong to some group or another.

Observe two facts about this grouping:

Fact 1: Every possible string belongs to some group.

Fact 2: No string belongs to two different groups.

How come Fact 2?

Okay, suppose a string S belongs to two different groups, say group of S1 and group of S2. This means S is finitely different from S1 and S2 is finitely different from S.

But then the Easy result we just proved implies that S2 is finitely different from S1.

But then S2 and S1 should be in the same group, which isn’t true. QED.

(My mathematician friends will realize that I am partitioning the set of strings into equivalence classes, but enough of that.)

Fact 1 and Fact 2 taken together can be combined to give us:

Big Fact: If the set of all possible strings is partitioned into groups whose members are all finitely different from each other, then every string will belong to exactly one of these groups.

Winning the Infinite Game

For what follows, we shall assume that all demons have infinitely good vision, infinite memory and infinite computing power.

Any objections ? None ? Very well then…

As a first step, the demons combine their infinite computing power to split the set of all possible strings into groups of finitely different strings as above.

The next step is to form a Representative Set, R, consisting of exactly one string from each group. (Each string in the set ‘represents’ its group, hence the name.)

At the third step, the infinite memory comes in handy – the demons simply memorize all the strings in the Representative Set.

(Note: Infinitely many different Representative Sets can be formed. The demons come to a consensus about which one to use before memorizing it.)

Now the demons line up as commanded and the Lord of Might places the hats.

With their infinitely good vision, each demon can see all the hats in front of them.

Theorem:

There will be a unique string, S*, in the Representative Set, R, which is finitely different from the string of hats on the demons’ heads.

Furthermore, each demon can identify S* simply by looking at the hats in front of it.

Proof: Let S represent the string of hats.

By the Big Fact stated above, S belongs to exactly one group of finitely different strings.

R consists of exactly one string from each such group.

So, S* will be the string in R which belongs to the group where S lies.

Given how the groups were formed, S and S* will be finitely different.

Consider Demon 17, say.

It can see all but the first 17 entries of S. (The 17 missing entries being the hat on its own head and the ones behind.)

Demon 17 simply goes through each string in R, picks out all but the first 17 letters and compares the result with what it sees. (Infinite computation power, remember?)

Now, suppose a string in R differs from S at infinitely many locations.

Removing 17 letters will reduce the number of different locations by at most 17 – ie, the truncated strings will still be infinitely different.

Conversely, if a string in R is only finitely different from S then, after truncation, the number of differences will either stay the same or decrease – ie, the truncated strings will be finitely different.

From what we stated above, only S* is finitely different from S and everything else in R is infinitely different. Hence, Demon 17 can identify S* because only the truncated version of S* will be finitely different from the string of hats it can see.

Clearly, the argument above applies to Demon 1, Demon 113274 or any demon in the line.

QED

So, finally we have it.

The hats are placed, the demons see what’s in front of them, and all of them identify S*.

When the questioning begins, Demon 1 whispers the first colour in the string S*, Demon 2 whispers the second colour and so on.

Since S* differs from the actual string S in finitely many places, all but finitely many of them get their hat colour correct.

To really see how surprising this is, imagine R’Holler walking down the line hearing the answers.

Initially, there are some mistakes, but at some point he passes the last location where S and S* differ, and from then on every single demon gets its hat colour correct !!!

In fact, if you think about it, it doesn’t matter if the Lord of Might walks down the line from back to front. He can question them in any order and the result is the same !!!

If you think a bit more, you will see that the same strategy works for any number of hat colours with exactly the same result !!!

In fact, even with infinitely many different hat colours, you get the same result !!!!

If that didn’t get an exclamation from you, I don’t know what will !!!!!

In Conclusion

Did the infinite game bother you ? It ought to.

In the finite version of the game played by Shamsay, blocking the information flow between prisoners by changing from “shout” to “whisper” led to a devastating change of outcome.

In the infinite version, the lack of communication matters not at all – in terms of proportions, precisely 0% of players guess wrong.

Maybe we can figure out the secret by trying to apply the winning strategy to a finite game with, say, 100 prisoners.

Very well then, we start off with strings of B and W of length 100.
Now we lump them into groups of finitely different strings.

Result: Since the strings are all finitely long, any two strings are finitely different, so the entire set forms a single group !

But let’s go on.

Since there’s only one group, the representative set, R, consists of just one string.

Basically, all the prisoners agree on one string and memorize it.

Now they are standing in line. What next ?
Well, there’s no problem of “recognizing S*”, since there is only one S* in the set R

And the strategy ? When Shamsay comes up, simply recite the letter of S* corresponding to your location.

Does the strategy work ? Yes it does !!
You see, if they are very lucky, the string of hats on their heads is exactly S*, whereby everyone is right.

Or it could be that only one person gets it wrong. Or all hundred. Or any number in between.

In every single case above, only finitely many people get their hat colour wrong, which is precisely what the strategy promised to achieve.

So there you have it. A strategy which worked with almost magical power for infinitely many players is totally ineffective, even ridiculous, in the finite world.

Which brings me to a point I have often made about infinity.

Most people imagine infinity by starting with something very big, then making it bigger and bigger and bigger and then it becomes, you know, infinite.

But when you think carefully, the world of the infinite reveals completely peculiar features with absolutely no finite analogue.

Infinity is infinitely weirder than you think.