0
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by Andrés E. Caicedo, mrs, JonMark Perry, Leucippus, hardmath Apr 18 '17 at 5:17

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ If it helps, the clearest way I've found to state the Axiom of Choice is "For any (possibly infinite) collection of non-empty sets: there exists a function (called the choice function) that maps each set to an element in that set." $\endgroup$ – WB-man Apr 17 '17 at 4:36
  • $\begingroup$ If possible, add the set-theory tag. It also has roots in the choice of axioms and set cardinality. $\endgroup$ – AspiringMathematician Apr 17 '17 at 5:25
  • $\begingroup$ It is burdensome to present Readers only with an external link to the problem you want help with, and then add only some remarks that "I don't see how you can solve this problem." Please review How to Ask and consider editing to include a full statement of the problem you want help with in the body of the Question itself. $\endgroup$ – hardmath Apr 18 '17 at 5:16
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ everything except the last sentence makes sense to me. However, the most important part is the last sentence. $\endgroup$ – wrek Apr 17 '17 at 4:33
  • $\begingroup$ @wrek Expanded answer to maybe clarify. $\endgroup$ – kholli Apr 17 '17 at 4:43
  • $\begingroup$ If the problem you're having is the fact that each has a $50\%$ chance of surviving (yet only finitely many die), my best advice is that probability simply does a poor job of modeling this scenario. $\endgroup$ – Fimpellizieri Apr 17 '17 at 4:43
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.