Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found this in An Introduction to Bioinformatics Algorithms. I've paraphrased for clarity.

There are 100 professors. Some are honest, while others are dishonest. There are more honest professors than dishonest ones. Honest professors always tell the truth, but the dishonest ones sometimes tell the truth and sometimes lie. You can ask any professor the following question about any other professor, "Professor Y, is Professor X honest?" to which he/she will answer yes or no. Design an algorithm that allows you to figure out which of the professors are honest with no more than 198 questions.

The bold part is the kicker. If liars always lied, then the problem is trivial - just ask 99 people about one guy. The majority would be the truthful answer, so you know your honest guys and your liars.

So, any advice? If you give the answer please put it in spoiler tags since I'm just looking for direction.

share|improve this question
    
Some observations. A dishonest professor can give any answer to any question. You can't distinguish between an honest professor and a dishonest professor by the answers they give, because a dishonest professor is capable of giving the same answers as an honest one. As soon as you identify an honest professor, you can ask that one about all the others you don't already know about. The information that the majority are honest is clearly crucial. If a professor gives an answer different from the majority, they are clearly dishonest, but you can't guarantee that will happen. –  Mark Bennet Jul 6 '11 at 7:21
1  
The problem was posed and closed on MathOverflow, but not before Boris Bukh left a link to a solution at ma.rhul.ac.uk/~uvah099/Maths/ksDRev2.pdf –  Gerry Myerson Jul 6 '11 at 9:48
    
@Gerry: thanks for the link, I was about to ask whether 198 questions was best that could be done –  Mark Bennet Jul 6 '11 at 10:14
add comment

1 Answer 1

Spoiler

Randomly pair the professors, for each pair ask both the professors, the opinion of each other. Pick one from each of the pairs which result in the answer of (Honest, Honest). Rinse, Repeat.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.