22
$\begingroup$

The problem is this (recently asked about here):

A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. The prisoners have a chance to meet and confer beforehand, but once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed?

The standard solution depends on the Axiom of Choice, as discussed in this previous question.

However, the previous question only explains that that particular strategy requires the Axiom of Choice. It still seems at least conceivable that there could be a completely different strategy that works and doesn't need Choice.

Thus: Is it known to be consistent with ZF that there is no strategy for the prisoners?

(Bonus question: If "yes", then is this also true in the variant where the prisoners can hear the answers of lower-numbered prisoners?)

$\endgroup$
0

1 Answer 1

Reset to default
10
$\begingroup$

After working out a little bit of math, I suddenly remembered that this was asked, in some variation, on MathOverflow. Thankfully, Nate Eldredge posted an answer to this question which had just the right reference.

Hardin, Christopher S.; Taylor, Alan D. An introduction to infinite hat problems. Math. Intelligencer 30 (2008), no. 4, 20–25. MR2501394.

In this paper the authors show that it is consistent with $\sf ZF+DC+BP$ (where $\sf BP$ is the axiom stating that every set of reals has the Baire property) that there is no winning strategy. Of course this theory is equiconsistent with $\sf ZFC$ (as shown by Shelah), and follows from $\sf AD$ as well it holds in Solovay's model.

Additional information can surely be found in their book (mentioned in the comments of Nate's answer by Francois Dorais), whose subtitle is "A study of generalized hat problems"

Christopher S. Hardin and Alan D. Taylor, The mathematics of coordinated inference, ISBN: 978-3-319-01332-9; 978-3-319-01333-6.

This might also seem interesting,

Hardin, Christopher S.; Taylor, Alan D. Minimal predictors in hat problems. Fund. Math. 208 (2010), no. 3, 273–285. MR2650985.

$\endgroup$
16
  • 4
    $\begingroup$ Incredible. That MO thread is just 5 weeks old. When I remembered it, it felt as if it is nearly a year old. I'd say that time flies when you do a lot. But I didn't do all that much in these five weeks! Where did time go? :( $\endgroup$
    – Asaf Karagila ♦
    Nov 21, 2014 at 23:26
  • $\begingroup$ Isn't time actually failing to fly in this case? $\endgroup$
    – Kevin Arlin
    Nov 21, 2014 at 23:29
  • $\begingroup$ @Kevin: Well, time is like a snail that can fly very fast sometimes, or crawl very slowly. So if it didn't fly, it had to crawl. But it didn't crawl. I don't remember doing anything in this past month, other than procrastinating writing the fine details of something new. In fact, I'm still procrastinating that! Just look at this comment! :-) $\endgroup$
    – Asaf Karagila ♦
    Nov 21, 2014 at 23:31
  • $\begingroup$ I'll take your word for it, since the papers are paywalled. $\endgroup$
    – hmakholm left over Monica
    Nov 22, 2014 at 0:05
  • 4
    $\begingroup$ Their book (or at least some draft version?) is available here (no paywall): qcpages.qc.cuny.edu/~rmiller/abstracts/Hardin-Taylor.pdf $\endgroup$
    – Hans Lundmark
    Nov 22, 2014 at 21:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .