MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

closed as off topic by Gerry Myerson, Bruce Westbury, Gjergji Zaimi, Franz Lemmermeyer, David Roberts Jul 6 '11 at 7:28

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Looks like a fun question. But this website (see the faq) is for questions related to mathematical research. Unless there's a research connection here, better take it to math.stackexchange or similar. – Gerry Myerson Jul 6 '11 at 6:17
Oh darn got them mixed up. Thanks! – randomPerson Jul 6 '11 at 6:19
It sounds connected to this puzzle: – Carlo Von Schnitzel Jul 6 '11 at 6:26
4 does in 148 questions, and proves this to be optimal. – Boris Bukh Jul 6 '11 at 7:34

Browse other questions tagged or ask your own question.