Author |
Topic: Fork in The Road (again) (Read 3083 times) |
|
VictorSand
Newbie
Yeah!
 
Gender: 
Posts: 7
|
 |
Fork in The Road (again)
« on: Dec 22nd, 2003, 5:58am » |
 Quote  Modify
|
Willy comes to a two-way fork in the road. A sign says "Paradise" and one says "Endless road of hunger, thirst and pain". Since the arrows are gone, Willy doesn't know which way to go. Sitting on some stones at the side of the roads, are three elves. They all know the roads, but there is one problem.
One of the elves always tell the truth, and one always lies. "So far so good, thinks Willy." This would'nt be a problem if it weren't for the third elf. He is a elf that sometimes lies, and sometimes tell the truth. Never in any patterns, so you can't decide if he is telling the truth or not.
Willy has two questions. The question is of the yes/no kind and he can only speak to one elf at a time. How is he going to figure out which road to take?
|
|
 IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Fork in The Road (again)
« Reply #1 on: Dec 22nd, 2003, 11:54pm » |
Quote Modify
|
Maybe he could sit around and wait until the elves leave, then follow them.  There's no way to find out with only two questions unless he lucks out and doesn't happen to talk to the third elf.
Obviously I'm assuming that Willy doesn't know which elf is which. I'm also assuming that if Willy asks a question where the answer isn't well defined, he still gets only a yes or no (chosen at random). So no fair asking a question where the answer is undefined for the third elf and eliminating him because he can't say either yes or no.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Margit
Guest
|
|
Re: Fork in The Road (again)
« Reply #2 on: Dec 23rd, 2003, 1:18am » |
Quote Modify
 Remove
|
I think you can do it in one.
Point to a particular road and ask any elf -
"If I were to ask you if this road leads to Paradise, would you answer 'yes'?".
Assuming the road does indeed lead to paradise then :
The truth-teller would answer "yes".
The liar must also answer "yes" as answering "no" would be true.
The same applies to the partial liar. In either case, he must answer yes. 
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Fork in The Road (again)
« Reply #3 on: Dec 23rd, 2003, 4:34am » |
Quote Modify
|
Good point Margit, but perhaps the partial liar could still lie, because he could say to himself: "Yes, that is the road to paradise, and I will answer truthfully to this question, but if this traveler were to ask me, I might very well answer falsely."
This puzzle can still be solved in two questions easily, and might even be solvable in one question, but you'd have to make it a more complicated question than that.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
VictorSand
Newbie
Yeah!
Gender:
Posts: 7
|
|
Re: Fork in The Road (again)
« Reply #4 on: Dec 23rd, 2003, 5:58am » |
Quote Modify
|
I have actually solved this once, but I have forgotten the first question.  The second one is easy though. Do you know the questions James Fingas?
I think the first question was one that ::Pointed out which of the elves that was the "randomizer"
|
| « Last Edit: Dec 23rd, 2003, 6:00am by VictorSand » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2874
|
|
Re: Fork in The Road (again)
« Reply #5 on: Dec 23rd, 2003, 9:33am » |
Quote Modify
|
This puzzle has already appeared on this site under a different guise - I can't remember the details well enough, but the solution relies on establishing one person who can't be the random guy with your first question, then asking the standard question to that guy (if the guy you ask the first question to isn't the randomiser, you can establish which of the other two isn't either, and if he is the randomiser, then neither of the other two is, so whichever you pick is fine)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fork in The Road (again)
« Reply #6 on: Dec 23rd, 2003, 4:32pm » |
Quote Modify
|
It is similar to the one about the Muppets, but there one is incomprehensible, one alternates, and the third tells the truth (if I recall correctly). I don't recall a puzzle exactly the same as this, but then there are so many logic problems here now it is hard to keep track of all of them.
|
|
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
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Fork in The Road (again)
« Reply #7 on: Dec 23rd, 2003, 7:19pm » |
Quote Modify
|
Hmm, yes, I was full of beans.
:Let's call the elves A, B, C. Ask A "If I were to ask you whether B is the elf who randomly either tells the truth or lies, what would you say?" If A is either the truth teller or the liar, he will give you the correct answer, by the usual double-lie principle. If A was the randomizer, he'll give you a random answer. Now ask your next question of B if the first answer was "no", of C if it was "yes." This guarantees that your second question is not addressed to the randomizer. Ask "If I were to ask you whether this is the road to Paradise, what would you say?":
I think we've seen this problem before too.
|
| « Last Edit: Dec 23rd, 2003, 7:20pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
VictorSand
Newbie
Yeah!
Gender:
Posts: 7
|
|
Re: Fork in The Road (again)
« Reply #8 on: Dec 24th, 2003, 3:46am » |
Quote Modify
|
Sorry if this has been up before. I really tried to search for it :/
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fork in The Road (again)
« Reply #9 on: Dec 24th, 2003, 7:55am » |
Quote Modify
|
It's rather hard to search out problems when they are phrased entirely different, even though the logic for the answer is the same. This problem is essentially the same as the 3 computers. It only requests that you do the same thing you need to do with the first question here. But if you can figure that part out, the second question is a snap.
|
|
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
|
|
|
Padzok
Junior Member
Gender:
Posts: 104
|
|
Re: Fork in The Road (again)
« Reply #10 on: Sep 4th, 2004, 3:17am » |
Quote Modify
|
This actually be done with one question only.
Obviously the question needs to be such that either all 3 will say yes, or all 3 will say no.
You then know (in either case) what the truth-teller has answered, and thus know what the truthful answer to the question is.
I am new here and so I won't post the answer just now.
Here's a hint:
Before answering a given question, the random elf, R, has to work out what the truthful reply is, and what the untruthful reply is. There are some questions that it will be impossible for him to answer (eg "if my next question to you was "does 2+2 = 4?" would you say YES"). However, some questions which seem unanswerable at first glance, do, in fact, have proper answers.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Fork in The Road (again)
« Reply #11 on: Sep 6th, 2004, 6:36am » |
Quote Modify
|
The problem statement says that the "random" elf either tells the truth or lies without pattern, not that he uses a random number generator to decide. A good way to do that would be to use the standard elfin random number tables (to which Willy has never had any access) to give a stream of bits, each of which represents the truthfulness of an answer to a (sub-) question. That way, the elf can deal with complicated conditionals involving his future behaviour in hypothetical futures (even to the extent of producing different bit streams for different hypothetical futures - the elfin random number tables being a little mystical in nature)
|
|
IP Logged |
|
|
|
Mayank
Newbie
Posts: 18
|
|
Re: Fork in The Road (again)
« Reply #12 on: Oct 11th, 2004, 9:34am » |
Quote Modify
|
Does any one have an answer to this yet.
For all the answers already given in this Post, none of them is correct or satisfies the given situation.
The "Computers" problem as pointed out by Icarus I believe, does not apply to this and it is much simpler.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fork in The Road (again)
« Reply #13 on: Oct 11th, 2004, 7:45pm » |
Quote Modify
|
Label the elves A, B, C. Then:
(1) Ask A "Does B tell the truth more often than C"?
If A answers yes, pose your 2nd question to C.
If A answers no, pose your 2nd question to B.
(2) Ask "If I were to ask you if this road (point to one) leads to Paradise, what would your answer be?"
As I said in my earlier post, the three computers problem tells you how to identify a consistent responder (my first question above was James Fingas' solution to the three computers problem - my own solution would work as well). From that point, the same question that solves the single-questionee Fork in the Road problem may be used.
I.e., while the problem as a whole had not been posted before, it had already been solved in detail.
|
|
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
|
|
|
Padzok
Junior Member
Gender:
Posts: 104
|
|
Re: Fork in The Road (again)
« Reply #14 on: Oct 12th, 2004, 4:06pm » |
Quote Modify
|
One question is enough.
Hint:
The inconsistent elf cannot predict what he would do in the future, but he can answer questions (either by lying or telling the truth) which merely require him to say what would happen in certain hypothetical circumstances.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fork in The Road (again)
« Reply #15 on: Oct 12th, 2004, 5:08pm » |
Quote Modify
|
That is a matter of interpretation. I think the intent here is that the third elf answers randomly, so no information can be gleaned from his answer (consider the muppets variation, wherein the third respondent doesn't even understand the question). In this case, 2 questions are required, as you need one to determine a consistent elf, before you can ask the question whose answer you need.
If the third elf's answers are not random, then by appropriately manipulation of the rules by which he does answer, you can obtain useful information, so - depending on those rules - it may be possible to get by with a single question.
However, VictorSand specifically says that the third elf does not answer in any patterns. This seems to me to mean that his answers are random.
|
|
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
|
|
|
Mayank
Newbie
Posts: 18
|
|
Re: Fork in The Road (again)
« Reply #16 on: Oct 13th, 2004, 7:10am » |
Quote Modify
|
on Oct 11th, 2004, 7:45pm, Icarus wrote:Label the elves A, B, C. Then:
As I said in my earlier post, the three computers problem tells you how to identify a consistent responder (my first question above was James Fingas' solution to the three computers problem - my own solution would work as well). From that point, the same question that solves the single-questionee Fork in the Road problem may be used.
I.e., while the problem as a whole had not been posted before, it had already been solved in detail. |
|
Icarus.
Your question 2 doesnt solve the riddle.
Consider the elves to be A, B and C. Answer to Q1 be M and Q2 be N. Now the following will happen
A B C M N(if paradise)/(if not paradise)
L T R N Y/N
L R T Y Y/N
T L R N N/Y
T R L Y N/Y
R T L - -
R L T - -
So you see the first question ascertains who answers absolute , but the second question gets two different responses (which will not help). Even the classic question of 2 Elve riddle will not fit the bill as we do not know for sure who the randomizer is.
The only thing we know is one of the absolute answering elf.
|
| « Last Edit: Oct 13th, 2004, 7:11am by Mayank » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Fork in The Road (again)
« Reply #17 on: Oct 13th, 2004, 7:59am » |
Quote Modify
|
on Oct 13th, 2004, 7:10am, Mayank wrote:
Icarus.
Your question 2 doesnt solve the riddle.
Consider the elves to be A, B and C. Answer to Q1 be M and Q2 be N. Now the following will happen
A B C M N(if paradise)/(if not paradise)
L T R N Y/N
L R T Y Y/N
T L R N N/Y
T R L Y N/Y
R T L - -
R L T - -
So you see the first question ascertains who answers absolute , but the second question gets two different responses (which will not help). Even the classic question of 2 Elve riddle will not fit the bill as we do not know for sure who the randomizer is.
The only thing we know is one of the absolute answering elf. |
|
For your 3rd and 4th rows, I get Y/N for the last column in both cases (If I were to ask the lying elf whether "that road" leads to paradise, he would lie and say N/Y, but because I ask him what his answer would be to that question, he lies about his answer so answers Y/N)
With that in mind, you can replace the last two rows with 2 rows each (one where R answers Y; one N), but in each case you get the same answers to the second question - because you ask a consistent answerer a question that would solve the 2 Elf variant.
The key to the problem is that the first question enables you to guarantee your second question isn't asked to R...
|
|
IP Logged |
|
|
|
Mayank
Newbie
Posts: 18
|
|
Re: Fork in The Road (again)
« Reply #18 on: Oct 13th, 2004, 8:19am » |
Quote Modify
|
hmmm. I was ok with the last two rows. It was the second question which confused me.
Question 2: If I were to ask you if this road leads to paradise, what would your answer be.
The "T" elf will answer correctly (and say Yes/No)
Now assume the road goes to paradise.
So correct answer is "Y"
The correct answer for Liar would be "N"
But since I am asking the liar what would his answer be he will lie (to his correct answer) and answer "Y"!!! 
Or can the liar just lie about the road and say "N"?
The answer to the question does'nt seem definite to me, even though it makes sense. (or maybe I am thinking too much)
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Fork in The Road (again)
« Reply #19 on: Oct 13th, 2004, 12:14pm » |
Quote Modify
|
The usual assumption is that the liar is an honest one - that he tells the exact opposite of the truth every time. Since the question is about his answer in a hypothetical situation, he will lie honestly about it.
You can get into interesting tangles if you assume a more artistic liar, whose sole intention is to decieve, but essentially you arrive at the conclusion that such a liar can always trick you.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fork in The Road (again)
« Reply #20 on: Oct 13th, 2004, 8:04pm » |
Quote Modify
|
Yes. The 2nd question is the solution to the "Fork in the Road II" riddle, where there is only one person at the crossroad, who is either a truth teller or a liar.
The Liar must, by the description, give the opposite answer from the one he knows to be true. The question asked gets around this because it is a "metaquestion": a question about the answer to a hypothetical question. The Liar must lie about his answer to the hypothetical question, with the result that his actual lie and hypothetical lie cancel out, leaving the truth.
Let me change the question slightly (the original form leaves a door open for the liar to answer something other than yes or no).
The 2nd question should be some form of "If I were to ask you 'is this the road to paradise', would you agree that it was?".
If the road chosen really is the road to paradise, the Liar would say "no" to the hypothetical question. So his answer to the actual question must be "yes", just like the truthteller's.
If the road chosen really is the road to pain, the Liar would say "yes" to the hypothetical question. So his answer to the actual question must be "no", just like the truthteller's.
|
| « Last Edit: Oct 13th, 2004, 8:04pm by Icarus » |
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
|
|
|
Padzok
Junior Member
Gender:
Posts: 104
|
|
Re: Fork in The Road (again)
« Reply #21 on: Oct 16th, 2004, 12:22am » |
Quote Modify
|
on Oct 12th, 2004, 5:08pm, Icarus wrote:That is a matter of interpretation. I think the intent here is that the third elf answers randomly, so no information can be gleaned from his answer (consider the muppets variation, wherein the third respondent doesn't even understand the question). In this case, 2 questions are required, as you need one to determine a consistent elf, before you can ask the question whose answer you need.
If the third elf's answers are not random, then by appropriately manipulation of the rules by which he does answer, you can obtain useful information, so - depending on those rules - it may be possible to get by with a single question.
However, VictorSand specifically says that the third elf does not answer in any patterns. This seems to me to mean that his answers are random. |
|
Icarus, VictorSand said:
Quote:| elf that sometimes lies, and sometimes tell the truth. Never in any patterns, so you can't decide if he is telling the truth or not. |
|
which is subtly different from answering randomly.
In other words, he does not choose, at random, either to say "yes" or to say "no".
He does choose (at random) either to answer truthfully, or to lie.
So long as we believe the liar will always say the opposite of the truth, and so long as we believe the third elf will do the same when lying, it is possible to ask just one meta-question which will uniquely determine the right route.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Fork in The Road (again)
« Reply #22 on: Oct 16th, 2004, 10:30am » |
Quote Modify
|
Could you give an example of such a meta-question? "If I were to ask you..." doesn't work reliably, because the elf could lie about his truthful answer to such a question - or tell the truth about his false answer.
|
|
IP Logged |
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: Fork in The Road (again)
« Reply #23 on: Oct 16th, 2004, 1:22pm » |
Quote Modify
|
What happens if I ask them a question and they can't know if it is true or false, i.e., if I trow a coin, will it face heads?
Why did I ask this?
Ask elf A: Would B's answer to the question: "Would C's answer to the question: "Is 2+2 = 4?" be yes?" be yes? Only if A is the "stupid" elf would he be able to say anything.
|
| « Last Edit: Oct 16th, 2004, 1:24pm by Earendil » |
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: Fork in The Road (again)
« Reply #24 on: Oct 18th, 2004, 6:12am » |
Quote Modify
|
Why do I get the feeling I'm going to end up going cross-eyed again? 
OK, for the hidden question, if A is not the "stupid" elf, then at some point in the chain the other two run into the difficulty of guessing what "stupid" elf would answer, and so would presumably sulk, or something like that (or know what "stupid" elf was going to say, and so provide you with absolutely no information whatsoever about who's who). Given you only have the two questions, establishing that elf A is/is not "stupid" seems not to provide sufficient information to guarantee getting the answer you want.
As for the non-hidden question, I would imagine that two possibilities exist. A) Only "stupid" elf responds, since he's the only one who doesn't care what the question is, or B) All the elves would respond (due to elves having mystic abilities to know everything) but you would only be able to state that they are (T EXOR F) or "stupid", based on the subsequent result of the coin-flip in said example. Again, seems to me to provide insufficient information.
Of course, if they were always forced to respond, and B did not apply, then we run into paradoxical situations where the answers true elf and false elf give do not necessarily follow their nature, and the universe collapses with me having gone cross-eyed in the process of trying to work out the paradox - personally, I don't like this theory, though...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print