Infinite Prisoner Hat problem

Question

Infinite prisoners puzzle.

The question has been asked in this forum as well. However, I have spent half an hour trying to comprehend what the axiom of choice is. My understanding is that, you encode black hat with 0, red hat with 1, and then you remember a string of 01010101010......and you are trying to match what you see against what you memorize. .... but, I don't see how you can solve this problem.

Can anyone explains the solution to me in 15 years old human-understandable language? Something that's not so abstract. Thanks.

Answer 1

The way I always think of the axiom of choice is this: you have an (uncountably) infinite number of buckets filled with balls. From each bucket, you take exactly one ball. The ball represents that bucket in whatever you are trying to do. In this case, the balls represents a string of 0's and 1's, and they are in the same bucket if they all agree identically after so many (possibly huge) number of characters. So the prisoner's can see the hats in front of them, so they can pick the bucket that agrees with their observation. However, they don't know at what point the balls agree, they only have the one representative.

At this point, they know which bucket matches their observation. However, being in the bucket means that after some finite number of 0's and 1's, everything agrees. However, if we look at an example, say the following three strings

0011010101|000001111111.....

1100101010|000001111111......

1010000111|000001111111

There are $2^{10}=1024$ such strings, so until the bar, the prisoners are essentially guessing and have a 50/50 chance. They only got to pick one of the strings. It could possibly be the correct one where no one dies, or it could be the exact opposite where all 10 of the first people die, or anywhere in-between. However, from the 11th prisoner on, they know they will be correct.

Answer 2

The axiom of choice, broadly speaking, says that no matter what kind of collection you have, you can always pick one and only one element of each set in the collection.

It is intuitive in the case of finite collections. Suppose you have $n$ color-coded bags, each containing $m$ numbered balls, without repetition. Then from each bag you can take one ball from each and make a new set of representatives of each set.

Now for the countable collection. Suppose for each colored bag we also numbered them "up to infinity". The axiom of countable choice says that we can still pick one ball from each bag and make a new set.

And now comes the more abstract case, of uncountable collections. Drop the numbered bags; your bags are still color-coded, but you allow them to have any color. Literally, any; there's a bag for every visible wavelength you can come up with, to infinite precision (doesn't matter if the difference is discernible or not). The full axiom of choice says that there is still a way to pick one ball from each bag (but doesn't say how).

---

Back to the problem, you need to recognize that the number of possible sequences is uncountable-infinity.

From all those sequences, the prisoners need to sort them out. So, the $n$-th prisoner sort the possible sequences he can be with the following rule:

If from the $n$-th hat the sequence doesn't change anymore, they belong to the same class. That is, if the hats don't change beginning from my hat, they're into the same class.

That is, suppose you have $RGRGRGRGRG...$, $GGGGRGRGRG...$ and $RRRRRGRGRG...$. Notice that beginning from the 5th hat the sequence is the same, so they belong to the same class for the 5th prisoner. Of course, the first prisoners will have fewer and "larger" classes than the ones behind them.

The axiom of choice implies that from each class they can pick a representative. So, suppose they agreed on a representative for every single class. Note that, by fixing a sequence from each class, they're actually deciding which color they'll call their hat, based on the outcome of the people in front of him.

Let's line them up now. Note that the actual sequence they were put into is inside a class for every prisoner.

The first, well, has only one class with all sequences. Poor him, but he was really unlucky to be picked among infinite prisoners. He calls out the predetermined sequence and hopes for the best.

The second prisoner has seen what happened with the first one, and calls out his color based on that.

The third eliminates all classes that didn't match the new outcome, and calls out his choice for the 3rd.

And on and on and on.

Now, remember that every sequence was in a class, including the actual one? That means that after the $m$-th prisoner the actual sequence will be in all subsequent classes, however large $m$ might be. So at most only $m$ prisoners will die.

Note that if the $n$-th prisoner was the first one that called his color right, you can still have $m\neq n$, since the $n$-th representative might not be the actual sequence, or the $n$-th prisoner just really got lucky and chose the right color. But $m$ is certainly finite, because of how we constructed our classes.