Captured by the Taliban

[azhiguore]

You and five other US spies are in holding cells awaiting execution by the Taliban. You got caught because one of your group members is a traitor, but you still don't know who the traitor is. If you know the identity of the traitor, it will give you enough information to hack the security system and escape, but you have to be careful. If you're wrong, the alarm will go off and all of you will be instantly executed.

Luckily, the five other prisoners each have phones (no speakerphones) and you have a list of three phone numbers. Two of them call US bases who know the name of the traitor. The other calls a former US base that was infiltrated by the Taliban who could say anything (even changing what they say).

You have enough time to make two rounds of calls, and have enough batteries (that can be passed between the cells) to make six total calls. How can you pull it off?

[gavinksong]

I assume you can't make any calls yourself.

Spoiler

In the first round, let three operatives each call a different base.

Since there's only one traitor and one compromised base, at least one of the three operatives will report the truth. Therefore, any operative who is not accused in the first round is guaranteed to be loyal.

Assume that fewer than three operatives are accused in the first round. Then, you should have at least three operatives who are in the clear. Ask these operatives to each call a different base in the second round. Since only one base is compromised, at least two out of the three bases should give you the true name of the traitor.

From this point on, assume that three different operatives are accused in the first round. Now, you have two operatives who you know are loyal.

If either of these operatives have already called a base, then in the second round, you can have your loyal operatives call the one or two remaining bases. Again, the majority of the three bases should name of the traitor.

If this is not the case, every operative who called a base must have accused each other. This means that they accused each other in a cycle, e.g. A accused B, B accused C, and C accused A. Notice that this means that the traitor must have accused the operative who called the infiltrated base, and the infiltrated base must have named the operative who correctly accused the traitor.

In the second round, have your loyal operatives call two of the bases. Each of these bases will either confirm the original caller's accusation or deny it, naming him/her as the traitor. Let's call these bases A and B, such that the original caller of A accused the original caller of B. If and only if A and B are both loyal bases, then the original caller of B must be the traitor (see the previous paragraph), and A will confirm and B will deny. If you fail to observe this, then the original caller of B must be loyal, and the remaining base (C) must be loyal. Since the original caller of B is not one of the operatives whose loyalty was ascertained in the first round, you can have him place the third call of the second round to base C, thus sealing the fate of our traitor.

[nana77]

 

My answer:

 

Spoiler

Let's call the spies a, b, c, d, e, and the phone numbers 1, 2, 3. Have a, b, c call 1, 2, 3.

If all three spies get the same answer, that is the correct answer.

If 2 spies (let's say a and b) get the same answer, then we know the traitor must either be the person they named, or one of the two accusers (with the other accuser having called the bad number). If one of the two are bad, the third spy should be accusing them. If the third spy accuses someone else, then we know whoever a,b accused is the traitor and the third spy must have bad results. So we either have the answer (whoever a,b accused) or have it narrowed down to 2 (the one accused by a,b and the one of a,b accused by c. The other 3 spies are all clear and may proceed with a 2nd round of calls to figure it out. Whoever is accused by 2 or more in the 2nd round is guilty.

If all three spies get different results, that is only possible if one of them is a traitor and one of the other two called the bad number. D and E are thus clear. If D and E were both accused, that only leaves on of ABC to have been accused and that one must be the traitor (since at least one result must be correct, and 2 incorrect results means a traitor must have made the accusation thus the traitor must be in ABC). If only one of D or E was accused, then whichever of ABC not accused is also clear. So that person along with D and E can make 3 calls to get the traitor. Whoever is accused by 2 or more in the 2nd round is guilty.

The only hope for the traitor is to create a round robin in which neither D nor E are accused. Let's say A accuses B who accuses C who accuses A.

In this case, D and E choose one of the 3, say A, to join in a 2nd round of calls. And A will be calling the number that B had called, 2.

If all three get the same results, whoever that is must be guilty. Assuming they do not all answer the same:

If A is traitor, 2 is the bad number and D and E will both be told A is the traitor.

If B is traitor, 3 is the bad number. A will be told B, D will be told B, and E will be told something else. Since D and E are told different things, they know one of them has the bad number, and therefor 2 is a good number and therefor A is clear. A can only be bad if 2 was a bad number. So they know that anytime D and E get different results, they can trust what A says.

If C is the traitor, 1 is the bad number, A will be told C, E will be told C, and B will be told something else. Just as above, they know they can trust what A says as true.