A very large department has a mix of 100 professors: some are honest and hard-wo
ID: 3748905 • Letter: A
Question
A very large department has a mix of 100 professors: some are
honest and hard-working, while others are deceitful and do not like students.
The honest professors always tell the truth, but the deceitful ones sometimes
tell the truth and sometimes lie. You can ask any professor the following ques-
tion about any other professor: professor Y , is professor X honest? Professor
Y will answer either with yes or no. Design an algorithm that, with no more
than 198 questions, would allow you to figure out which of the 100 professors
are honest. It is known that there are more honest than dishonest professors.
Explanation / Answer
Given : There are more honest than dishonest professor
Solution :
Consider out of 100 professors , there are 51 honest ones and 49 bad ones .
when asked 51 honest professors questions about the rest 49 it becomes easy to point out that there will be dishonest professors. 51 questions are being asked about the 49 professors about their honesty and they will exactly correct whether they are trutfully honest or dishonest.
All it takes is 51 questions of honest professors about the rest 49 to identify the dishonest ones.