Prisoners in hats

Situations about people wearing hats is a common occurence in puzzles. One of my favourite puzzles is one of these.

A prison has just recieved $n$ new prisoners, $n\geq 2$. Unfortunately the prison is full. The solution the prison comes up with is to make the prisoners play a game. Any who win are set free and any who lose are executed.

The game is as follows. The $n$ prisoners stand in a line and are each given a hat to wear. The hat is either blue or red for each prisoner. The prisoner at the back of the line can see all the hats in front of him and the person next in line can see all the hats in front of him except for the hat of prisoner at the back and so on.

The executioner then walks into the room. He asks the man at the back what colour hat he is wearing. If he guesses correctly he lives. Otherwise he is executed. Before the prisoners went into the room and put on the hats they agreed on a strategy to maximise the number of prisoners going free.

What was that strategy? (at most one prisoner dies with this strategy!)

SOLUTION

The way I thought of the solution was to imagine a way in which the person at the back could give enough information about the sequence so that every other prisoner could then know what there hat was.

Imagine if the prisoner at the back was allowed to say "I can see an even number of blue hats". Prisoner number 2 would then look in front of him. If he could see an even number of blue hats he would know that he was wearing a red hat. But if he could see an odd number of blue hats then he would know that he is wearing a blue hat. Prisoner number 3 then looks in front of him and counts the number of blue hats. He then adds to that the number of blue hats he has heard people say behind him. If this total is even he says red and if odd he says blue. This repeats for all prisoners. All prisoners survive about from the first one who dies half of the time.

Now the problem is how the prisoner at the back signals whether he can see an even or odd number of blue hats. He acomplishes this by saying red if he can see an even number of blue hats and saying blue if he can see an odd number of blue hats. (This in fact allows everyone to just pretend that there is an even number of blue hats in the sequence)

THE INFINTE CASE

Thats the problem solved for a finite number of prisoners. But lets suppose that a countbaly infinite number of prisoners turn up. Assuming that the prison warden doesnt know about Hilberts hotel then he cannot accomodate them. So he once again makes the prisoners play this game.

This time the prisoners come up with a strategy so that only a finite number of them die. What is it?

SOLUTION

This is where things start to get difficult and knowledge of some more complicated maths is assumed.

 Instead of red and blue let the hats labels be 0 and 1. Let $X$ be the set of all possible sequences. We then add an equivalence relation onto the set of all possible sequences. We say that two sequence $(x_{n})$ and $(y_{n})$ are equivalent if the set $\{n| x_{n}-y_{n}\neq 0\}$ is finite. In other words two sets are equivalent if they only differ in a finite number of terms. This forms an equivalence relation on $X$ which we denote as $R.$

We then consider $X/R.$ For each equvalence class $V\in X/R$ we choose $x\in V.$ Let $S$ be the set of all of our $x.$ We can choose such a set by assuming the axiom of choice. $S$ is known as our strategy. Note that no two elements in $S$ are equivalent and if $x\in X$ then there exists $s\in S$ such that $x\sim s.$

One more observation before the solution. If I take a sequence and change only finitely many terms then it will still be equivalent to the original sequence.

Now the solution. Let $x=(x_{n})$ be the sequence of hats placed on the prisoners.  Prisoner 1 looks in front of him. He consider the sequence $(0,x_{2},x_{3},x_{4},x_{5},...).$ He then picks the element $s\in S$ such that $s\sim x$ and say $s_{1}.$ Prisoner 2 considers the sequence $(0,0,x_{3},x_{4},x_{5},...)$ and picks the element from $S$ equivalent to this sequence. This will once again be $s$. Prisoner 2 says $s_{2}.$

This continues for all prisoners and the sequence the prisoners answers will form will be $s$. And since $s\sim x$ only a finite number of prisoners will die. Thus completing the problem.

A BETTER SOLUTION

I talked about these problems at a talk I gave to fellow post graduates this week. More on these puzzles can be found on the wikipedia page here.

After giving the talk I then thought "Hang on. Can't we just combine both the finite and infinite case so that only one person dies?"

It turns out that you can. Almost anyway. At most 2 people will die with strategy I now outline.

Consider the $n^{th}$ prisoner. That prisoner picks $s$ as above. If $s_{k}=x_{k}$ for all $k>n$ then we say that the prisoner is in state 1. Other wise he is in state 2.

If a prisoner number $n$ is in state 1 then he says $s_{n}$.

Now we come to prisoners in the second state. We note that a prisoner can not only say what state he is in but he knows what state every prisoner in fron of him is in. We also note that after a while all prisoners will be in state 1. There is therefore an $N$ such that prisoner $N$ is in state 2 and all other prisoners in front of him are of state 1.

If a prisoner is in state 2 then he plays the finite games with all the prinsoner upto and including prisoner number $N+1$.

The only prisoner who have a chance of dying are prisoners numbers 1 and $N+1.$

If anyone can see any mistakes are slight corrections with the above argument then please let me know.

BADGERS!