
September 17th, 2013, 04:31 PM
#1
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.

September 18th, 2013, 12:08 AM
#2
Re: Optimal Algorithm (Puzzle)
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 N1 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 N1 questions to be asked.
All in all this gives a linear dependency on N, that is the algorithm is O(N).
Last edited by dazzle; September 19th, 2013 at 01:18 AM.

September 18th, 2013, 04:47 AM
#3
Re: Optimal Algorithm (Puzzle)
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
