# Prisoners wearing infinite stack of hats

There are N prisoners, each wearing an infinite stack of hats. Each hat was chosen at random to be black or white. Each prisoner can see all the others but not her own stack. Each prisoner must independently write down the index of a black hat in her own stack. The warden checks all the guesses, and if one or more are wrong the prisoners are killed.

The day before, the prisoners were told the rules and allowed to agree on a strategy they would follow for guessing. What strategy should they adopt and what is the probability that they will survive?

I have an ad hoc strategy that promises survival with probability 1/(N+1). Can one do better or prove that this is optimal?

• It would greatly improve your post to include the "ad hoc strategy" that you found, esp. if you invite proofs of optimality etc. – hardmath Apr 10 '18 at 5:07
• Already for N=2, this problem seems to be very challenging. – jan1892 Apr 14 '18 at 16:39
• When you say "write down", does this imply that the other prisons cannot hear each others guess? – Chris Jan 29 at 17:22

We have the prisoners agree to pick the lowest number such that all the hats they can see are black. Since the hats are chosen randomly the probability such a possibility never crops up is $0$ so shouldn't effect the end probability.
• I understand the (brilliant!) solution, including the math, but this still feels like magic to me. :) From each prisoner's perspective, Prob(pick white) = 1/2. And yet, instead of an abyssmally low chance of success of $\frac{1}{2^N}$ if they were to pick randomly, this method raises the chance of success to 1/(N+1). I.e. somehow this makes the choices highly correlated. BTW I have tried variants like each person picks the SECOND row where she sees all black hats, or consider pairs of rows, etc., but everything I tried is provably worse. – antkam Apr 10 '18 at 23:24