  A puzzle about prisoners trying to identify the color of a hat on their head
leads to a version where there are k more hats than prisoners. This generalized
puzzle is related to the independence number of the arrangement graph A(m, n)
and to Steiner systems and other designs. A natural conjecture is that perfect
hat-guessing strategies exist in all cases, where "perfect" means that the
success probability is 1/(k+1). This is true when k = 1, but we show that it is
false when k = 2. Further, we present a strategy with success rate at least
1/O(k log k), independent of the number of prisoners.
