A few days ago, I saw a very interesting topic on the homepage of the blog hall (http://blog.joycode.com). The topic is as follows:
Saying the residents on a small island have two tribes. One tribe is only truth, and the other person sometimes tells the truth, sometimes telling the fake. (Listen is very familiar?) Everyone on the island knows the true identity of others (how to know? Don't ask me, huh, I know that there are more than 2005 people on the island, and the tribes of the tribes are more than those who are not necessarily tribes. If you are the new governor on the island, I want to figure out their identity, so you need to pick a assistant from the truth tribe. So you held the first island meeting of the X-General, you can ask questions from anyone. Can you find an assistant in less than 4,000 questions? Note that a question is an interrogator, if you ask three people the same problem, it is considered three questions, and any problem may not involve 1 group of people, such as you can't ask, "Who is the smallest tribe in this 100 people? Such problems.
At that time, the rough thinking about this topic has a place very badly, and sometimes the people who are lying will deliberately tell the truth to confuse the governor. If this is true, don't say 4000 questions, it is 40,000 people who don't necessarily find a helper that only tells the truth. Moreover, the only thing that can be confirmed by the whole topic is that people who tell the truth is much more than the number of people lying.
In order to solve, only people who are lying are set to random states, ie the probability of lying lying lying is always around 1/2. Go on then ...
I don't think about 4,000 questions, I think of a way: first, first randomly pick one from everyone, then ask questions to the remaining people, ask the people in this wheel to tell the truth or talk , Statistics on the answer. The answer is the same, and the number of people is sure all the people who sometimes speak fake. If the answer is the same, the number of people answers the people in this round of the truth, the people in this wheel will definitely tell the truth, the assistant is found, bingo! ! ! Otherwise, sieve the one who is less than the number of people and the number of people in this press, the rest of the people enter the lower wheel, continue to continue ...
According to this approach, the new Governor finally finds a truth. However, this method takes more than 4,000 questions for this method. So, there is a way to optimize this benzene algorithm? After thinking about it, I found a start-up point. The total number of people at the beginning of each round is M. After the question is over, the number of answers is the same, and the number of people is N. Then, after screening the one of the people in this press and the number of people, then randomly remove (N 1) people from the remaining people. At this point, the number of people who have been sieved for 2 times or to ensure that the number of people telling the truth. Thus, after each round is over, the question range can be reduced (m-2 * n-2).
The number after the optimization is more than the number of people who are lying (assuming to a maximum of 1002 people), and each selected person sometimes tells the truth, sometimes, can meet the topic of up to 4000 questions. .
The first round: 2005 people, remove the chosers, the number of people who are lying is 1001. Results There were 500 people in 2004, because the false words were sieved, and finally sieved for 1002 people. Take the worst case, 501 people from the second screen are all telling the truth;
The second round: 1003 people, remove the chosers, sometimes the number of people lying is 500. Results There were 250 questions in 1002 questions because they were sieved, and finally sieve 502 people. Take the worst case, the 251 people from the second screen are all truth;
The third round: 501 people, remove the chosers, sometimes the number of people lying is 249. Results There were 124 people in 500 questions because they were sieved, and finally sieved 250 people. Take the worst case, the 125 people in the second screen are all truth; the fourth round: 251 people, remove the chosers, sometimes lying is 124. Results There were 62 people in 250 questions because they were sieved, and finally sieved 126 people. Take the worst case, 63 people from the second screen are all told;
The fifth round: 125 people, remove the chosers, sometimes lying is 61. Results There were 30 questions in 124 questions because they were sieved, and finally sieveded 62 people. Take the worst case, 31 people from the second screen truthfully;
Sixth round: 63 people, except for the chosers, the number of people who are lying is 30. Results There were 15 questions in 62 questions because they were sieved, and finally sieved 32 people. Take the worst case, 16 people in the second screen are all truth;
The seventh round: 31 people, remove the chosers, the number of people who are lying is 14. Results There were 7 people in 30 questions because they were sieved, and finally sieve 16 people. Take the worst case, 8 people from the second screen truthfully;
Eighth rounds: 15 people, remove the chosers, sometimes the number of people lying is 6. Results There were 3 people in 14 questions because they were sieved, and finally sieved 8 people. Take the worst case, the 4 people from the second screen truthfully;
The ninth wheel: 7 people, remove the chosers, sometimes the number of people lying is 2. Results There were one question in 6 questions, because of the false words, the last part was sieved. Take the worst case, the 2 people from the second screen truth;
The tenth round: the last three people, one of them sometimes tells the truth, sometimes tells the fake, and we consume (2004 1002 500 250 124 62 30 14 6) 3992 questions. The last 8 chances are enough to find out the help of telling the truth ^ - ^
The above method is feasible in the case where the number of people lying is more, then it does not mean that when I sometimes tell the truth, sometimes the number of people don't have fewer people. Let's take a look at that only 11 in 2005 sometimes tell the extreme situation of fake words (the same, every time the selected person is sometimes telling the truth sometimes telling the falsehood):
The first round: 2005 people, remove the chosers, the number of people who are lying is 10. As a result, only 5 people in 2004 were sieved by the false words, and finally sieved 12 people. Take the worst case, 6 people from the second screen are all truth;
The second round: 1993 people, remove the chosers, the number of people who are lying is 4. Results There were only 2 people in 1992, and they were sieved due to false words;
It has been spent 4002 questions at this time, beyond the title requirements. It seems that the above method is in this case. And slow, let us pay attention to the ratio of each round because of the ratio of the number of people deleted and the number of questions.
Sometimes the number of people is 1002 people, there are 500 people in 2004, and when this number fell to 11 people, only 5 people in the same 2004 question, this is a breakthrough. We can determine all of people based on this ratio, sometimes the number of people who lying, if the ratio is near 1/4, and the number of people who guarantees the truth, the number of people is substantially quite. So, is we set a coefficient X based on this ratio, let the second screen fall (N 1) * X people?
Please wait, let us reverse thinking.
Since the probability of lying people who lying prior to the previous assumption is always kept near 1/2, if the number of people from the filling, it can be sure, hidden in the population of (M-N-1), and the number of people who are lying is roughly N. So, as long as we are randomly withstand (2 * n 1) from the remaining (M-N-1) population. In this newly selected population, you can guarantee that people who tell the truth are more than people who are lying! ! ! Now let's take a look at only 11 people in 2005 sometimes lying, and it is effective to use the solution (2 * n 1).
The first round: 2005 people, remove the chosers, the number of people who are lying is 10. As a result, only 5 questions in 2004 were splitted from the first screening of 1999;
The second round: 11 people, remove the chosers, sometimes the number of people lying is 4, at this time, only 10 questions will be issued. Don't have been analyzed later.
Sometimes the number of people lying is the same as the result of the above analysis, and after the nine-round screening, it can get the result of final 3 election 2 after the nine-round screening. At this point, the analysis ends. Finally, the final solution given is as follows:
In the case where the chance to lying lying lying is always in the vicinity of 1/2, first randomly selected 1 person in 2005, ask the remaining 2004 people, whether the selected person is lying. If you have already asked 2004 people, I replied that "not" is halfway, then the selection is always telling the truth, the assistant is found. Otherwise, the number of people set "is not" (ie, in this wheel question) is n, and randomly select 2 * n 1 person from the crowd that answer "Yes". Repeat the above operation until the last 3 people are selected, or the "not" is over half.
