Puzzle 15: Hat Problems |

Here are some problems with hats. The scenarios are all very similar.
At the start there are *n* people wearing hats.

**Problem 1** Each hat is black or white. The people are standing
in line. Person *i* can only see which types of hat persons 1,2,...,*i-*1
are wearing. The inquisitor starts with person *n* and goes down
the line,* n*,*n*-1,...,1 asking each person in turn what sort
of hat they are wearing. Each person hears all the previous answers to
the question but nothing more i.e. he/she does not hear directly whether
a previous answer was correct. A wrong answer leads to elimination, which
is painful and is to be avoided at all costs. The *n* people can
decide on a strategy before the inquisition begins. Devise a strategy
that will lead to as few eliminations as possible.

**Problem 2** Now our *n* hat wearing friends are standing in
a circle and so everyone can see everybody else's hat. The hats have been
assigned randomly and each allocation of hat colors is equally likely.
At a certain moment in time each person must simultaneously shout "my
hat is black'' or "my hat is whie'' or "I haven't a clue''.
The team wins a big prize if at least one person gets the color of his
hat right and no one gets it wrong (saying "I haven't a clue'' is
not getting it wrong). Of course, if anyone gets it wrong, the whole team
is eliminated and this is painful. The prize is big enough to risk the
pain and so devise a strategy which gives a good chance of success.

Try the same problem assuming there a *q* colors for the hats.

**Problem 3** Our *n* hat wearing friends are again in a circle
but this time the hats have been placed on their heads by Agar the Adversary
who would like nothing better than to eliminate the lot of them. The hat
wearers are allowed to think and there is a clock and after each minute
passes, anybody is allowed to shout out what sort of hat they are wearing.
Time is up after *n* minutes and anyone who hasn't declared will
be eliminated. Also, if anyone declares wrongly, the whole group will
be eliminated. Can they survive with any certainty?

Now consider the same situation where someone rushes into the room and truthfully shouts "there is someone wearing a black hat'' or "you are all wearing white hats'' before Agar can silence him. How does this help?

**Aside:** Perhaps you know some similar problems that you can share
with us!