wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Oh No! Not Another Fork in the Road
        
(Message started by: BNC on Aug 9th, 2006, 9:17am)
Title: Oh No! Not Another Fork in the Road
Post by BNC on Aug 9th, 2006, 9:17am
Oh No! Not Another Fork in the Road
or
A Glimpse into the Religion of the Fork People


You wipe your brow as you stroll down the winding path. It had been a long day. Heck, it's been a long year. This adventure of yours, which was supposed to be fun, had turned into an ordeal a while back, but you have no visible way out.

You have lost count of the number of forks in the road you passed. Some were weird. Some were weirder. And some were... well... just crazy. And how many more forks you'll need to pass before getting back to civilization as you know it?

Well, the last fork was a simple one. You found the two classical members sitting by the road, and asked one of them what would the other one have said had you asked him.. blah-blah you can get through 5-degree metaquestions in your sleep by now.

You are getting close to a village now. Fortunate for you, you are sure it is indeed a truth-telling people village. So, without hesitance, you push open the steel gate in the concrete wall surrounding the village, and walk in. As you do, the gate slams shut behind your back! What the... a quick examination reveals the gate to be locked! And what’s more -- as you look around, you see that the village is completely deserted. Hmm...

Walking down Main Street, you reach the village square. There, on the main billboard, you see a large sign. Going closer, you read:


Welcome, stranger, to our truth-telling village! (Yes, we would say that were you to ask us tomorrow as well...)

You should know, though, that you had come on a special day -- which may prove rather difficult for you. You see, today is the Mgrtuffle Day. It is the single most important religious holiday 'round this area. Throughout this day, all of the residents from this village meet on the fork in the road just up the road outside (away from the direction you just came). There, at that fork, we meet and mingle with the residents of the two other villages that the fork leads to: the other friendly truth-tellers village, and the cannibal liars' village.

There are some rules you must know and follow, in this Mgrtuffle Day. They may seems a little strange to you – but hey – we may not approve of your religion's customs either! So, here is the short list for strangers (our list, FYI, contains 1332 rules):

1. You must leave this village and come to the fork before sundown. If, at day end, we'll come back and find you either on the way or in the village, you will be stoned to death!

2. After you reach the fork, you must leave in one of the two directions, towards one of the two villages. Not reaching either village before sundown is, again, a mortal sin.

3. If you reach the truth-telling village, you will be sheltered, fed, and generally taken care of. But should you reach the other village, you will be killed, cooked, and eaten –not necessarily in that order.

4. What may make things more difficult for you, is that on this day everyone talks only using the Frghtaj sacred language, which no one but the Fork People know, or may learn. Hence, you can't really converse with either of us down at the fork.

5. What's more, in this holiday, we, the truth-tellers will still tell the truth. The Liars, on the other hand, may tell the truth or lie, as they see fit in order to lull you into their village.

6. To assist you somewhat, we will give you some words and phrases to use. "Frrrt" means "Yes" in Frghtaj, and "Swaaakch" means "No". Pointing at a third person, while closing your left eye and saying "Ze Sham Shakran?" means "Is that person a Liar?". Note, though, that saying that while not pointing, pointing to yourself, or pointing to the person to whom you are speaking, is, once more, a mortal sin.

7. At the envelope you see below (closed and sealed using red wax) is a note saying (in Frghtaj, off course) "what is the road to the truth-telling village up the road from this fork?" You may give this envelope to any person of your choice, and you will be answered according to his or hers traits for this holiday. So you better find one of us truth-teller to give this to!

8. All the people at the fork are either truth-tellers or Liars. And everyone knows everyone else. Moreover, since there are two truth-teller villages, and only one Liars' village, there are more truth-tellers than Liars.


You pick up the sealed envelope. Looking ahead, you see the exit gate of the village, and then the gathering at the fork. Sundown is due in less than an hour, so you better work fast!

What should you do to continue your adventures?


[e]Ammended to address point made by Trebla[/e]
Edited by Icarus to increase font size to something even we curmudgeons can read.
Title: Re: Oh No! Not Another Fork in the Road
Post by THUDandBLUNDER on Aug 9th, 2006, 9:22am
Pick up the next fork?      ;)
Title: Re: Oh No! Not Another Fork in the Road
Post by SMQ on Aug 9th, 2006, 11:13am
This can probably be improved upon -- depending on the number of villiagers an hour might not be enough time -- but it should work:

[hide]The key is that there are more truth-tellers than liars, so pick someone at random and ask enough other villiagers about that person to establish the majority opinion.  If the majority says that person you were asking about is a truth teller you're done; give him/her the envelope.  Otherwise, discard that person and anyone else who lied to you, and repeat the process.  Since there are more truth tellers than liars the chances of you picking a large number of successive liars at random are very small.[/hide]

--SMQ
Title: Re: Oh No! Not Another Fork in the Road
Post by BNC on Aug 9th, 2006, 1:57pm
True, but a more efficient algorithm exist.
Title: Re: Oh No! Not Another Fork in the Road
Post by towr on Aug 9th, 2006, 2:15pm
Hmm.. I've got the feeling I should know this from somewhere..
Something like [hide]put them all in a circle and ask each villager if the next is a liar[/hide]. But what if anything to do next..
Title: Re: Oh No! Not Another Fork in the Road
Post by Trebla on Aug 10th, 2006, 11:10am
Identifying a truthteller may not be enough...

"what is the road to the truth-telling village?" creates ambiguity as there are two truth-telling villages.  If you get pointed back the way you came, that doesn't help.  You may need to identify multiple truthtellers, and even then it doesn't guarantee that all of them wouldn't point back the way you came...
Title: Re: Oh No! Not Another Fork in the Road
Post by BNC on Aug 10th, 2006, 12:28pm

on 08/10/06 at 11:10:11, Trebla wrote:
Identifying a truthteller may not be enough...

"what is the road to the truth-telling village?" creates ambiguity as there are two truth-telling villages.  If you get pointed back the way you came, that doesn't help.  You may need to identify multiple truthtellers, and even then it doesn't guarantee that all of them wouldn't point back the way you came...


Changed section 7 to address point. The intended problem is identifing the truth-teller.
Title: Re: Oh No! Not Another Fork in the Road
Post by ChunkTug on Aug 10th, 2006, 7:47pm
Forgive me. I'm tired and the ability to form a complete sentence is failing me. That said, here's my solution.

[hideb]
Have every body pair up (odd man out considered later). For each pair ask them if the other is a Liar. If they both answer "No" they make it to the next round. Have everybody shift over one partner. Repeat until you get an iteration where you eliminate nobody.

Exceptions:
If on the first round you eliminate nobody, shift once and continue.
TTL
TTL

Odd man out:
If you ever eliminate everybody. Then choose the odd man out.
TTTT   T
LLLL
[/hideb]
Title: Re: Oh No! Not Another Fork in the Road
Post by BNC on Aug 11th, 2006, 8:26am

on 08/10/06 at 19:47:31, ChunkTug wrote:
Forgive me. I'm tired and the ability to form a complete sentence is failing me. That said, here's my solution.

[hideb]
Have every body pair up (odd man out considered later). For each pair ask them if the other is a Liar. If they both answer "No" they make it to the next round. Have everybody shift over one partner. Repeat until you get an iteration where you eliminate nobody.

Exceptions:
If on the first round you eliminate nobody, shift once and continue.
TTL
TTL

Odd man out:
If you ever eliminate everybody. Then choose the odd man out.
TTTT   T
LLLL
[/hideb]



You're on the right track. Note, though, that your method may run through all of the Liars-pairs before actually working, which will take longer than optimum.

Look for a way to minimize the number of questions in the worst case.
Title: Re: Oh No! Not Another Fork in the Road
Post by Roy on Aug 14th, 2006, 3:31am
I'm thinking of an answer and I've got an idea, but i may need a little longer, it goes for a bit too long
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Aug 23rd, 2006, 9:38am
Building on ChunkTug's idea:

[hideb]
Set aside a chair.  Pair up the villagers, and if there is an odd man out, he should sit in the chair.  Ask each member of the pair if the other is a liar.  Their answers will either be NN or not NN.

If the pair answers anything other than NN, they are both set aside and will not be questioned further.  If they answer NN, then one of them is set aside but the other is asked to stay for further questioning.

Repeat this process.  Pair up the remaining villagers.  Any odd man out should sit in the chair (if the chair is currently occupied, the current occupant should vacate it and go with the rest of the villagers who have been set aside).  Each member of the pair is asked if the other is a Liar.  Pairs answering anything other than NN have both members set aside, and pairs answering NN have one member set aside and one remains for further questioning.

Continue this until there is only the person in the chair left.  Present this person with the envelope; you will get a truthful answer.
[/hideb]
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Aug 23rd, 2006, 10:05am
Some hints:

1. [hide]Suppose there are three villagers, A, B, and C.  You ask A if B is a Liar and he says "Yes."  Is this enough information to identify a truth-teller?[/hide]

2. [hide]Suppose there are three villagers, A, B, and C.  You ask A if B is a Liar and he says "No."  Is this enough information to identify a truth-teller?[/hide]

3. [hide]Suppose there are three villagers, A, B, and C.  You ask A if B is a Liar and he says "No."  Next you ask B if A is a Liar and he says "No."  Is this enough information to identify a truth-teller?[/hide]

4. [hide]Suppose there are 1007 villagers, and you've deduced that among the first thousand there are at least 500 Liars.  Furthermore, you know that villagers 1001 through 1004 are the "same" (either all Truth-tellers or all Liars).  Is this enough information to identify a truth-teller?[/hide]
Title: Re: Oh No! Not Another Fork in the Road
Post by BNC on Aug 29th, 2006, 3:41am
A smal note / hint:
[hide]
If there are N people (liars + truthtellers together) at the fork, only N-1 question are required to find a truthteller.
[/hide]
Title: Re: Oh No! Not Another Fork in the Road
Post by Barukh on Aug 29th, 2006, 6:53am
How about this?

[hide]In every pair, ask only one question. If the answer is "No",  keep the other person. If the answer is "Yes", eliminate both.[/hide]
Title: Re: Oh No! Not Another Fork in the Road
Post by BNC on Aug 29th, 2006, 7:12am
Can you elaborate? How do you find the truthteller? Do continue the described procedure until just one remains?
Title: Re: Oh No! Not Another Fork in the Road
Post by Eigenray on Aug 29th, 2006, 6:12pm

on 08/29/06 at 06:53:01, Barukh wrote:
How about this?

Trying a few examples shows that it matters very much exactly how you do the pairing.  I finally came up with a solution -- but then saw it was identical to joefendel's, except for the trivial observation that [hide]you only need to ask one from each pair[/hide].

Anyway, the reason why it works:
[hideb]At any given point in time, either (1) there are more truthers than liars standing, or (2) there are the same of each standing and a truther sitting.  Both elimination and rechairing preserve this (though in rechairing, we might switch between (1) and (2)).  And at the end, 0 are standing, so we're in case (2).[/hideb]
Title: Re: Oh No! Not Another Fork in the Road
Post by BNC on Aug 30th, 2006, 1:10am
Assume that you have 2K truthtellers and 2K-1 liars. By chance, you pick a liar to sit in the chair. By further chance, you pair up liars with liars ans truthtellers with truthtellers.

Now you have a liar in the chair, K truthteller pairs, and 2K-1 liar pairs. After questioning, you'll get K truthtellers (1 of each pair removed) and K-1 liar + 1 liar in the chair. So you no longer have truthtellers majority.
Title: Re: Oh No! Not Another Fork in the Road
Post by Barukh on Aug 30th, 2006, 3:31am

on 08/29/06 at 07:12:25, BNC wrote:
Can you elaborate? How do you find the truthteller? Do continue the described procedure until just one remains?

I cannot  :-X

I realized too late that this approach won't work.
Title: Re: Oh No! Not Another Fork in the Road
Post by Eigenray on Aug 30th, 2006, 1:31pm

on 08/30/06 at 01:10:51, BNC wrote:
After questioning, you'll get K truthtellers (1 of each pair removed) and K-1 liar + 1 liar in the chair. So you no longer have truthtellers majority.

But it's okay because the guy in the chair is distinguished, and the only time you lose a strict truthteller majority is when a liar is seated, in which case there's a strict truthteller majority among those standing.  And if that happens, the guy currently in the chair will always end up being replaced.  In more detail:
[hideb]Claim: At any stage, either (1) there are more truthers than liars standing, or (2) there are the same of each standing and a truther sitting.

-This is true at the beginning (nobody sitting).
-If there's an odd number T+F standing, then T>=F implies T>F.  If we seat a truthteller, we'll either be in case (1) or (2) since (T-1)>=F.  If we seat a liar, we'll be in case (1).
-If there are x TT pairs, y TF/FT pairs, and z FF pairs standing, then after questioning, the number of truthtellers/liars standing goes from (2x+y, y+2z) -> (x,z).  Hence (1) or (2) holds afterwards iff (1) or (2), respectively, held before.
-At the end, nobody is standing, so we must be in case (2).[/hideb]
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Aug 30th, 2006, 1:45pm

on 08/29/06 at 18:12:34, Eigenray wrote:
Trying a few examples shows that it matters very much exactly how you do the pairing.  I finally came up with a solution -- but then saw it was identical to joefendel's, except for the trivial observation that [hide]you only need to ask one from each pair[/hide].


Not so trivial, Eigenray.  Well, at least I missed it!  But you're absolutely right - [hide]asking the second member of the pair is not necessary.[/hide]  It's funny - when I posted my "hints" I really thought the answer to the second hint was "No," but of course the answer is "Yes."  If I had only solved my own hints correctly, I might have found the optimal solution!
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Aug 30th, 2006, 1:53pm

on 08/30/06 at 13:31:36, Eigenray wrote:
[hideb]-If there are x TT pairs, y TF/FT pairs, and z FF pairs standing, then after questioning, the number of truthtellers/liars standing goes from (2x+y, y+2z) -> (x,z)[/hideb]


This isn't quite right, since Liars are allowed to be truthful.  But [hideb]let v be the number of Liars who are truthful about their partner being a Liar and w be the number of Liars who are truthful about their partner being a Truth-teller.  

Then (2x + y, y+2z) -> (x+w, z-v).  And since 2x+y >= y+2z, then x >= z, so x+w >= z-v.  In other words, Liars actually never help their case by telling the truth!
[/hideb]
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Aug 30th, 2006, 2:03pm

on 08/29/06 at 03:41:45, BNC wrote:
A smal note / hint:
[hide]
If there are N people (liars + truthtellers together) at the fork, only N-1 question are required to find a truthteller.
[/hide]


I disagree.  Given Eigenray's optimization of my solution, I think only [hide]N-2[/hide] questions are needed!  But this upper bound can surely be improved.  For example, with 4 villagers, only [hide]1[/hide] questions are necessary to identify a truthteller.
Title: Re: Oh No! Not Another Fork in the Road
Post by Eigenray on Aug 30th, 2006, 4:24pm

on 08/30/06 at 13:53:30, joefendel wrote:
This isn't quite right, since Liars are allowed to be truthful.  But

Heh.  Actually, I have to admit that in the 3 weeks since reading the problem, I had forgotten that liars were allowed to tell the truth :-[.  So my solution is not nearly as clever as it seems -- just lucky.
Title: Re: Oh No! Not Another Fork in the Road
Post by Icarus on Aug 30th, 2006, 6:59pm

on 08/30/06 at 13:53:30, joefendel wrote:
In other words, Liars actually never help their case by telling the truth!


Which, by rule (5), means that they will choose to lie every time, so Eigenray's lapse of memory was correct after all! Another freedom proves to be illusory.
:'(

Well done, you two!
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Aug 31st, 2006, 12:44pm

on 08/30/06 at 14:03:05, joefendel wrote:
I disagree.  Given Eigenray's optimization of my solution, I think only [hide]N-2[/hide] questions are needed!  But this upper bound can surely be improved.  For example, with 4 villagers, only [hide]1[/hide] questions are necessary to identify a truthteller.


I'm now intrigued with this minimal questions problem.  How many questions are necessary with N villagers to identify the truth-teller?

With 1 or 2 villagers, clearly 0 questions are required - knowing that the truth-tellers are in the majority means that anyone there is a truth-teller.

For N > 2 villagers, I'm finding the following formula:
[hideb]
The minimum number of questions is N-F, where F is either 2 or 3, and is obtained by writing (N-1) out in binary, and setting F equal to the first two digits.  So if N is 7, for example, then N-1 is 6 = 110 (binary), so F=11 (binary) = 3.  So 4 questions are necessary to identify a truth-teller from among 7 villagers.
[/hideb]

That this is a sufficient number of questions can probably be proven by induction on N.  That it may be necessary to ask this many is harder.

Correction: I'm totally wrong.  It's more complicated than this.
Title: Re: Oh No! Not Another Fork in the Road
Post by Deedlit on Sep 1st, 2006, 7:27am
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.
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Sep 1st, 2006, 8:35am

on 09/01/06 at 07:27:09, 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.
[hideb]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.
[/hideb]
Title: Re: Oh No! Not Another Fork in the Road
Post by Deedlit on Sep 1st, 2006, 8:52am

on 09/01/06 at 08:35:39, joefendel wrote:
I don't understand.
[hideb]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?[/hideb]


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?
Title: Re: Oh No! Not Another Fork in the Road
Post by joefendel on Sep 1st, 2006, 10:54am

on 09/01/06 at 08:52:39, 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:

[hideb]If there are an even number of villagers, begin the process by sending one away so that you have an odd number.[/hideb]

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!
[hideb]
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.
[/hideb]

But I still don't have a proof that modified p&c is optimal.
Title: Re: Oh No! Not Another Fork in the Road
Post by BNC on Sep 1st, 2006, 10:37pm
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.
Title: Re: Oh No! Not Another Fork in the Road
Post by Deedlit on Sep 2nd, 2006, 12:57am
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.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board