Optimal Algorithm (Puzzle)

On a mountain there are two types of people - consistent and inconsistent. The consistent people always speak the truth, while the inconsistent people cannot be trusted (they may speak the truth or they may not). Now you go to the mountain to find all the consistent people. To do that you can ask a question to a person A regarding another person B the following way:

"Is B a consistent person?" (this is kind of questions that you can ask to a person)

Now if A is consistent then he will tell the truth. Otherwise the answer of A could be either true or false. Before you reach the mountain you realize that there are more consistent people than inconsistent people. I am looking for an algorithm using the example question shown above - to find out the number of consistent people. It is possible to do this in Big Theta (n).

Thanks.

Quote:

---

Originally Posted by vsha041

Before you reach the mountain you realize that there are more consistent people than inconsistent people.

---

Given that the consistent people are in majority, the group of all people together will be consistent. The inconsistent vote of the minority isn't big enougth to change the consistent vote of the majority.

So if everybody is asked about a specific person you will know for sure whether this person is consistent or not because what most people answer is the truth. By repeating this you will be able to locate a consistent individual eventually. This known to be consistent person can then be used to determine whether everybody else is consistent or not.

Say there are N people. A voting requires N-1 people to be asked. The number of necessary votings depends on the fraction of consistent people among the N. This number is a constant of probabilistic nature (an expectation) independent of N. Finally to classify everybody requires N-1 questions to be asked.

All in all this gives a linear dependency on N, that is the algorithm is O(N).

Thanks Buddy :-)