The game described in the riddle was invented by Lionel Levine in 2010. The solution to Part 1 was originally derived by Peter Winkler. The two-player variation that is the subject of Part 2 was first proposed by Tanya Khovanova, and the solution to Part 2 is due to Noga Alon. The best known strategy of the two-player game succeeds with probability 0.35. It was derived by Chris Freiling, who improved on a previous bound of 0.349 obtained by Uri Zwick. Both bounds are still closer to the semi-trivial strategy of choosing the number of the other player's lowest white hat than they are to the best known upper bound that is discussed in Part 2. A review of the present state of the art about this problem (as of March 2016) was written up by Jonathan Kariv, Clint van Alten and Dmytro Yeroshkin, and can be found here. This write-up also includes new extended results.

Let us consider the success probability of this strategy.

First, the strategy may fail because one or more of the players do not have
*any* white hats within their first *k*. This happens with
probability 1-(1-1/2^{k})^{n}.

If this is not the case, this induces some distribution on the sum of the
lowest-numbered white-hat positions modulo *k*. Regardless of what this
distribution is, at least one residue class will have probability of at least
1/*k*, so we can always choose *L* to be this residue class.

The probability for success is therefore bounded from below by

Choosing to set *k*=log_{2}*n*, we get that this probability
is (1-1/*n*)^{n}/log_{2}*n*, which tends to
1/(e log_{2}*n*), an expression that satisfies the desired
condition to solve the riddle.

First, for convenience, let us consider our towers of hats as subsets of
the integers: the subset for player *i* will include the ordinal positions
of all white hats on player *i*'s head.

In this formulation, an instance of the game can be denoted by a tuple,
(*A*,*B*), where *A* indicates the white hats on the first
player's head and *B* those on the second player.

Let us take all instances and join them up according to the
following rule: for any *A* and *B*, we will group together

- (
*A*,*B*) - (
*A*,*B*⊕ {p_{2}(*A*)}) - (
*A*,*B*⊕ {p_{2}(*A*)}) - (
*A*,*B*⊕ {p_{2}(*A*), p_{2}(*A*)}) - (
*A*,*B*) - (
*A*,*B*⊕ {p_{2}(*A*)}) - (
*A*,*B*⊕ {p_{2}(*A*)}) - (
*A*,*B*⊕ {p_{2}(*A*), p_{2}(*A*)})

On the assumption that p_{2}(*A*) and
p_{2}(*A*)
are distinct,
let us use the naming convention in which *B*, in the set of 8
representatives above, is the set that contains neither p_{2}(*A*)
nor p_{2}(*A*).
In this case, player 2 will make the correct guess in 4 of the 8 cases, namely
in cases number 2, 4, 7 and 8. However, because in cases 4 and 8 player 1
sees the same tower of hats on player 2, player 1 will make the same choice in
both cases, so, given that his own two towers in the two cases are
complementary, it will only succeed in 1 of the 2. Therefore, it is not
possible to win in more than 3 out of every 8 cases, or, in other words, with
probability 3/8.

Readers are encouraged to ascertain that in the case not handled here, namely
if p_{2}(*A*) and
p_{2}(*A*)
are identical, the choices of the two players are independent within the set,
so their success probability is bounded by the lower value 1/4 rather than
by 3/8.

NB -- Readers wishing for a more rigorous proof will need to perform the "grouping together" process more carefully than was done here, in order to avoid building statistics on groups of measure zero. I have decided to gloss over such technicalities here.