DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 14--------------------------------------------------
Please help this traveller inorder to find the correct route
By: kranthipls Date: August 12, 2012, 11:18 pm
---------------------------------------------------------
A traveler has to pass tests of increasing difficulty to meet an
Eastern mystical master. For the first test, he meets a pair of
twins at a fork in the road: one path leads to the jungle, the
other to the mystic. One of the twins always says the truth, the
other always lies. What yes/no question should you ask one of
the twins to determine the path that goes to the mystic?
#Post#: 15--------------------------------------------------
Re: Please help this traveller inorder to find the correct route
By: kranthipls Date: August 13, 2012, 10:03 am
---------------------------------------------------------
The answer to the above question is a very easy. The answer is:
"The traveler may ask, "Would your brother agree that the road
on the left leads to the mystic?" The answer is guaranteed to be
'Yes' if and only if the road on the right leads to the mystic."
But the traveller gets the much tougher position next. The next
test is
The traveler encounters another fork in the road. Again, one
path leads to the jungle, the other to the mystic. This time,
there are three look-alike brothers: one always tells the truth,
the second always lies but the third sometimes tells the truth
and sometimes lies. What two Yes/No questions should the
traveler ask two of the brothers to determine the path to the
mystic? Each question is answered by only the brother it is
posed to. For the second question, the traveler may choose the
brother and the question depending upon the answer to the first
question.
#Post#: 21--------------------------------------------------
Re: Please help this traveller inorder to find the correct route
By: dinesh Date: August 14, 2012, 10:34 am
---------------------------------------------------------
another answer to first question:
" what answer would your brother give if he were asked to tell
which way to go to the mystic? "
Follow the path other than the one answered. ( since in either
case the answer will be wrong )
#Post#: 43--------------------------------------------------
Re: Please help this traveller inorder to find the correct route
By: kranthipls Date: August 22, 2012, 10:17 am
---------------------------------------------------------
The answer for the second part of the question:
Actually i asked the solution only with two questions. But let
me give the solution with 4,3,2 questions.
Solutions to the three-brother problem:
With 4 questions: We first ask each brother, "Is one of the
other two inconsistent, i.e., sometimes tells the truth and
sometimes lies?" The truthful brother would say 'Yes', the lying
brother would say 'No'. The third brother might say 'Yes' or
'No. Interestingly, if the answers form the multi-set {'Yes',
'Yes', 'No'}, then the 'No' answer was certainly given by the
lying brother. If the answers form the multi-set {'Yes', 'No',
'No'}, then the 'Yes' answer was certainly given by the truthful
brother. No other multi-set of answers is possible. So the
fourth question may be posed appropriately to either the
truthful brother or the lying brother depending upon which
multi-set was observed.
With 3 questions: We ask the same question to all three, "Would
your consistent brother (who always tells the truth or always
tells lies, other than you) agree that the road on the left
leads to the mystic?" In response, the consistent brothers would
both say 'Yes' or both say 'No'. The inconsistent brother may
say either 'Yes' or 'No'. So the majority vote allows us
determine which road leads to the mystic.
With 2 questions: The key idea is to utilize the first question
to identify a consistent brother (who always speaks the truth or
always lies). The second question is posed to the brother just
identified — at this point, the problem is identical to the
2-brother problem. Let us label the brothers as #1, #2 and #3.
We shall use X to denote the brother whom we shall ask the
second question. Here are some possibilities for the first
question. In each case, if the answer is 'Yes', set X to #3,
otherwise set X to #2. Claim: X is consistent!
(devised by Ovidiu Gheorghioiu at Google) Ask #1 whether the
following logical proposition is true: ("You always tell the
truth" == "#2 gives random answers").
Ask #1, "Is #2 more likely to give the correct answer than #3?"
Ask #1, "If I were to ask you 'Is #2 consistent?', would you say
'Yes'?" Note that the 'if I were to ask you' construct makes
consistent brothers truthful!
The second question is posed to X (see the solution to the
2-brother problem). Either of the following suffices:
"Would your consistent brother agree that the road on the left
leads to the mystic?"
"If I were to ask you whether the road on the left leads to the
mystic, would you say 'Yes'?"
*****************************************************