Too Many Hats

Rob Pratt, Stan Wagon, Michael Wiener, Piotr Zielinski

Published 2018-10-18Version 1

A puzzle about prisoners trying to identify the color of a hat on their head leads to a version that is related to the independence number of the arrangement graph A(m,n), to linear fractional transformations in finite fields, and to Steiner systems. We present several results, the main ones counterexamples to the natural conjecture that perfect hat-guessing strategies (success probability 1/(k+1), where k is the number of extra hats) exist in all cases and the existence of a strategy with success rate at least 1/(e k^2), independent of the number of prisoners.