September 17th, 2013, 05:31 PM
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).
Tags for this Thread
Click Here to Expand Forum to Full Width