2. "There are three black hats and two white hats. Let three people stand in a row from front to back, each wearing a hat. Everyone can't see the color of his hat, but he can only see the color of the hat of the person standing in front. So the last person can see the colors of the hats on the heads of the two people in front, the middle person can see the colors of the hats of the people in front but not the hats of the people behind, and the first person can't see anyone's hats. Now, start with the last person and ask him if he knows the color of the hat he is wearing. If he says no, keep asking the person in front. In fact, all three of them wear black hats, so the person in front will know that he is wearing a black hat. Why? "
The answer is that the person in front heard the two people behind say "I don't know". He assumed that he was wearing a white hat, so the people 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 always only two white hats, so he should understand that he is wearing a black hat. Now he says he doesn't know, which means that my assumption of wearing a white hat is wrong, so I wear a black hat. " The problem is that if the person in the middle says he doesn't know, then the person in front knows that his assumption of wearing a white hat is wrong, so it is inferred that he is wearing a black hat.
We summarize this problem in the following form:
"There are several colors of hats, each with several tops. Suppose several people stand in a row from front to back and put a hat on each person. Everyone can't see the color of the hat he wears. Everyone can see the color of the hat on everyone in front of him, but can't see the color of the hat on anyone behind him. Now, starting with the last person,
Ask him if he knows the color of the hat he is wearing. If he says no, keep asking the person in front. Keep asking, then someone must know the color of his hat. "
Of course, we must assume some conditions:
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 message "How many hats of different colors, how many hats of each kind and how many people" is known by everyone in the queue in advance, everyone knows that everyone knows about it, everyone knows that everyone knows that everyone knows about it, and so on. However, the "number" in this condition need not be given in detail.
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 "there are 1 red, yellow and green hats, but I don't know which colors, there are 6 people", or even the specific number of people, "I don't know how many people are in a row, there are black and white. The number of each hat is less than the number of people 1 ". At this time, the last person who came didn't know he was the last one-he didn't know he was the last one until he started asking him and found that no one else asked him. In the next part of this post, when I write the title, I only write the preset condition of "how many hats there are in several colors, how many hats there are in each kind, and how many people there are", because this part is certain and the title is also certain.
3) Of course, the remaining hats not worn on everyone's heads are hidden, and no one in the team knows what hats are left.
4) Everyone is not color blind, not only not, but as long as the two colors are different, they can be distinguished. Of course, their eyesight is also very good, and they can see anywhere far ahead. They are extremely clever and have excellent logical reasoning. In a word, as long as it can be deduced logically in theory, it will certainly be deduced. On the contrary, if they can't figure out the color of the hat, no one will guess or cheat and peek-I don't know.
5) The people behind can't whisper or signal to the people in front.
Of course, not all presuppositions can give reasonable questions. For example, 99 black hats, 99 white hats and 2 people. No matter how you wear them, no one can know the color of their hats. In addition, as long as there is not only one color hat, it is impossible for this person to tell the color of his hat in a team composed of only one person.
But the following questions are reasonable:
1)3 red hats, 4 black hats, 5 white hats, 10 people.
2) Three red hats, four black hats, five white hats and eight people.
3)n black hats, n- 1 white hats, n people (n>0).
4) 1 hat color 1, 2 hat color 2, ..., 99 hats with color 99, 100 hats with color 100, * * 5000 people.
5) There are 1 hats, with three colors of red, yellow and green, two hats and three hats, but I don't know which color is how many hats, and there are six people.
6) I don't know how many people are in a row (at least two people). There are two kinds of hats, black and white, and the number of each hat is less than the number of people 1.
You can try to do these questions without looking at my analysis below.
If we follow the reasoning method of the above three black hats and two white hats, then 10 people can kill us, let alone 5000 people. But n in 3) is an abstract number. Considering how to solve this problem is of great benefit to solving general problems.
Suppose n people are wearing hats now and ask the last person in the queue what color his hat is. When will he answer "Yes"? Obviously, it is only possible when he sees that all the people in front of n- 1 are wearing white hats, because all the white hats in n- 1 are 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 can't rule out the possibility that his head is black-even if all the people in front are black hats, he may still wear the nth hat.
Now suppose the last person's answer is "I don't know", so it's the turn to ask the penultimate person. What can he infer from the last answer? If all he sees is a white hat, he can immediately infer that he is wearing a black hat-if he is also wearing a white hat, then the last thing this person should see is a white hat. When asked about him, he should answer "know". But if the penultimate person sees at least one black hat in front of him, he can't judge-he may be wearing a white hat, but those black hats in front make the last person unable to answer "know"; Naturally, he may also wear a black hat.
This reasoning can continue, but we have seen signs. Finally, that person can answer "know" 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. This is the key to all hat color problems!
If the last person answers "I don't know", then he has seen at least one black hat. If the last person has seen all white hats, where is the at least one black hat that the last person saw? Not anywhere else, just on the head of the penultimate person. If this reasoning continues, then for everyone in the queue:
"Everyone behind me has seen at least one black hat, otherwise they will judge that they are wearing a black hat according to the same judgment, so if I see that the people in front are all wearing white hats, I must put the black hat that the people behind me see on my head."
We know that the person in front can't see any hat, let alone see a black hat, so if the person behind answers "I don't know", then according to the above reasoning, it can be determined that he is wearing a black hat, because the person behind must have seen the black hat-only the one on the head of the first person. In fact, it is obvious that the first person to tell what color hat he is wearing is the first person to wear a black hat from the beginning of the team, that is, the first person to see that everyone in front of him is wearing a white hat from the end of the team.
This kind of reasoning may make people feel a little circular, because the above reasoning contains the meaning of "if others use the same reasoning", and logically such a self-reference proposition is a bit dangerous. But in fact, there is no circular argument here, similar to mathematical induction. Everyone's reasoning is based on the reasoning of the people behind him, and for the last person, there is no one behind him, so his reasoning can be established without relying on other people's reasoning, which is the first reasoning in induction. With a little thought, we can turn the above argument into any multi-color inference:
"If we can assume that there will be a hat of a certain color in the queue, then the first person who can't see the hat of this color from the end of the queue can immediately judge according to the same argument as this argument. He is wearing a hat of this color. Now the people in the back answer that they don't know, so the people in the back also see the hat of this color. If I can't see this color hat in front of me, then I must be wearing this color hat. "
Of course, the first person's initial reasoning was quite simple: "There must be someone wearing this color hat in the queue. Now I can't see anyone wearing this color hat in front, I can only wear it on my head. "
For the question 1), it becomes obvious that three red hats, four black hats and five white hats are for 10 people, and there must be at least one hat of each color in the queue, so the first person who can't see a hat of a certain color from the end of the queue can conclude that he is wearing a hat of this color. It can also be seen that when asking the third person in the front row at most, because the third person in the front row can only see two hats at most, he can see two colors at most. If everyone behind him answers "I don't know", then there must be two colors of hats in front of him. He must be wearing a hat that can't see the color.
Question 2) The same is true. Three red hats, four black hats and five white hats belong to eight people, so there must be at least one white hat in the queue, because the other colors add up to seven, so someone in the queue will definitely answer "yes".
The scale of question 4) is a bit large, but the reason is exactly the same as that of question 2). 5050 hats, 100 colors, worn by 5000 people. The number of hats with 99 colors in front is 1+...+99 = 4950, so there must be hats with 100 color in the queue (at least 50 hats), so if everyone behind him answers "I don't know", then that one can't see the color.
As for 5) and 6), "There are 1 hats, red, yellow, green and three hats, but I don't know which color is several, and there are six people" and "I don't know how many people are in a row, and there are black and white hats, and the number of each hat is less than the number of people 1". The principle is exactly the same, so I won't analyze it in detail.
Finally, we have just demonstrated that if we can judge that there is at least one hat of a certain color in the queue according to the number of hats of various colors and the number of people in the queue, then there must be a person who can judge the color of the hat on his head. Because if everyone behind you answers "I don't know", the first person who can't see this color hat from the end of the line can judge that he is wearing this color hat. 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 in which the faces in the queue face)
White, black, black, black, red, red and white →
Then the first person in the last line can immediately answer that there is a white hat on his head, because he has seen three red hats and four black hats, and only the white hat can be kept for himself.
3. Recursive algorithm can be used for this problem, but the time complexity is 2 to the n power, and dynamic programming method can also be used. The time complexity is the square of n, which is much simpler to realize, but the most convenient method is to use the formula directly: the number of queued species =(2n)! /[n！ (n+ 1)！ ]。
If you don't consider whether the cinema can change money, then a * * * has (2n)! /[n！ n！ There are three ways to queue (that is, take out the number of combinations of n people from 2n people). For each queuing method, if it will cause a loss to the cinema, it is called unqualified. This queuing method has (2n)! /[(n- 1)！ (n+ 1)！ ] (take out the combination number of n- 1 person from 2n people), then the number of eligible queued species is (2n)! /[n！ n！ ]- (2n)！ /[(n- 1)！ (n+ 1)！ ] =(2n)！ /[n！ (n+ 1)！ ]。 As for why the unqualified number is (2n)! /[(n- 1)！ (n+ 1)！ 】, it is too complicated to say, so I won't say it here.
Good luck!