wu :: forums
« wu :: forums - Oh No! Not Another Fork in the Road »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 5:01am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: SMQ, Icarus, ThudnBlunder, towr, Eigenray, Grimbal, william wu)
   Oh No! Not Another Fork in the Road
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Oh No! Not Another Fork in the Road  (Read 5416 times)
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Oh No! Not Another Fork in the Road  
« on: Aug 9th, 2006, 9:17am »
Quote Quote Modify Modify

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.
« Last Edit: Aug 10th, 2006, 4:31pm by Icarus » IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Oh No! Not Another Fork in the Road  
« Reply #1 on: Aug 9th, 2006, 9:22am »
Quote Quote Modify Modify

Pick up the next fork? Wink
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re: Oh No! Not Another Fork in the Road  
« Reply #2 on: Aug 9th, 2006, 11:13am »
Quote Quote Modify Modify

This can probably be improved upon -- depending on the number of villiagers an hour might not be enough time -- but it should work:
 
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.
 
--SMQ
IP Logged

--SMQ

BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Oh No! Not Another Fork in the Road  
« Reply #3 on: Aug 9th, 2006, 1:57pm »
Quote Quote Modify Modify

True, but a more efficient algorithm exist.
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Oh No! Not Another Fork in the Road  
« Reply #4 on: Aug 9th, 2006, 2:15pm »
Quote Quote Modify Modify

Hmm.. I've got the feeling I should know this from somewhere..
Something like put them all in a circle and ask each villager if the next is a liar. But what if anything to do next..
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Trebla
Newbie
*





   


Gender: male
Posts: 16
Re: Oh No! Not Another Fork in the Road  
« Reply #5 on: Aug 10th, 2006, 11:10am »
Quote Quote Modify Modify

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...
 
IP Logged
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Oh No! Not Another Fork in the Road  
« Reply #6 on: Aug 10th, 2006, 12:28pm »
Quote Quote Modify Modify

on Aug 10th, 2006, 11:10am, 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.
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
ChunkTug
Full Member
***






   


Gender: male
Posts: 166
Re: Oh No! Not Another Fork in the Road  
« Reply #7 on: Aug 10th, 2006, 7:47pm »
Quote Quote Modify Modify

Forgive me. I'm tired and the ability to form a complete sentence is failing me. That said, here's my solution.
 
hidden:

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
IP Logged
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Oh No! Not Another Fork in the Road  
« Reply #8 on: Aug 11th, 2006, 8:26am »
Quote Quote Modify Modify

on Aug 10th, 2006, 7:47pm, ChunkTug wrote:
Forgive me. I'm tired and the ability to form a complete sentence is failing me. That said, here's my solution.
 
hidden:

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

 
 
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.
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
Roy42
Senior Riddler
****






    ddhilltop2


Gender: male
Posts: 418
Re: Oh No! Not Another Fork in the Road  
« Reply #9 on: Aug 14th, 2006, 3:31am »
Quote Quote Modify Modify

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
IP Logged

Regards,

≈Roy42
Joe Fendel
Full Member
***





   


Posts: 158
Re: Oh No! Not Another Fork in the Road  
« Reply #10 on: Aug 23rd, 2006, 9:38am »
Quote Quote Modify Modify

Building on ChunkTug's idea:
 
hidden:

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.
« Last Edit: Aug 23rd, 2006, 9:52am by Joe Fendel » IP Logged
Joe Fendel
Full Member
***





   


Posts: 158
Re: Oh No! Not Another Fork in the Road  
« Reply #11 on: Aug 23rd, 2006, 10:05am »
Quote Quote Modify Modify

Some hints:
 
1. 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?
 
2. 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?
 
3. 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?
 
4. 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?
IP Logged
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Oh No! Not Another Fork in the Road  
« Reply #12 on: Aug 29th, 2006, 3:41am »
Quote Quote Modify Modify

A smal note / hint:

If there are N people (liars + truthtellers together) at the fork, only N-1 question are required to find a truthteller.
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Oh No! Not Another Fork in the Road  
« Reply #13 on: Aug 29th, 2006, 6:53am »
Quote Quote Modify Modify

How about this?
 
In every pair, ask only one question. If the answer is "No",  keep the other person. If the answer is "Yes", eliminate both.
IP Logged
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Oh No! Not Another Fork in the Road  
« Reply #14 on: Aug 29th, 2006, 7:12am »
Quote Quote Modify Modify

Can you elaborate? How do you find the truthteller? Do continue the described procedure until just one remains?
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Oh No! Not Another Fork in the Road  
« Reply #15 on: Aug 29th, 2006, 6:12pm »
Quote Quote Modify Modify

on Aug 29th, 2006, 6:53am, 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 you only need to ask one from each pair.
 
Anyway, the reason why it works:
hidden:
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).
IP Logged
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Oh No! Not Another Fork in the Road  
« Reply #16 on: Aug 30th, 2006, 1:10am »
Quote Quote Modify Modify

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.
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Oh No! Not Another Fork in the Road  
« Reply #17 on: Aug 30th, 2006, 3:31am »
Quote Quote Modify Modify

on Aug 29th, 2006, 7:12am, BNC wrote:
Can you elaborate? How do you find the truthteller? Do continue the described procedure until just one remains?

I cannot  Lips Sealed
 
I realized too late that this approach won't work.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Oh No! Not Another Fork in the Road  
« Reply #18 on: Aug 30th, 2006, 1:31pm »
Quote Quote Modify Modify

on Aug 30th, 2006, 1:10am, 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:
hidden:
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).
IP Logged
Joe Fendel
Full Member
***





   


Posts: 158
Re: Oh No! Not Another Fork in the Road  
« Reply #19 on: Aug 30th, 2006, 1:45pm »
Quote Quote Modify Modify

on Aug 29th, 2006, 6:12pm, 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 you only need to ask one from each pair.

 
Not so trivial, Eigenray.  Well, at least I missed it!  But you're absolutely right - asking the second member of the pair is not necessary.  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!
IP Logged
Joe Fendel
Full Member
***





   


Posts: 158
Re: Oh No! Not Another Fork in the Road  
« Reply #20 on: Aug 30th, 2006, 1:53pm »
Quote Quote Modify Modify

on Aug 30th, 2006, 1:31pm, Eigenray wrote:

hidden:
-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)

 
This isn't quite right, since Liars are allowed to be truthful.  But
hidden:
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!
IP Logged
Joe Fendel
Full Member
***





   


Posts: 158
Re: Oh No! Not Another Fork in the Road  
« Reply #21 on: Aug 30th, 2006, 2:03pm »
Quote Quote Modify Modify

on Aug 29th, 2006, 3:41am, BNC wrote:
A smal note / hint:

If there are N people (liars + truthtellers together) at the fork, only N-1 question are required to find a truthteller.

 
I disagree.  Given Eigenray's optimization of my solution, I think only N-2 questions are needed!  But this upper bound can surely be improved.  For example, with 4 villagers, only 1 questions are necessary to identify a truthteller.
« Last Edit: Aug 30th, 2006, 2:07pm by Joe Fendel » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Oh No! Not Another Fork in the Road  
« Reply #22 on: Aug 30th, 2006, 4:24pm »
Quote Quote Modify Modify

on Aug 30th, 2006, 1:53pm, 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 Embarassed.  So my solution is not nearly as clever as it seems -- just lucky.
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Oh No! Not Another Fork in the Road  
« Reply #23 on: Aug 30th, 2006, 6:59pm »
Quote Quote Modify Modify

on Aug 30th, 2006, 1:53pm, 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.
 Cry
 
Well done, you two!
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Joe Fendel
Full Member
***





   


Posts: 158
Re: Oh No! Not Another Fork in the Road  
« Reply #24 on: Aug 31st, 2006, 12:44pm »
Quote Quote Modify Modify

on Aug 30th, 2006, 2:03pm, joefendel wrote:

 
I disagree.  Given Eigenray's optimization of my solution, I think only N-2 questions are needed!  But this upper bound can surely be improved.  For example, with 4 villagers, only 1 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:
hidden:

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.

 
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.
« Last Edit: Aug 31st, 2006, 1:58pm by Joe Fendel » IP Logged
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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