mathematics classics

Chapter 3 Hat Color Problems
problem
This should be one of the oldest and earliest interesting logic problems. His general form is this: "There are 3 black hats and 2 white hats. Let three people stand in a row from front to back, and give each of them wear a hat.

"Everyone can't see the color of his own hat, but only the hats of those standing in front of him.

(So ​​the last person can see the color of the hats on the heads of the two people in front, the person in the middle can see the hat color of the person in front but not the hat color of the person behind him, and the person in front can see everyone's hats not see.)
Solution
"Now start with the last person and ask him if he knows the color of his hat, and if he says no, go ahead and ask the person in front of him.

"In fact, all three of them are wearing black hats, so the person in the front must know that he is wearing a black hat. Why?"

The answer is that the person in the front heard the two people behind say "don't know", and he assumed that he was wearing a white hat, so the person in the middle saw the white hat he was wearing.

Then the person in the middle will make the following reasoning: "Suppose I wear a white hat, then the last person will see the two white hats in front, but there are only two white hats in total, and he should understand that he is wearing a black hat. Now that he says he doesn't know, it means that the assumption that I wear a white hat is wrong, so I wear a black hat."

The problem is that the person in the middle also said he didn't know, so the person in the front knew that his assumption of wearing a white hat was wrong, so he deduced that he was wearing a black hat.

We generalize this problem to the following form:
"There are hats of several colors, several of each. Suppose there are several people standing in a row from front to back, and each of them wears a hat on his head.

"Each man cannot see the color of the hat he wears, and each man sees the color of the hats of all the people in front of him, but not of the hats of anyone behind him.

"Now start from the last person and ask him if he knows the color of the hat he is wearing. If he answers that he does not know, continue to ask the person in front of him. Keep asking, then there must be someone who knows the color of the hat he is wearing .”

Of course some assumptions are made:
(1) First of all, the total number of hats must be greater than the number of people, otherwise there are not enough hats to wear.

(2) The information "there are hats of several colors, how many of each type, and how many people there are" is known in advance by everyone in the queue, and everyone knows that everyone knows this, everyone knows everyone Everybody knows everybody knows about it, blah blah blah.

However, the "several" in this condition does not necessarily have to give specific numbers one by one.

Specifically, this information can be in the classic form above, listing the number of hats of each color "there are 3 black hats, 2 white hats, and 3 people", or it can be "hats with three colors of red, yellow and green 1 hat, 2 hats and 3 hats, but I don’t know which color and how many hats, there are 6 people”, and even the specific number of people may not be known, “I don’t know how many people lined up, there are black and white hats, each The number of hats is 1" less than the number of people. At this time, the person who is at the end of the list does not know that he is at the end of the list-until he starts to ask him and finds that no one else is asked before he answers, he does not know that he is at the end.

In the next part of this post, when I make a question, I will only write the precondition of "there are hats of several colors, how many hats of each type, and how many people are there", because this part is determined, and the question is also determined up.

(3) The rest of the hats that were not worn by everyone were of course hidden, and no one in the team knew what hats were left.

(4) All people are not color blind, not only not, but as long as two colors are different, they can be distinguished.Of course, their eyesight is also very good, and they can see any place far ahead.They are extremely intelligent and their logical reasoning is excellent.

All in all, as long as it can be deduced theoretically and logically, they must be able to deduce it.Conversely, if they can't deduce the color of the hat on their head, no one will try to guess or cheat to peek - don't know, don't know.

(5) The people behind cannot whisper or make secret signs with the people in front.

Of course, not all preconditions can give a reasonable title.

For example, there are 99 black hats, 99 white hats, and 2 people. No matter how they wear it, it is impossible for anyone to know the color of the hat on their head.

In addition, as long as there is not only one color hat, in a team composed of only one person, it is impossible for this person to tell the color of his hat.

But the following questions are reasonable questions:
(1) 3 red hats, 4 black hats, 5 white hats, 10 people.

(2) 3 red hats, 4 black hats, 5 white hats, 8 people.

(3) n black hats, n-1 white hats, n people (n>0).

（4）1顶颜色1的帽子，2顶颜色2的帽子，……，99顶颜色99的帽子，100顶颜色100的帽子，共5000个人。

（5）有红黄绿三种颜色的帽子各1顶2顶3顶，但具体不知道哪种颜色是几顶，有6个人。

(6) There are an unknown number of people (at least two) lined up in a row, with black and white hats, and the number of each hat is 1 less than the number of people.

You can ignore my analysis below and try to do these questions.

If we follow the above reasoning method when we have 3 black hats and 2 white hats, then 10 people can exhaust us to death, let alone 5000 people.However, n in (3) is an abstract number, and thinking about how to solve this problem is of great benefit to solving general problems.

Assuming that n people have already worn their hats now, ask the last person in the row what color is the hat on his head, when will he answer "know"?Obviously, it is only possible when he sees that n-1 people in front are wearing white hats, because at this time all n-1 white hats have been used up, and he can only wear black hats on his own head. As long as there is a black hat in front of him, he cannot rule out the possibility that he has a black hat on his head-even if he sees all the people in front of him are black hats, he may still be wearing the nth black hat.

Now suppose that the last person answered "don't know", then it's the turn to ask the penultimate person.According to the last person's answer, what can he deduce?If all he sees are white hats, then he can immediately deduce that he is wearing a black hat - if he also wears a white hat, then the last person should see a white hat, and when asked he should answer "" knew.

But if the penultimate person sees at least one black hat in front of him, he cannot make a judgment - he may be wearing a white hat, but the black hats in front of him prevent the last person from answering "know"; wearing a black hat.

Such reasoning could go on, but we've already seen the beginnings.The last person can answer "yes" if and only if all he sees are white hats, so he answers "don't know" if and only if he sees at least one black hat.That's the crux of all hat color matters!

If the last person answered "don't know", then he saw at least one black hat, so if the second-to-last person saw all white hats, where is the last person who saw at least one black hat?It won't be anywhere else, only on the penultimate person's own head.

This reasoning continues, and for everyone in the queue it becomes: "Everyone behind me has seen at least one black hat, otherwise they would have judged by the same judgment that they were wearing a black hat." hats, so if I see all the white hats in front of me, I must be wearing the same black hat that the man behind me sees."

We know that the person in the front can't see any hats, let alone black hats, so if everyone behind him answers "don't know", then according to the above reasoning, he can be sure that he is wearing a black hat. hat, because the person behind him must have seen a black hat—it can only be the one on the first person's own head.

In fact, it is obvious that the first person to say what color hat he is wearing is the first person to wear a black hat from the beginning of the line, and the first person to see all the black hats from the end of the line. Everyone wears a white hat.

This kind of reasoning may feel like a circular argument, because the above reasoning contains the meaning of "if others use the same reasoning", such a self-referential proposition is a bit dangerous in logic.

But in fact, there is no circular argument here. This is a reasoning similar to mathematical induction. Everyone's reasoning is based on the reasoning of those behind him, and for the last person, there is no one behind him, so his reasoning does not matter. Inferences that depend on other people can be established, which is the first inference in induction.With a little thought, we can modify the above argument to apply to any multi-color inference: "If we can conclude from the assumption that a hat of a certain color must appear in the queue, the first one from the end of the queue will not be able to see it. The person with the hat of this color can immediately judge from the same argument as this argument that he is wearing a hat of this color.

Now all the people behind me answered that they don't know, so the people behind me also saw the hat of this color.If I don't see a hat of this color in front of me, it must be me wearing a hat of this color. "

Of course, the initial reasoning of the first person is quite simple: "There must be someone wearing a hat of this color in the queue. Now I can't see anyone wearing a hat of this color in front of me, so it can only be worn on my head."

For question (1), things become obvious. 3 red hats, 4 black hats, and 5 white hats are worn by 10 people. There should be at least one of each color in the queue, so the first one to see from the end of the queue A person who does not see a hat of a certain color can conclude that he is wearing a hat of this color. From this we can also see that when the third person counting from the head of the team is asked at most, someone should answer "know." "Yes, because the third person counting from the head of the team can only see two hats at most, so he can see at most two colors. If the people behind him answer "don't know", then there must be hats of two colors in front of him , and he must be wearing a hat of the color he cannot see.

Question (2) is the same, 3 red hats, 4 black hats, and 5 white hats are worn by 8 people, then there must be at least one white hat in the queue, because there are only 7 hats in total in other colors, so there must be Someone answered "yes".

题（4）的规模大了一点，但是道理和（2）完全一样。100种颜色的5050顶帽子给5000人戴，前面99种颜色的帽子数量是1＋……＋99=4950，所以队列中一定有第100种颜色的帽子（至少有50顶），所以如果自己身后的人都回答“不知道”，那么那个看不见颜色100帽子的人就可以断定自己戴着这种颜色的帽子。

As for (5), (6) "There are 1 hat, 2 hats and 3 hats in red, yellow and green colors, but I don't know which color is the number, there are 6 people" and "I don't know how many people lined up There are black and white hats in the platoon, and the number of each hat is 1” less than the number of people. The principle is exactly the same, so I won’t analyze it in detail.

The last thing to point out is that we just demonstrated above that if we can judge that there is at least one hat of a certain color in the queue based on the number of hats of various colors and the number of people in the queue, then there must be someone who can judge himself The color of the hat on the head.

Because if all the people behind answer "don't know", the first person from the end of the team who cannot see the hat of this color can judge that he is wearing a hat of this color.

But this does not mean that he must answer "know" in the inquiry, because there may be other ways to judge the color of the hat on his head.For example, in question (2), if the queue is as follows: (the arrow indicates the direction of the faces of the people in the queue)

White white black black black black red red red white→Then No.1 at the end of the line can immediately answer that the hat on his head is white, because he saw all 3 red hats and 4 black hats, so he can wear them for himself It can only be a white hat.

(End of this chapter)