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” –

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 !!!

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.

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.

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.*

**Let S represent the string of hats.**

*Proof:*
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.

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

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.

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.