Consider the following game: there are N players standing in a row, each with a tower of countably infinitely many red or blue hats on top of their heads. The probability of any hat being red is 1/2 and likewise for any hat being blue, and the colors of the hats are jointly independent. Each player can see all of the hats on the heads of everyone other than themselves but they can’t see any of their own hats.
To win the game, the players must all simultaneously guess a natural number (the number can be different for different players) and ensure that all of the hats on their own heads in the position they named from the bottom of the tower are red. For example, if three players are in the game and their guesses are 1,5,13, then they win if the first hat from the bottom on player 1′s head, the fifth hat from the bottom on player 2′s head and the thirteenth hat from the bottom on player 3′s head are all red. If even one of them is blue, then they lose.
The players can all agree on a strategy to execute as a group beforehand, but can’t communicate with each other once the game begins.
Prove that there is a strategy with which the players can win with probability Θ(1/logN).
Consider the following game: there are N players standing in a row, each with a tower of countably infinitely many red or blue hats on top of their heads. The probability of any hat being red is 1/2 and likewise for any hat being blue, and the colors of the hats are jointly independent. Each player can see all of the hats on the heads of everyone other than themselves but they can’t see any of their own hats.
To win the game, the players must all simultaneously guess a natural number (the number can be different for different players) and ensure that all of the hats on their own heads in the position they named from the bottom of the tower are red. For example, if three players are in the game and their guesses are 1,5,13, then they win if the first hat from the bottom on player 1′s head, the fifth hat from the bottom on player 2′s head and the thirteenth hat from the bottom on player 3′s head are all red. If even one of them is blue, then they lose.
The players can all agree on a strategy to execute as a group beforehand, but can’t communicate with each other once the game begins.
Prove that there is a strategy with which the players can win with probability Θ(1/logN).