In: Advanced Math
A terrible despot governing one small country decided to
check
how smart are people living in his country. He gathered 20 smartest
people
and put hats on their heads. Everybody could see all hats except
their own.
Then the despot said: "Some of the hats have a red stripe on them.
I will
give you one minute to think and then ask who has a red stripe on
their
hat? If nobody answers, then I will give one more minute and ask
the same
question again. I will repeat it 100 times. If you guess somehow
that you got
stripe on the hat you have to wait till I ask my question and say
immediately
about that, because after somebody will gure out correctly that he
or she
has a stripe on the hat, I will kill everybody else who has the
stripe and did
not gure it out. If you say that you have a stripe and you don't ,
I will kill
you. " They know that each of them is really good at deduction (got
A for
Math 311W when they were in college) and nobody wants to die.
a) Prove that if 2 people have red stripes on their hats, then
after the terrible
despot will ask them second time all of them will say that they
have them,
and despot won't be able to kill anybody.
b) What happens if three people have stripes?
Both parts are done in a similar way, so I will describe them together. Let us assume for starters, that only one person had a stripe on his/her hat. In that case that person can't see stripe on anyone else's hat. But when the despot says that there is at least one person with a stripe on his hat, the person with a stripe can easily conclude that it his/her own hat that has the stripe and will announce immediately after the first time.
Now we go to the case when two people have stripes on their hat. Let those person be called A and B. A can see only one other person with striped hat(that is B). From A's point of view there are two cases, his hat is striped or it not striped. If his hat is not striped then there is only person with a hat on his head. Therefore from the previous discussion that person will announce that he/she has a striped hat immediately after the first question. But since B has the same observations he will not announce that he has striped hat after the question. Therefore A can conclude that B is seeing one more striped hat and hence was not able to conclude that he himself has a striped hat. Since no other person has a striped hat it means that A can conclude that he has striped hat and will announce the fact after the second question. B making the same observations will conclude the same thing and will announce he has a striped hat.
In the case three striped hats, following the same line of argument, all three will see people with two striped hats. From the previous para, those people will assume that if they don't have the striped hat, other two will announce that they have striped hat after 2 times. Since they will not, all three can conclude that they also have striped hats and will announce it after 3 times the question is asked. (The other people who could see three striped hats, will wait for the 4th time, but this will not happen, as the 3 people will announce the fact after the 3 time itself).
The logic is taken from the famous Blue Eyed Problem.