10
$\begingroup$

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.

  • 0
    @Gerry: thanks for the link, I was about to ask whether 198 questions was best that could be done2011-07-06

2 Answers 2

8

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.

0

(cross-posted and updated from a closed-as-duplicate question)

If you pair up the professors and ask each about the other, there are a few possible outcomes ($H$ "is honest", $D$ "is dishonest"):

$\begin{array}{|c|c|c|c|} \hline \text{Prof }1&\text{Prof }2&1 \text{ says that }2&2\text{ says that } 1 \\ \hline H & H & H & H \\ \hline H & D & D & H \\ & & D & D \\ \hline D & H & H & D \\ & & D & D \\ \hline D & D & H & H \\ & & D & H \\ & & H & D \\ & & D & D \\ \hline \end{array}$

As you can see, each professor saying the other is honest can only occur if the two are the same (both honest or both dishonest). We can use this to eventually identify an honest professor, who can then tell us all about any remaining professors we need to know about.

Since there are more honest professors than dishonest we will get at least one pairing of honest professors, and for each pairing of dishonest professors we will get another pairing of honest professors. So there will always be more honest professors than dishonest among the possible [$HH$] reporting pairs.

We can then iteratively pick one each from these pairs to produce a new pool (for odd numbers, one professor can wait until the next round) to make a new set of tests, each time with a surplus of honest professors. The final professor (and all his prior companions, etc) will be honest, and we can ask any one of them about the remaining professors.

The first round of pairings we potentially use $100$ questions, the second round $50$, the third round $24$ ($1$ bye), the fourth round $12$ ($1$ bye), fifth round $6$ ($1$ bye), sixth round $4$. Total questions so far (worst case), $196$. This leaves us with one or two professors, who are honest. We also know that anyone that was in a pair with these professors is also honest, as is anyone who was in a pair with them, etc. - a minimum of $32$ professors. Unfortunately you would need to ask the honest professors about the other (up to) $64$ professors, which would leave my scheme beyond the target at $258$ questions (although that could certainly be optimized down somewhat by backtracking from rejected pairs).

It's possible that there are enough pairs rejected due to an honest/dishonest mix along the way that this scheme actually comes out significantly better than the worst case, and would meet the question limit, but I don't see a simple way to demonstrate that.


Subsequently, I read the Spider Interrogation Strategy in the pdf, which would apparently achieve the purpose in at most $148$ questions. Clever stuff, recommended.