Maths Olympiad Prep

Library / /16 of 19

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:
On a certain island, there are knights, who always tell the truth, knaves, who always lie, and spies, who could do either. Suppose you meet three people, and you know one is a knight, one is a knave, and one is a spy, but you don't know which is which.
Find a method to ask three yes/no questions, each to one of the three people, so you can determine for sure which is which. You may question the same person multiple times, and your questions can depend on answers to previous questions.

Solution

Solution:
One strategy is as follows:
1. Ask the first person, "Is the second person more likely to tell the truth than the third person?"
If the response is "yes", then if the first person is the knight, the second must be the spy and the third must be the knave. If the first person is the knave, the second must be the spy and the third the knight. Either way, if the first person is not the spy, the second person is the spy.
If the response is "no", then if the first person is the knight, the second must be the knave and the third the spy. If the first is the knave, the second must be the knight and the third the spy. Either way, the first person or the third is the spy.
Thus, at this point, you either know for certain that the second person is not the spy, or that the third person is not the spy.

2. Ask the person whom you now know to be either the knight or the knave and not the spy (either the second or the third person) some question you know the answer to, like, "Does 1+11+1 equal 2?" Then, depending on their response, you know whether they are a knight or a knave.

3. Now ask this same person about the identity of one of the other two people. Since you know for sure whether this person is lying, their answer will tell you the identities of the other two people. For instance, if you know the second person to be a knave, you could ask, "Is the first person a knight?" If the second person says yes, the first person is the spy and the third the knight, and if the second person says no, the first person is the knight and the third the spy. No matter what, you can now figure out the identities of all three people.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.