CoCalc Public Fileswww / edu / fall05 / gsr / butler.html
Author: William A. Stein
TITLE: A hypercube approach to a hats guessing game

SPEAKER: Steven Butler

ABSTRACT: We will consider a hat guessing game.  This game is composed
of $n$ players who have one of $k$ different colored hats placed on
their heads they are allowed to see what other players are wearing,
but not their own hat.  They then must guess their own hat.  No
communication is allowed.  Before the hats are placed the players are
allowed to come up with a public strategy.  The goal of the strategy
is to maximize the guaranteed number of correct guesses.  We will show
that the best possible is the floor of n/k.

We will give a hyper-hypercube interpretation of the game which will
allow us to generate some balanced strategies in the 2-colored version
of the game.  We will also discuss the limited hats game and give a
bound for it by using the hyper-hypercube interpretation.