My original concern with that logic for odd N is whether the +2 honest majority would be maintained in the N-1 sample that we take to the next round (since the odd man out might be honest). However, I see now that this is of no concern, because if N is odd we will have a +3 majority (coming from previous round we know we'll have at least +2, but since N is odd we can't have exactlky +2, it has to be at least +3), and after setting one guy aside the remaining profs will have at least +2.
Bob H On Apr 30, 3:52 am, pramod <[EMAIL PROTECTED]> wrote: > OK, it's a long time for me too. > So let's see. > If we start with odd number of people, then we'll be left out with one > who won't be carried out in the next iteration. > Only when we found out at the end who the one truth teller is that we > ask the truth teller whether the left out single person is a liar or > truth teller. > So in this case only one question is needed for this person which is > what was needed otherwise too. > > Hope it's clear. Take an example of odd numbered case and it should be > apparent. > > On Apr 29, 4:48 pm, me13013 <[EMAIL PROTECTED]> wrote: > > > (sorry to reply so late, I only discovered this thread yesterday) > > > back on Mar/9 pramod wrote: > > > > 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. > > > ... > > > Hence proved. > > > The proof given is only valid when the number of people you start > > with, in every round, is even. How do you handle the odd case? > > > Bob H --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
