I think I made a mistake. After we found out the truth teller, we need 2 questions for each of the "tl" and "ll" groups. This is because we know at least one of them is a liar and nothing else. Say the answer is "yn" then the group could be "tl" or "ll". Similarly if the answer is "nn" then also the group could be "tl" or "ll". We need two questions to tell who's who and not one. So my previous argument was wrong.
Here's another argument. Say there are 'a' number of "tt" groups, 'b' number of "ll" who answer "yy", 'c' number of "tl" and 'd' number of "ll" whose answer has a "no" in it. Then total number of questions asked so far for grouping is 2(a+b+c+d) = N the number of people we started with. Now with induction we'll prove that for 'p' people we need at most 2p-2 questions. In the next iteration we have a+b people so we need at most 2(a+b)-2 questions to identify all the truth tellers and liars among a+b. Once we have that we need 2 questions each for c,d groups so we need to ask 2(c+d) questions. So total questions asked are 2(a+b+c+d) + 2(a+b) -2 + 2(c+d) = 4(a+b+c +d)-2 = 2N-2. Hence proved. For 100 people we need at most 198. The "-2" is coming from the fact that for the case of N=2 we don't need to ask any questions as both have to be truth tellers. I hope I am right this time. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
