Hi, Note that the problem is solved if you find one honest professor then you can ask him about all the other professors and solve it 99 questions from there on. The problem is to find one honest person in 99 questions. This can be done as follows,
Divide the professors into groups of 2. In each group ask if the opposite professor is honest. 4 possibilities (i) Both honest and say both honest or Both liars and say both liars Discard all the other groups Choose one person from the groups saying both honest. Observe that now whenever both are honest or both are liars in a group one of them will get included and therefore the teams that got discarded atleast have one liar. In the resulting problem with 50 members still again the majority are honest professors Therefore after one round (50 questions) For second round you have (25 questions) 50+25+(12+1)+6+(3+1)+1 = 99 questions (whenever we have odd number of ppl it takes 1 extra question to eliminate the extra guy). So we will have the person we are looking for in 99 questions. Then ask him about the remaining 99 ppl and you are done with exactly 198 questions.. I am not sure if the exact calculations are correct for each round but overall this is the logic --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
