Log In

Infinite prisoners and hats

Posted on: August 30th, 2013 by

Suppose there are infinite prisoners. Each prisoner wears a red or a blue hat. Every prisoner can see every other prisoner's hats. No prisoners know their hat color. Each prisoner can either attempt to guess his hat color or abstain from guessing. However, in order for the prisoners to succeed, an infinite number of prisoners should make a guess and all the prisoners who guess should guess their hat color right. Can the prisoners come up with a strategy that will enable them to succeed with a probability of at least 0.5?

- via Quora

2 Responses to Infinite prisoners and hats

  1. Lizard had this to say about that:

    I think this is possible even if all prisoners are required to guess.

  2. Lizard had this to say about that:

    For two global hat assignments X and Y, we'll say that X ~ Y if X and Y assign different hat colors only to finitely many prisoners. This ~ is an equivalence relation.

    Before the game, the prisoners agree on a representative hat assignment from each equivalence class and agree on a parity (odd or even) by flipping a coin.

    Upon seeing each other's hats, they can identify the actual assignment's equivalence class and count the differences between the actual assignment and the agreed-upon representative from its class; these assignments will differ on a finite number of prisoners.

    Each prisoner guesses his hat color by assuming that the total number of differences has the agreed-upon parity. E.g. if the coin toss said "even" but I see an odd number of differences, then my hat must also differ from the representative assignment.

    With this strategy, either everyone is right or everyone is wrong, depending on whether the randomly-chosen parity is correct.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}