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/2k)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=log2n, we get that this probability is (1-1/n)n/log2n, which tends to 1/(e log2n), 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
On the assumption that p2(A) and p2(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 p2(A) nor p2(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 p2(A) and p2(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.