Gadiel Seroussi, Hewlett-Packard Laboratories
On hats and other covers
We study a game puzzle that has enjoyed recent popularity among mathematicians, computer scientists, coding theorists and even the mass press. In the game, n players are fitted with randomly assigned colored hats. Individual players can see their teammates' hat colors, but not their own. Based on this information, and without any further communication, each player must attempt to guess his hat color, or pass. The team wins a big prize if there is at least one correct guess, and no incorrect ones. Otherwise, it loses. Assuming a uniform distribution of hat combinations, a trivial strategy gives the team a 50% 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 some presumed new results. (Joint work with Hendrik Lenstra.)