wu :: forums - Print Page


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

        riddles >> hard >> Fork in The Road (again)
        
(Message started by: VictorSand on Dec 22^nd, 2003, 5:58am)

Title: Fork in The Road (again)
Post by VictorSand on Dec 22^nd, 2003, 5:58am

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?

Title: Re: Fork in The Road (again)
Post by TimMann on Dec 22^nd, 2003, 11:54pm

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.

Title: Re: Fork in The Road (again)
Post by Margit on Dec 23^rd, 2003, 1:18am

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. ;D

Title: Re: Fork in The Road (again)
Post by James Fingas on Dec 23^rd, 2003, 4:34am

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.

Title: Re: Fork in The Road (again)
Post by VictorSand on Dec 23^rd, 2003, 5:58am

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 ::[hide]Pointed out which of the elves that was the "randomizer"[/hide]

Title: Re: Fork in The Road (again)
Post by rmsgrey on Dec 23^rd, 2003, 9:33am

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)

Title: Re: Fork in The Road (again)
Post by Icarus on Dec 23^rd, 2003, 4:32pm

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.

Title: Re: Fork in The Road (again)
Post by TimMann on Dec 23^rd, 2003, 7:19pm

Hmm, yes, I was full of beans.

:[hide]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?"[/hide]:

I think we've seen this problem before too.

Title: Re: Fork in The Road (again)
Post by VictorSand on Dec 24^th, 2003, 3:46am

Sorry if this has been up before. I really tried to search for it :/

Title: Re: Fork in The Road (again)
Post by Icarus on Dec 24^th, 2003, 7:55am

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1064263223). 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.

Title: Re: Fork in The Road (again)
Post by Padzok on Sep 4^th, 2004, 3:17am

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:

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

Title: Re: Fork in The Road (again)
Post by rmsgrey on Sep 6^th, 2004, 6:36am

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)

Title: Re: Fork in The Road (again)
Post by Mayank on Oct 11^th, 2004, 9:34am

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.

Title: Re: Fork in The Road (again)
Post by Icarus on Oct 11^th, 2004, 7:45pm

Label the elves A, B, C. Then: [hide]
(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?"
[/hide]

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.

Title: Re: Fork in The Road (again)
Post by Padzok on Oct 12^th, 2004, 4:06pm

One question is enough.

Hint:

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

Title: Re: Fork in The Road (again)
Post by Icarus on Oct 12^th, 2004, 5:08pm

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.

Title: Re: Fork in The Road (again)
Post by Mayank on Oct 13^th, 2004, 7:10am

on 10/11/04 at 19:45:48, 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.

Title: Re: Fork in The Road (again)
Post by rmsgrey on Oct 13^th, 2004, 7:59am

on 10/13/04 at 07:10:39, Mayank wrote:

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

Title: Re: Fork in The Road (again)
Post by Mayank on Oct 13^th, 2004, 8:19am

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"!!! :o

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)

Title: Re: Fork in The Road (again)
Post by rmsgrey on Oct 13^th, 2004, 12:14pm

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.

Title: Re: Fork in The Road (again)
Post by Icarus on Oct 13^th, 2004, 8:04pm

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.

Title: Re: Fork in The Road (again)
Post by Padzok on Oct 16^th, 2004, 12:22am

on 10/12/04 at 17:08:14, Icarus wrote:

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.

Title: Re: Fork in The Road (again)
Post by rmsgrey on Oct 16^th, 2004, 10:30am

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.

Title: Re: Fork in The Road (again)
Post by Earendil on Oct 16^th, 2004, 1:22pm

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?
[hide] 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. [/hide]

Title: Re: Fork in The Road (again)
Post by Three Hands on Oct 18^th, 2004, 6:12am

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

Title: Re: Fork in The Road (again)
Post by rmsgrey on Oct 18^th, 2004, 7:08am

I think we just say that their behaviour is undefined in situations where they don't know the truth, so, not knowing how they choose their responses, you can't deduce anything from them.

This sinks both the hidden and non-hidden questions.

Of course, if the "stupid" elf uses a deterministic method of determining whether to lie, which both other elves know, but you don't, then the hidden question is again sunk because everyone can answer, and you get either yes or no depending on the "stupid" guy's veracity at the time.

Title: Re: Fork in The Road (again)
Post by Padzok on Oct 18^th, 2004, 12:38pm

How about this?

[hide]If I asked you if the road on the left leads to "Paradise", and you happened to answer with the same degree of truth as you answer this question I'm asking now, would you answer 'YES'?

Say "Paradise" is to the left:

Truth-teller says "YES".

Liar, says, "YES".

Inconsistent elf, if answering this question truthfully says "YES" (because that is the truthful answer to the question "Does the road on the left lead to "Paradise" ?").

Inconsistent elf, if answering this question untruthfully says "YES" (because the truthful answer to the question "Does the road on the left lead to "Paradise" ? " is YES. If lying, he would have said "NO" to that question. So if lying in response to this question he would say "YES".).

[/hide]

Title: Re: Fork in The Road (again)
Post by rmsgrey on Oct 19^th, 2004, 8:51am

I'm not very happy about it, but I can't actually come up with anything wrong with that one. It seems to work (which is why I prefer the third elf to be completely random)