The Traitorous Generals

This Riddler problem is a logic puzzle about liars and truth-tellers.

You are the emperor of Byzantium (lucky you!) and you have N generals working for you. You know that more than half of your generals are loyal, and the rest are traitors. You can ask any general about the loyalty of any other general: If the general you ask is loyal, he will answer correctly, but if he is a traitor he can answer however he likes. Your goal is to find one general you are absolutely certain is loyal while asking the fewest possible questions.

What is the minimum number of questions (in terms of N) that will guarantee a solution, and what strategy produces it?

There is a problem in cryptography known as the Byzantine Generals Problem, which has to do with achieving consensus in the presence of traitors that can sabotage communications. The Riddler problem above also involves liars and truth-tellers, but it’s a very different problem.

The following is adapted from a comment by Guy Moore. A similar solution that obtains the same final result was also found by Dmytro Taranovsky. Thank you both for your insights!

[Show Solution]