9
$\begingroup$

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?

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ That's the strategy I was thinking of. But it leads to survival only with probability 1/(N+1). We only have to consider rows that have either 0 or 1 white hat, because none of the prisoners will choose a row with 2 or more white hats. Among those rows, if the first one from the bottom has 1 white hat the prisoners die, if it has 0 white hats they live. The probability of 1 white hat is N times the probability of 0 white hats. Therefore survival with probability 1/(N+1). Still unsure whether that's the best strategy... $\endgroup$
    – Markus Meister
    Apr 10, 2018 at 2:18
  • $\begingroup$ @MarkusMeister Ah yes I see your point, edited post to correct this. $\endgroup$
    – S. Dewar
    Apr 10, 2018 at 2:29
  • $\begingroup$ 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. $\endgroup$
    – antkam
    Apr 10, 2018 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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