Author |
Topic: Oh No! Not Another Fork in the Road (Read 5427 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
Re: Oh No! Not Another Fork in the Road
« Reply #25 on: Sep 1st, 2006, 7:27am » |
 Quote  Modify
|
Well, we already have the N-2 upper bound, and if N is even we can just ignore somebody at random, reducing the bound to N-3.
This seems to be the right answer for n = 3 to 6.
Edit: So, it's probably more natural to give the answer in terms of L = the number of liars. We've shown that it can be solved with 2L - 1 questions. Obviously at least L questions are necessary, since with L - 1 questions everyone we ask could be a liar, along with anyone else.
If we find at least two people who are identified as truth-tellers, than we can't solve it in L questions either. Of course all the people we ask could be lying. If A identifies B as a truth-teller, and C identifies D as a truth-teller, with B != D, then all the people we ask besides A could be a liar, plus anyone besides B. Similarly, anyone besides C or D could be a liar. So anyone can be a liar.
So, if the answer to the first question is "no", then we can't point to anyone else besides who we pointed to the first time, or we might wind up with the above situation. But if the guy we're pointing to is a liar, we obviously can't find a truth-teller this way.
Well, that bumps it up to L+1, but we'll never get to 2L-1 this way... I need a new approach.
|
| « Last Edit: Sep 1st, 2006, 8:20am by Deedlit » |
 IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Oh No! Not Another Fork in the Road
« Reply #26 on: Sep 1st, 2006, 8:35am » |
Quote Modify
|
on Sep 1st, 2006, 7:27am, Deedlit wrote:Well, we already have the N-2 upper bound, and if N is even we can just ignore somebody at random, reducing the bound to N-3.
This seems to be the right answer for n = 3 to 6. |
|
I don't understand.
| hidden: | With 3 villagers, only 1 question is necessary.
With 4 villagers, only 1 question is necessary.
With 5 villagers, I'm pretty sure 3 questions are necessary. Certainly with the pair-and-chair algorithm, 2 "no" answers require a 2nd round (and third question). Can anyone prove that there is no way to guarantee finding a truth-teller with two questions?
The pair-and-chair algorithm is pretty good, though not always optimal:
- With 2 villagers (and nobody in the chair), no questions are necessary, though p&c would have you ask a question.
- With 4 villagers (and nobody in the chair), only 1 question is necessary - if A says that B is a Liar, then C is a truth-teller. If A says that B is not a Liar, then he isn't. In this case, full p&c might have you ask 3 questions!
I'm not sure if there are other cases where the pair-and-chair algorithm is non-optimal. Pair-and-chair also never modifies itself based on answers. One might suspect that an optimal algorithm would change later questioning depending on earlier answers.
|
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Oh No! Not Another Fork in the Road
« Reply #27 on: Sep 1st, 2006, 8:52am » |
Quote Modify
|
on Sep 1st, 2006, 8:35am, joefendel wrote:
I don't understand.
| hidden: | | With 5 villagers, I'm pretty sure 3 questions are necessary. Certainly with the pair-and-chair algorithm, 2 "no" answers require a 2nd round (and third question). Can anyone prove that there is no way to guarantee finding a truth-teller with two questions? |
|
|
Yes, it's just brute force search.
The answers you give match up with the above bound. Can you be more specific about what you don't understand?
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Oh No! Not Another Fork in the Road
« Reply #28 on: Sep 1st, 2006, 10:54am » |
Quote Modify
|
on Sep 1st, 2006, 8:52am, Deedlit wrote:
Yes, it's just brute force search.
The answers you give match up with the above bound. Can you be more specific about what you don't understand?
|
|
Oh, I missed the "If N is even" bit! I understand now.
In fact, this seems to "optimize" the p&c algorithm:
| hidden: | | If there are an even number of villagers, begin the process by sending one away so that you have an odd number. |
This takes care of my "non-optimal" cases above, in any case.
So is this modified p&c actually optimal? If so, I get an interesting formula for the minimum number of questions required to identify a truth-teller from among N villagers!
| hidden: |
It looks like I was on the right track before. Write N-1 out in binary. Let F be the number of 1-digits in this representation. Then you need N - F - 1 questions to identify a truth-teller using this modified p&c.
For example, with 80 villagers, write 79 as 1001111, which has 5 1-digits, so 80 villagers require 80-5-1 = 74 questions using modified p&c. This bears out: 39 in round 1, 19 in round 2, 9 in round 3, 4 in round 4, 2 in round 5, 1 in round 6.
I've double-checked, and this can be easily proven by induction.
|
But I still don't have a proof that modified p&c is optimal.
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
|
Re: Oh No! Not Another Fork in the Road
« Reply #29 on: Sep 1st, 2006, 10:37pm » |
Quote Modify
|
There is a "trivial" solution (slightly different than the p&c, although I haven;t checked in depth (may be identical in essence)). This solution yields N-1.
Improvments to N-2 are straightforward.
For N=>4 and even, remove one to get N-3.
IIRC there is a proof that this is optimal.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Oh No! Not Another Fork in the Road
« Reply #30 on: Sep 2nd, 2006, 12:57am » |
Quote Modify
|
Actually, Joe and Eigenray's solution already does better in general; the worst case is n = 2m + 1, which yields a maximum of n-2 questions, but the best case is n = 2m, which yields a maximum of n - m - 1 questions. On average, the bound is around n - 1 - [log2 (n-1)]/2 questions.
Since we need at least L + 1 questions for L >= 2, the bound is exact for n = 1 to 8. So n = 9 is a good test case for the optimality of the algorithm - it gives a maximum of 7 questions, while the lower bound is 5 questions.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print