# Truths, Lies, and Xors

Rusty is a member of the highly secretive Logician's guild. After years of grueling trials, he is now finally allowed to meet the three leaders of the guild. Their names are Truman, Lyle and Xavier, and they have specific ways of answering yes/no questions:

• Truman tells the truth.
• Lyle lies.
• Xavier answers the "xor" of how Truman and Lyle would answer the question, meaning:

• If Truman and Lyle would give different answers, then Xavier responds "yes".
• If Truman and Lyle would give the same answer, then Xavier responds "no".

Rusty enters the main chamber, and find the leaders sitting in chairs labeled Left, Right, and Middle, though he doesn't know who is who (the three know each other's identities). The leaders give Rusty a challenge. Rusty must determine their identities by asking at most three yes/no questions, each directed at a single leader.

To make things harder, and to prevent paradoxes, the only allowable questions are those which are Boolean combinations of questions of one of these two forms:

• "Is leader in the _____ chair named _____?"

• "Are you named _____?"

For example, Rusty may ask questions like "Is the person in the middle chair either Xavier or Lyle?", or "Is it true that both you are Xavier and the person in the left chair is Truman?".

How can Rusty pass the test?

Note: It may seem that Xavier would always answer "yes", since Truman tells the truth, which should always be different than Lyle's lie. However, including the pronoun "you" in your question can break this symmetry.

╠ Ask one of them (let it be one in the middle) "Are you Truman?" (Q1)
╠═No╦ Middle is Xavier.
║   ║
║   ╠ Ask man on the left if he is Xavier. (Q2)
║   ╠Yes═ Left is Lyle. (Right is Truman.)
║   ╚═No═ Left is Truman. (Right is Lyle.)
║
╚Yes╦ Middle is either Truman or Lyle.
║
╠ Ask middle if he is Xavier. (Q2)
╠Yes╦ Middle is Lyle.
║   ║
║   ╠ Ask middle if left is Xavier. (Q3)
║   ╠Yes═ Left is Truman. (Right is Xavier.)
║   ╚═No═ Left is Xavier. (Right is Truman.)
║
╚═No╦ Middle is Truman.
║
╠ Ask middle if left is Xavier. (Q3)
╠Yes═ Left is Xavier. (Right is Lyle.)
╚═No═ Left is Lyle. (Right is Xavier.)

• I thought each question had to be directed at a different leader. You are asking middle leader up to 3 questions. Nov 7, 2015 at 0:04
• @GordonK: The puzzle just says "each directed at a single leader", with no requirement of choosing distinct leaders for distinct questions. Nov 7, 2015 at 1:01
• @user2357112 Yes, re-reading it I agree. Nov 7, 2015 at 1:04
• Does it make any significant difference? Nov 17, 2015 at 18:03
• @nitro2k01 the names of the leaders imply that they are male. But either way, does it really matter?
– Hugo
Feb 1, 2016 at 13:01

Only two questions are needed: "Are you Truman?" and "Are you Xavier?", though you may have to direct one of the questions to two different leaders. The following lists show how each of these questions are answered by each leader:

Are you Truman? Truman: Yes, Lyle: Yes, Xavier: No.

Are you Xavier? Truman: No, Lyle: Yes, Xavier: Yes.

Each leader has a unique combination of answers: Lyle says yes to either question, and Truman and Xavier have opposite answers from each other.

For your first question, pick a leader and ask one of the questions. If the answer is no, you figured out who it is (only one leader answers no to each of the two questions). You only need to ask the other question of another leader, and you're done. If the answer to the first question was yes, then ask the other question of the same leader. If you get another yes you've found Lyle and you can ask either question of another leader to figure out who is Truman and who is Xavier. If you get a no, you've identified the first leader and you pick one of the two remaining leaders to re-ask the original question.

We can do this without asking a specific person "are you...?".

Ask chair 1, "is the person in chair 2 Truman, Lyle, or Xavier?". The correct answer, obviously, is yes, which means Truman answers yes, Lyle no, Xavier yes.

• If the guy in chair 1 answers no, he's definitely Lyle. Ask chair 2 "is the person in chair 1 Truman?". The correct answer is no, so Truman will say no, Lyle would say yes, Xavier will say yes.
• If the guy in chair 2 answers no, he's Truman and chair 3 is Xavier.
• If the guy in chair 2 answers yes, he's Xavier and chair 3 is Truman.
• If the guy in chair 1 answers yes, he's definitely not Lyle. Ask chair 2 the original question "is the person in chair 3 Truman, Lyle, or Xavier?". The correct answer is yes, so Truman says yes, Lyle no, Xavier yes.
• If the guy in chair 2 answers no, he's definitely Lyle. Same as above, ask the guy in chair 3 "is the person in chair 2 Truman?". The correct answer being no, Truman says no, Lyle yes, Xavier yes.
• If the guy in chair 3 answers no, he's Truman and chair 1 is Xavier.
• If the guy in chair 3 answers yes, he's Xavier and chair 1 is Truman.
• If the guy in chair 2 answers yes, he's definitely not Lyle, which means the guy in chair 3 is definitely Lyle. Ask the guy in chair 1 "is the guy in chair 3 Truman?". The correct answer is no, so Truman answers yes, Lyle no, Xavier yes.
• If the guy in chair 1 answers no, he's Truman and chair 2 is Xavier.
• If the guy in chair 2 answers yes, he's Xavier and chair 2 is Truman.

You can do something similar by leading with "is the person in chair 1 both Truman and Lyle?", which must be false, so instead of showing who Lyle is, it shows who Truman is. Then you ask if Truman is Truman and Lyle says no, Xavier says yes.

Once you know who Truman or Lyle are, you can directly ask them if one of the unknowns is Xavier. Truman will say yes if it's Xavier, no if it's Lyle. Lyle will say no if it's Xavier, yes if it's Truman. Same thing for directly asking Truman if a chair is Lyle, or Lyle if a chair is Truman.

And, of course, it doesn't matter what we call the chairs or what order we ask in, as long as we're careful to swap labels around appropriately.