|
There are many riddles that involve several players (we'll call their
number n), each wearing a hat that can be either black or white, and
each seeing all other players' hats but not their own, with the players trying
to devise a strategy that will allow them to optimise their guesses regarding
some information about the colour of their own hats. This riddle is a variation
over this theme. Credits for it will be given on the solution page.
The variation in our scenario is that each player does not just wear one hat, but, in fact, an infinite number of hats, all stacked one above the other in a tall tower. The players play a cooperative game in which all players, after having observed the hat colours of all other players, simultaneously choose one of their own hats. (You can think of this as the players "pointing" to one of their hats, or just calling out its number in the height ordering.) The players win the game if every one of the n hats chosen is white. (Note that this is also different from more standard versions of this problem, in which the players merely need to guess the colour.) The players can synchronise a common strategy, and each hat is either black or white with 50/50 probability, independent of the colours of all other hats. This month the riddle has two parts. Answer either or both.
Part 1:Describe a strategy for the n players that ensures a success probability proportional to 1/log n at least, for an asymptotically large n, or prove that none exists.Part 2:Describe a non-trivial upper bound on what the success rate of the optimal strategy is, for the case n=2. |
List of solvers:Part 1:Oren Zeitlin (8 July 04:11)Lin Jin (11 July 16:14) Yuping Luo (19 July 23:34) Uoti Urpala (30 July 06:57) Part 2:Lin Jin (11 July 16:14)Uoti Urpala (30 July 06:57) |
Elegant and original solutions can be submitted to the puzzlemaster at riddles
brand.scso.com.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.
The solution will be published at the end of the month.
Enjoy!