SCHOOL OF COMPUTER SCIENCE

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!

  Solution

< back to the main puzzle page