| |
|
||
| |
|
|
Introduction
Every few weeks or so we'll put up a new puzzle. Some of them will be old classics, some of them will be new. Most will involve constructing an algorithm or a proof, while some will involve writing a computer program to solve them. After a few weeks or so we'll post a solution, along with proper references to the problem.
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!
Previous Puzzles with Solutions
Puzzle 15 -- Hat Problem
Puzzle 14 -- Restrooms and Solution (pdf)
Puzzle 13 --The Voting Problem and solution (pdf)
Puzzle 12 -- Level with me and solution (pdf)
Puzzle 11 -- Quarelling Quartets and solution (pdf)
Puzzle 10 -- Card Tricks and solution (pdf)
Puzzle 9 --Problems with ants and solution (pdf)
Puzzle 8 -- Here comes Santa (pdf) and solution (pdf)
Puzzle 7 --The Gridville Garbash problem and solution (pdf)
Puzzle 6 --Uniform Candy Distribution and solution (pdf)
Puzzle 5 -- Empty the Bucket
Puzzle 4 ---Vacancy and solution (pdf)
Puzzle 3 ---Take the last chip and solution (pdf)
Puzzle 2 --- Lights of the Round Table (pdf)
Puzzle 1 --- Managers and Engineers
Alan
Frieze,