Prisoners

Solution

The best possible strategy is a strategy that guarantees success. Label the prisoners as \[ 0,1,2,\dots,99. \] Also reinterpret the hat numbers \(1,2,\dots,100\) modulo \(100\), where we treat \[ 100 \equiv 0 \pmod{100}. \] So every hat number is now one of the residues \[ 0,1,2,\dots,99. \] Now fix the following rule in advance: Prisoner \(i\) will guess the unique number that makes the total sum of all \(100\) hat numbers congruent to \(i \pmod{100}\). Suppose prisoner \(i\) sees the other \(99\) hats, and their sum is \[ S_i \pmod{100}. \] Then prisoner \(i\) guesses the number \[ g_i \equiv i - S_i \pmod{100}. \] In ordinary hat labels, if \(g_i \equiv 0 \pmod{100}\), he guesses \(100\); otherwise he guesses the number \(g_i\). Why does this work? Let the actual total sum of all \(100\) hat numbers be \[ T \pmod{100}. \] There is exactly one prisoner whose label is \(T\), namely prisoner \(T\). That prisoner guesses his own number correctly, because he sees the other hats summing to \[ T - h_T \pmod{100}, \] where \(h_T\) is his actual hat number. So his rule tells him to guess \[ g_T \equiv T - (T - h_T) \equiv h_T \pmod{100}. \] So prisoner \(T\) is correct. For every other prisoner \(i \neq T\), his guess is the number that would make the total sum equal to \(i\), not to the true total \(T\), so he is wrong. Thus exactly one prisoner guesses correctly. Since the rule of the game only requires that at least one person be correct, everyone escapes.