Sunday, May 11, 2014

Truth AND Lies

Problems

1.When a person has to find out which of the two paths lead to his destination and there are two guys sitting there, one of which always speaks the truth and the other always lies. What is the single question he can ask to reach his aim?

2.There are two ways (like previous question). One right and the other wrong. But there are 3 guys. One will always speak the truth or keep mum(if he does not know the answer). One will always lie or keep mum(if he does not know the answer). The third will never keep mum and may speak the truth or lie with equal probability. You can ask two questions. Find out your destination.

3.There are three people named Larry, Curly and Moe. One always tells the truth, one always tells a lie and the other gives unpredictable answers, but all of them can only answer yes or no questions (with yes or no). Like any classic Smullyan puzzle (from whom I believe this problem originates), the goal is to ask a certain number of questions to figure out who is who. In this case, the three know who is which and now you are allowed three yes or no questions (each directed to only one of the three at a time) to figure it out for yourself. How's do you do it?

4.You are now quite definitely talking to True, but he refuses to
answer you in English and will only say da or ja. What one yes-no question can you
ask True to determine whether or not Dushanbe is in Kirghizia?

5.Suppose that, somehow, you have learned that you are speaking not
to Random but to True or False — you don’t know which — and that whichever
god you’re talking to has condescended to answer you in English. For some reason,
you need to know whether Dushanbe is in Kirghizia or not. What one yes-no
question can you ask the god from the answer to which you can determine whether
or not Dushanbe is in Kirghizia

Solution

SOLUTION FOR 1------------------
He asks to any one "What would the other guy say if I ask him the direction to my address?" and take the opposite of the answer he gets.

SOLUTION FOR 2------------------
Idea - In the first question you should be able to eliminate the random guy; so that you are sure that next question you ask is asked to either of TURE or FALSE guy.

Idea2 - The second question should be asked to one guy and only in his context...

Question1. Is B more likely to tell the truth than C. If the answer is YES choose C else choose B.

Now let's consider all the possible cases in this scenario

A B C
----------------
T T/F F (Expected Ans=YES, A's answer = YES; CHOSEN=C.)
T F T/F (Expected Ans =NO, A's answer = NO; CHOSEN=B.)
------------------
F T/F T (Expected Ans=No, A's answer = YES(since A is liar); CHOSEN=C)
F T T/F (Expected Answer=Yes, A's answer=NO(since A is liar); CHOSEN=B
--------------------
T/F T F
T/F F T
In the above 2 cases you would have chosen any of B and C it doesn't matter since they would be either T or F

Conclusion from Question 1- We are always getting CHOSEN guy as either T or F guy so in the first question we have removed the chance of RANDOM to be the second guy whom we ask).

Question2.Are you TRUE iff(if and only if) This is the correct path.

let's call
Are you TRUE as Stmt1
This is correct Path as Stmt2.

Remember how iff works..it would be TRUE if both the statements in between iff is put are TRUE or BOTH are false..if one is TRUE and the other is FALSE then iff would be FALSE...

Consider all the possible cases since our CHOSEN guy can be either of TRUE or FALSE so the following four cases.

Case1. True guy and CorrectPath = Both Satement's (Stmt1 and Stmt2)are TRUE so Answer = YES

Case2. True guy and IncorrectPath=
(Stmt1 is TRUE and Stmt2 is FALSE)
so Answer = NO

Case3. False guy and CorrectPath=
(Stmt1 is False and Stmt 2 is True)..Expected Answer = NO, but he guy whose replying is a liar so ANSWER= YES

Case4. False guy and IncorrectPath=
(Stmt1 is False and Stmt2 is False)..Expected Ans= YES, but liar will say ANSWER=NO.

Now from above Case1..4 we see that if we get a YES for Question2 we take that path else we take the opposite path..will always help us get the right path.

SOLUTION FOR 3-----------------------
T = truth guy
F = false guy
R = random guy

our guys A B C
ask the same first question to know who is the guy which is definitely not the random guy.. say A

so A is T/F

now ask A "Is B more likely to say the truth than C"
===============
if ans is "yes"

if A = T B=R C=F
if A = F B=R C=T
==============
if ans is "no"

if A = T B=F C=R
if A = F B=T C=R

so if A answers yes B is the random guy else C is the random guy

once we know who is random ask the third question to any of the other 2 guys.

the 3rd question should be an obvious question like "is 2+3=5?"

if the guy answers "yes" he is T else F ----------------

References

0 comments:

Post a Comment