Challenge 9: The Prisoner Line-Up

[Office_Shredder]

Countably infinite prisoners, numbered 1,2,3 etc. are told that tomorrow they will be given hats, colored either black or white, and lined up so that each prisoner can only see the prisoners whose hats are labeled with a greater number. The prisoners then get to guess which color hat they wear, in order from 1 onwards. If all but finitely many of them guess which color hat they have, the prisoners win and they are let free.

The challenge: Describe a strategy which let's the prisoners go free. Assume as with all such challenges that the prisoners can't communicate in secret once they get their hats, they can see infinitely far to all the prisoners that are supposed to be visible to them, they have perfect memory and are perfectly logical and all those other things that people can't do in real life.

Bonus points if you can create a strategy that places a specific upper bound on how many prisoners get their hat wrong.

 

[economicsnerd]

Let's assume a (somehow stronger) version of choice, say the axiom of collective choice, that for any set $\mathcal X$ of sets, the prisoners can agree on an element of $\prod_{X\in\mathcal X} X$. Hopefully that's not cheating.

Define a binary relation on $Z= \{b,w\}^\infty$ via $$\sim := \{(x,y)\in Z\times Z: \enspace x,y \text{ agree on cofinitely many entries} \}$$ which is easily seen to be an equivalence relation. By collective choice, the prisoners can agree on a function $f: Z\to Z$ such that
- Every $z\in Z$ satisfies $f(z)\sim z$.
- Every $z,y\in Z$ with $z\sim y$ satisfy $f(z)=f(y)$.

The guessing rule: If $z$ is the true hat sequence, prisoner $k$ guesses $f(z)_k$, which he knows, because he knows the $\sim$-class of $z$.

Because $f(z)\sim z$, only finitely many of the prisoners can be incorrect.

 

[Office_Shredder]

economicsnerd, your axiom of collective choice is just the axiom of choice plus one prisoner telling everyone what he chose so I'll allow it. That's a really nice solution. Any alternate or stronger solutions out there? (by stronger I mean limiting how many prisoners guess wrong).

 

[economicsnerd]

economicsnerd, your axiom of collective choice is just the axiom of choice plus one prisoner telling everyone what he chose...

True. I guess I was just worrying about being able to "tell" something with so much information in it.

 

[Boorglar]

Define the real number $a$ to be the number (between 0 and 1) whose binary expansion is represented by the sequence of hat colors (white = 0, black = 1). Assuming this is a computable number, then there exists an algorithm to compute it with arbitrary precision. This algorithm must be finite, so it can be encoded in a binary program of length n. The first n prisoners will say each bit in the program (using the convention that white = 0 and black = 1). Then all other prisoners will be able to run the algorithm in their heads up to the desired accuracy to predict their own hat color.

I see a few flaws in this solution, for example not all numbers are computable (but for all purposes, who could realistically generate such a number in the first place? :P ). Also, I am not sure whether it is possible to generate an algorithm to compute a computable number given only its decimal (binary) expansion. This would work well for rational numbers, or even algebraic numbers (by encoding the coefficients of the polynomial whose root we are looking for, and then using numerical methods such as Newton-Raphson, etc).

EDIT: speaking of that, I think there's something wrong or that I have misunderstood. The set of all sequences of ones and zeros is uncountable. But if there was a strategy that gave a finite upper bound N on the number of prisoners who must guess, then the set of all possible sequences generated by such a strategy must be countable, since it depends only on N bits, and so only 2^N such sequences are possible. Thus some sequences would not be described by such a strategy.

 

[Citan Uzuki]

As a matter of fact, it's possible for us to construct a strategy that guarantees that at most one prisoner will get his hat wrong. As in economicsnerd's solution, we start by having the prisoners agree on a choice function $f$ on the set of all infinite sequences. The first prisoner counts the number of positions $k\geq 2$ such that $f(z)_k \neq z_k$ - which will necessarily be a finite number - and then calls out "black" if this number is even and "white" if this number is odd. The second prisoner observes the number of $k\geq 3$ such that $f(z)_k \neq z_k$, and by comparing the parity he gets with that indicated by the first prisoner, determine whether $f(z)_2 = z_2$ and hence the color of his own hat, which he calls out. This gives the third prisoner enough information to deduce and call out the color of his hat, followed by the fourth, and so on. Hence every prisoner except possibly the first will correctly guess the color of his own hat with this strategy.

 

[mfb]

@Boorglar: The set of computable numbers is countable, so this strategy does not cover most cases.

With at most N guesses, you can distinguish more than 2^N cases - there is some freedom which prisoners decide to transmit information (instead of trying to get their own hat right based on the previous information). Doesn't change much, however.Is this possible without the axiom of choice? If not, I think Citan Uzuki found the perfect solution.

 

[Boorglar]

Yeah I just realized another (huge) flaw in my answer: the first prisonner might think of a number and come up with an algorithm. But the second prisoner will not see the same number, and he has no way to know which algorithm the 1st prisoner had in mind.

And also, mfb is right. The information that prisoner n obtains contains the hat colors for prisonners 1 to n-1. So each prisoner actually has more information than the previous.

 

[economicsnerd]

I think Citan Uzuki found the perfect solution.

Agreed! It's a very elegant solution.