Tan Kin Lian's Blog: Toughest Puzzle

Wednesday, March 24, 2010

Toughest Puzzle - Who tells the truth?

This is labelled by www.ft.com as the toughest puzzle of all times. But it is not so difficult after all, as I was able to solve it. Read the comments for my solution.

There are three guardians, A, B and C. Their ames are Knight, Knave and Chaos. Knight always speaks truly, Knave always lies. Chaos tossed a coin this morning to decide whether today he would behave like Knight or like Knave.
Your task is simple: ask three yes-no questions, each of a single guardian, and determine which is Knight, which is Knave, and which is Chaos. There is, alas, a complication: the guardians understand English but will answer in the local language, in which “Da” means yes and “Ja” means no. Or possibly “Ja” means yes and “Da” means no – you cannot remember.

9 comments:

Tan Kin Lian said...: This is labelled as the toughest puzzle of all times. I had a lot of difficulty figuring out the logic. It seems that nobody knows the answer.; March 20, 2010 8:57 PM
Tan Kin Lian said...: It is not clear, but it seems that you will be asking 3 questions for each person, i.e. total of 9 questions.

Scenario 1:
The first question is "Are you Knight?". If all three answer the same, you know that Chaos had decided to tell a lie and their answer means "yes".

The next question is "are you Chaos". The person who answer "yes" is Knave.

The third question is, "Are you Knave?" Of the remaining two, the one who answer "yes" is Chaos and the other person is Knight.

Scenario 2:
The first question is "Are you Knight?". If only two of them give the same answer, you know that Chaos had decided to tell the truth. The answer given by two guardian means "yes" and Chaos answered "no".

The second question is "Are you Chaos?". The person who answers "no" is Knight and the one who answer "yes" is Knave.

Does my answer look correct?; March 20, 2010 9:34 PM
Anonymous said...: A B C
1. Are you Knave? N N ?
2. Are you Chaos? N Y ?

From 1, you can derive which mean NO. (the majority syllable)

From 1&2, if you receive the answer YY or YN from Chaos, you can identify all of them. However, if Chaos replies NN or NY (duplicate!), you can only certainly identify either Knave or Knight, and a third question is required.

Pulling the duplicate aside, ask the confirmed: Is THIS PERSON Chaos?

Problem solved. -zerodude; March 22, 2010 4:41 PM
Anonymous said...: Hi Mr Tan,

I have seen this puzzle in a class during my student days.

The constrain is to ask only 3 questions in total (rather than 9).

The structure of the solution is complicated, but it is shown here:
http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

Cheers,
Trevor; March 22, 2010 6:27 PM
Tan Kin Lian said...: Here is the solution.

The first question that you ask is "Are you the Knight? "

You can get two or three answering the same "ja" or "da". If they "ja", you know that "ja" means "yes".

The Knight will answer "yes" (as he is telling the truth) and the Knave will answer "yes" (as he tells a lie).

CHAOS TELLS THE TRUTH
If one person answer "no", he is Chaos and he has decided to tell the truth today.

The second question that you ask of the other two is "Are you Chaos". The person who answer "yes" is Knave and the person who answer "no" is Knight.

CHAOS TELLS A LIE
If all three answer "yes", then Chaos has decided to lie.

Your second question is "Are you the Knave?". The person who answer "yes" is Chaos, as Knight and Knave will answer "no".

The third question is "Are you Chaos?". Of the remaining two, the person who answer "yes" is the Knave and "no" is the Knight.

Easy?; March 24, 2010 11:16 AM
Anonymous said...: Your solution is asking up to eight questions in total (up to 3 to each Guardian).

We can only ask 3.; March 24, 2010 3:32 PM
Tan Kin Lian said...: Reply to 3:32 PM
If you can only ask 3 questions, then it is quite difficult. So, I withdraw my solution.; March 24, 2010 6:12 PM
Anonymous said...: Mr. Tan, you are very smart to find a solution in such a short time. Good work!; March 24, 2010 7:38 PM
Anonymous said...: The trick is to ask questions with set parameters or conditions. eg. If "ja" means "yes" and you're the knave, is one of the other 2 the knight?
Ok, this example is totally worthless, just an example; March 24, 2010 10:25 PM