4
$\begingroup$

There are $n$ people in room each being put on hat from amongest at least $n$ white hats and $n-1$ black hats. They stand in a queue, so that everyone can see the colour of the hat of the person standing in front of him.

Starting from the back we ask the person in turn, "Do you know the what is the colour of your hat?" If the first $n-1$ person say no, prove that front person will say "Yes colour of my hat is white."

original question

$\endgroup$
  • 1
    $\begingroup$ A little clarification: "Each one can se the colour of the hat of the PERSON standing in front of him" or "Each one can se the colour of the hat of the PERSONS standing in front of him"? $\endgroup$ – Yiorgos S. Smyrlis Oct 30 '14 at 6:50
  • 2
    $\begingroup$ If we assume that "Each one can see the colour of the hat of ALL the PERSONS standing in front of him", then there is an explanation. If instead we assume that "Each one can see the colour of the hat ONLY of the PERSON standing in front of him", then the last one can not know. Take for example the case $n=3$, where the 1st and 2nd guy would say I don't know, regardless of the colour of the hat of the guy in front of them. $\endgroup$ – Yiorgos S. Smyrlis Oct 30 '14 at 6:59
  • 1
    $\begingroup$ I am still confused, if there are at least $n$ white hats in a room of $n$ people, how can there be a black hat? $\endgroup$ – IAmNoOne Oct 30 '14 at 7:02
  • 1
    $\begingroup$ @Freddy, no I am asking all those questions because I don't understand the problem, that is I am trying to say there is something wrong with it. Unless I am completely reading this all wrong. $\endgroup$ – IAmNoOne Oct 30 '14 at 7:15
  • 2
    $\begingroup$ @Freddy What book is this from? From the image you posted it seems that English is not the author's native language. Perhaps "person" was meant to be "persons". $\endgroup$ – bof Oct 30 '14 at 8:57
1
$\begingroup$

Solution:

Let $p(n)$: If first $(n-1)$ people say no, the person in the first will say yes.

For $n = 1$ , there are no black hats$(n-1=1-1=0)$. Hence the first person will say “Yes colour of my hat is white.”

Suppose the statement is true for $n=k$.

Let $n=k+1$

See how the man standing in the front would think. Suppose my hatis black, then there are $k$ people with at least $k$ white hats and $k-1$ black hats.

By $p(k)$, since first $(k-1)$ person said no, the person behind me must say yes. "I know the colour of my hat is white"

If he says mo. So colour of my hat can not be black. Hence it is white.

So $p(k)$ is true

so, $p(k)$ is true $\implies$ $p(k-1)$ is true.

Hence by the principle of mathematical induction it is proved!

Explanation:

IF $n=2$, there is 1 black hat and at least 2 white hats. If the last person sees a black cap is put on by the person in front on him, he would definitely say "yes colour of my hat is white" as there is only 1 black hat.

But if he not able to answer first person will logically thinks he has put white hat and person behind him might have out black or white hat.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ How does this work if $n=3$? Suppose #1 and #2 (from the front) have black hats and #3 has the white hat. We ask #3 first. He sees a black hat on #2, he can't see #1's hat, of course he doesn't know what color his own hat is. $\endgroup$ – bof Oct 30 '14 at 8:52
  • $\begingroup$ It does not work for $n=3$! Think about @bof's comment! $\endgroup$ – Yiorgos S. Smyrlis Oct 30 '14 at 11:36
  • $\begingroup$ @bof Yes you are right it doesn't work for that!! $\endgroup$ – Freddy Oct 30 '14 at 13:47
1
$\begingroup$

I'm supposing every person can see the color of all the hats in front of him.

If the last person in the queue says $no$, then every one hears his reponse and then knows that there is at least $1$ white hats on the head of the first $n-1$ persons. Because otherwise the last person can deduce his own hat is white.

Now for the second last person, if he sees no white hat in front of him, then he knows his own hat is white. But he says still $no$, which means there is at least a white hat in front of him. And his response is heard by everyone and everyone knows there is at least a white hat on the head of the first $n-2$ persons.

Similarly, if one person says $no$, this means there is at least a white hat in front of him and everyone knows that information after they hear the response.

So finally the first one knows his hat is white..

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If the first $n-1$ persons are all wearing black hats, how does that enable the last person to deduce his own hat is white, seeing as he can only see one hat, the hat of the person in front of him. $\endgroup$ – bof Oct 30 '14 at 9:00
  • $\begingroup$ @bof I am not sure if it's possible in that case. I am supposing everyone can see all the hats in front of him. $\endgroup$ – Petite Etincelle Oct 30 '14 at 9:12
0
$\begingroup$

This is not an answer, as there is a serious problem in the formulation.

As I said in my comments, each of the persons has to be able to see the hats of all the persons in front of him/her. Not just the hat of the guy next to him/her.

Let me explain why with the current formulation, it does not work even for $n=3$.

The first one will say I don't know regardless of the colour of the hat of the second guy. So his answer DOES NOT provide any piece of information to the second and third guy. Similarly, the second guy will also answer no, regardless of what he sees on the head of the third guy, and this also does not provide any information to the third guy.

On the other hand, if the first could see the hats of the 2nd and 3rd guy, then by saying I don't know, the 2nd and 3rd guys obtain the information the the 1st guy does not see 2 black hats. So if the 2nd guy also says, I don't know, then the 3rd guy will know that his hat is not black, for if it were black, then the 2nd guy, knowing that the 1st does not see 2 black hat, his own hat would be white. This argument can be generalised using induction to $n$ white and $n-1$ black hats.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.