SoylentNews is people
SoylentNews
I just happened to see this story appear in our #rss-bot feed. How to Solve the World's Hardest Logic Puzzle. Given that this is the weekend, I thought it might make for an interesting challenge and discussion.
To set the stage for the puzzle, the author provides some background on Raymond Smullyan, the puzzle's composer:
While a doctoral student at Princeton University in 1957, studying under a founder of theoretical computer science, Raymond Smullyan would occasionally visit New York City. On one of these visits, he met a "very charming lady musician" and, on their first date, Smullyan, an incorrigible flirt, proceeded very logically—and sneakily.
"Would you please do me a favor?" he asked her. "I am to make a statement. If the statement is true, would you give me your autograph?"
Content to play along, she replied, "I don't see why not."
"If the statement is false," he went on, "you don't give me your autograph."
"Alright ..."
His statement was: "You'll give me neither your autograph nor a kiss."
It takes a moment, but the cleverness of Smullyan's ploy eventually becomes clear.
A truthful statement gets him her autograph, as they agreed. But Smullyan's statement, supposing it's true, leads to contradiction: It rules out giving an autograph. That makes Smullyan's statement false. And if Smullyan's statement is false, then the charming lady musician will give him either an autograph or a kiss. Now you see the trap: She has already agreed not to reward a false statement with an autograph.
With logic, Smullyan turned a false statement into a kiss. (And into a beautiful romance: The two would eventually marry.)
Clever! But enough with the setup — What's the puzzle?
The Hardest Logic Puzzle Ever goes like this:
Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for "yes" and "no" are "da" and "ja," in some order. You do not know which word means which.
The story's author is, himself, a bit of a puzzle-poser. The story tells how to solve the puzzle, but does not actually provide the solution. Are there any Soylentils up to the challenge?
(Score: 1) by jsdfk on Monday October 24 2016, @11:50AM
Disclaimer : could be wrong
We have 3 gods T (True), F (False) and R (Random).
As we don't know which god is which, let's assign identifiers to them : A, B and C.
The gods answer in their own language, where ja and da mean yes and no, not necessarily in this order.
Problem overview
----------------
We have to find which god is which. We have to find a mapping between
( A, B, C ) and ( T, F, R ). We have the following 6 options :
(I)
A B C
T F R 1
T R F 2
F T R 3
F R T 4
R T F 5
R F T 6
We can ask the gods 3 questions, on each we get an answer ja or da.
This means that we can get in total 8 different sets of answers ( 2^3 = 8, ja/da 3 times ).
We also don't know the mapping between ja / da and yes / no :
(II)
1) da = yes, ja = no
2) da = no, ja = yes
From this alone we can see that if we want to determine the mapping ja/da to yes/no
as well as the mapping (I) (6x2=12 possibilities), we don't have enough questions
(with 3 questions we can distinguish between 8 possibilities).
Therefore our solution will not include the mapping ja/da to yes/no.
Part 1 : eliminating da/ja mapping problem
------------------------------------------
Let's suppose we ask one god X a question of type
( Q if and only if "ja" means "yes" in your language ).
The result, presuming the god will answer truthfully :
Q ("da=="yes") (Q iff "da"=="yes") word we hear
T T T da
T F F da
F T T ja
F F T ja
iff means if and only if, Q is an arbitrary question.
Therefore by asking the god (Q iff da==yes) we hear da exactly when Q is true.
Using this we can eliminate the problem of not knowing the mapping (II),
simply by asking (Q iff "da"=="yes) instead of just asking Q.
Part 2 : deducing truth from an answer by a T/F god
---------------------------------------------------
If we are talking to a god that is either T or F, how do we learn the truth ?
By asking ( Q iff (you are T god) ) we get the following truth table :
Q (you are T) (Q iff (you are T)) (answer we hear)
T T T T (tells the truth)
T F F T (lies)
F T F F (truthfully)
F F T F (lies)
Therefore by asking (Q iff (you are T)) we can determine the truth of the statement Q.
In combination with part 1, this means that we will have to ask :
( Q if and only if you are T ) if and only if "da" means "yes"
and will hear "da" from a god that is T or F exactly when our question Q is true.
Part 3 : Solution
-----------------
Lets define our question Q'( i, j, k, ..., n ) as :
Q'( i, j, ..., n ) :
is it true that at leas one of the following statements is true :
- You identities are as describe in table (I), row i
- You identities are as describe in table (I), row j
- ...
- You identities are as describe in table (I), row n
and Q( i, j, ..., n ) as :
Q( i, j, ..., n ) = ( Q' iff you are T ) iff ( "da" == "yes" )
By asking a T/F god a question Q( i, j, k ) we will therefore determine the following :
- if he answers "da", we will know that only possibilities (i,j and k) in our table are possible
- if he answers "ja", we will know that possibilities (i,j and k) are not possible
Solution :
Ask god A question Q( 1, 3, 5 ).
If he answers "da", we know that only options 1, 3, and 5 are possible, __if he is a T/F god__.
In that case god B can not be R. If god A is R, then his answer doesn't matter, and god B can not be R as well.
We ask god B question Q( 1, 2, 3 ) :
- answers "da" : ask god B question Q( 1 ) :
- answers "da" : option 1 in table
- answers "ja" : option 3 in table
- answers "ja" : ask god B question Q( 5 ) :
- answers "da" : option 5 in table
- answers "ja" : option 6 in table
If A answers with "ja" in the first case, proceed similarly by asking C similar questions.
(Exercise left to the reader)