Abstract:

  We consider a hats game puzzle that has been making the rounds in the 
  mathematical, CS and coding communities, and has been the subject of 
  a recent article in the Science section of the NY Times. The game is 
  played by a team of n players, and(say) a TV host. After the team 
  enters the game room, the host places either a green hat or a red 
  hat on each player's head. Every player can see the other players' 
  hats, but not her own. Shortly after getting the hat, each player 
  has to declare "my hat is green", "my hat is red", or "I pass". 
  These declarations have to be simultaneous, and no communication is 
  allowed between the players after the game starts. They are allowed, 
  however, to coordinate their strategies beforehand. The team wins a 
  big prize if at least one player guesses his hat color right, and 
  none guesses it wrong. Otherwise, they lose. Assuming a uniform 
  distribution of hat combinations, a trivial strategy gives the team
  a 1/2 probability of winning. We will discuss how that probability 
  can be improved, what its limit is when n goes to infinity, the 
  convergence rate to that limit, and the close relationship of the 
  problem to coding theory. We will also discuss the desperate 
  measures the TV station, being on the brink of bankruptcy, took 
  to diminish the team's probability of success. These measures 
  included using an arbitrary distribution on the hat color 
  combinations, disallowing the use of coins by the players during the 
  game, and using an arbitrary number of hat colors. We will check how 
  teams fared under those conditions, and whether the TV station is 
  still in business.
  The talk will include a combination of known results, some history, 
  and also some presumed new results.
  
  Joint work with Hendrik Lenstra.