Logic Puzzles vs. Hat Problem
Steamboat Steven gave me this gem. Unlike my previous discussion of a hat problem, this one can be solved in a reasonably short amount of time.
There are n people on a staircase facing downstairs when a hat is placed on each person's head. There are c different hat colors, and each hat has a 1/c chance of being each color (that is to say, the color of each hat is independent; some of the c colors might not be used anywhere, while others may be very common). Each person can see the color of every hat downstairs from her, but not the color of her own hat or any hat upstairs. Starting at the top of the stairs and working down to the bottom, each person guesses the color of her own hat. Each person can hear all previous guesses.
The group as a whole gets 1 point for every correct guess, and nothing for incorrect guesses. If the group is allowed to discuss and to agree upon a strategy ahead of time, how many correct guesses can they guarantee?
One naïve strategy would be to have people 1, 3, 5, &c simply say the color of the hat in front of them, and have people 2, 4, 6, &c repeat that color, guaranteeing n/2 correct guesses. It turns out you can do a lot better. How?
There are n people on a staircase facing downstairs when a hat is placed on each person's head. There are c different hat colors, and each hat has a 1/c chance of being each color (that is to say, the color of each hat is independent; some of the c colors might not be used anywhere, while others may be very common). Each person can see the color of every hat downstairs from her, but not the color of her own hat or any hat upstairs. Starting at the top of the stairs and working down to the bottom, each person guesses the color of her own hat. Each person can hear all previous guesses.
The group as a whole gets 1 point for every correct guess, and nothing for incorrect guesses. If the group is allowed to discuss and to agree upon a strategy ahead of time, how many correct guesses can they guarantee?
One naïve strategy would be to have people 1, 3, 5, &c simply say the color of the hat in front of them, and have people 2, 4, 6, &c repeat that color, guaranteeing n/2 correct guesses. It turns out you can do a lot better. How?