2

The problem is from Infinite prisoners with hats -- is choice really needed?

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?

There's no strategy that guarantees $<N$ prisoners are killed, because we can imagine an outsider coming in before the game starts, and asking prisoner $N$ what they would guess, then changing their hat to the opposite color. Then do the same for prisoner $N-1$, and so on. This way the outsider guarantees the first $N$ prisoners dies.

This trick works because changing hats of prisoners $1$ to $N-1$ does not affect $N$. But now change the question so that every prisoner can see every other prisoner. The original strategy that guarantees only finitely many prisoners die still works, but now, is it possible to guarantee $< N$ prisoners would die, for some finite number $N$? (The prisoners still can't hear what others say.)

MaudPieTheRocktorate
  • 3,796
  • 16
  • 34
  • I believe the answer is no, you still can't set a maximum, and it comes with a similar proof to the infinite Ramsey's theorem. Pick one prisoner and call him $0$. Clearly he might die because we can switch his hat and he sees nothing different. Ask all the other prisoners what their choices would be for prisoner $0$ having a red hat and for prisoner $0$ having a blue hat. – Ross Millikan Mar 04 '18 at 05:37
  • Only finitely many of them can change their minds based on prisoner $0$ because if infinitely many do there will be one choice of prisoner $0$ hat that causes infinitely many prisoners to be killed. Pick one of the people who doesn't change his mind, call him prisoner $1$, and make his hat the color he doesn't guess. Now ask everybody how they react to the four possible color pairs of prisoners $0$ and $1$. Again infinitely many cannot change their minds, so pick prisoner $2$ out of that group. – Ross Millikan Mar 04 '18 at 05:37
  • The gaping hole is that prisoner $0$ might react to the change of prisoner $1$s hat color. I believe that prisoner $0$ can only react to finitely many hats, which will rescue the argument, but can't get there. – Ross Millikan Mar 04 '18 at 05:37

1 Answers1

1

This is not possible.

Imagine again our outsider arbitrarily choosing $2N$ prisoners. The outsider can ask these prisoners what their guesses will be for each of the $2^{2N}$ ways the hats can be assigned to those prisoners (leaving the hats of the unchosen prisoners unchanged).

Each chosen prisoner will die in half of the assignments (choosing wrong in one of a pair in which the other hats are fixed), so there are $2N\cdot2^{2N-1}$ total deaths among all hat assignments. By the pigeonhole principle, then, there must be at least one assignment with at least $\lceil2N\cdot2^{2N-1}/2^{2N}\rceil = N$ deaths.

(Equivalently, the expected number of deaths is $N$, so there must be at least one assignment with at least $N$ deaths.)

tehtmi
  • 1,063