The Byzantine General Problem

[Bob78164]

I'm told that this week's Riddler is a well known problem called the Byzantine General Problem. I had never heard it but I think I have a solution.

You are the Emperor of Byzantium. You have N generals. You know that more than half of them are loyal, because otherwise the traitors would already have started a civil war to depose you.

You may ask any general about the loyalty of any other general. A loyal general will tell the truth. A traitor will say whatever he wants. What is the minimum number of questions you must ask to identify with certainty at least one loyal general, and what strategy achieves that solution?

If there are 50 generals, my solution guarantees that you will locate a loyalist in no more than 300 questions. Can anyone do better? --Bob

[President Chump]

Can anyone do better? --Bob

I would just execute them all and be done with it. Look, I just created N number of jobs!

I'll make Byzantium great again!!!!

[Bob Juch]

I'm aware of a totally different Byzantine Generals' Problem which has to do with unreliable communications.

[Vandal]

I'm pretty good at math and I think the answer is:



Three

[Bob78164]

I'm pretty good at math and I think the answer is:



Three

This makes me think of melly, because she gave an immediate answer to that question when serving as a PAF. --Bob

[Vandal]

I'm pretty good at math and I think the answer is:



Three

This makes me think of melly, because she gave an immediate answer to that question when serving as a PAF. --Bob

I've never met her, but I'm pretty sure Melly has five digits at the end of her armwings.

[plasticene]

If there are 50 generals, my solution guarantees that you will locate a loyalist in no more than 300 questions. Can anyone do better? --Bob

I can't do better, because I haven't quite figured out how to generalize my method, but I'm pretty sure you'd be able to do better than 300 with a slight tweak to your solution. Would your solution require three questions for four generals? You only need one!

[Bob78164]

If there are 50 generals, my solution guarantees that you will locate a loyalist in no more than 300 questions. Can anyone do better? --Bob

I can't do better, because I haven't quite figured out how to generalize my method, but I'm pretty sure you'd be able to do better than 300 with a slight tweak to your solution. Would your solution require three questions for four generals? You only need one!

My solution requires only 1 question for 4 generals. --Bob

[Bob78164]

My answer requires k(k + 1)/2 questions where k = INT((N - 1)/2) is the greatest possible number of traitors.

Proof is by induction on N. We don't need any questions at all if there are 1 or 2 generals so assume there are at least 3. Ask the next k generals (Generals 2 through k + 1) whether General 1 is loyal. If all of them say yes, then there are two possibilities, both resulting in certain knowledge that General 1 is loyal.

All k of them might be traitors, but if that's the case, then we've used up all of the traitors so General 1 is loyal (as are all of the other generals) and we are done.

Otherwise, at least one of the generals we asked is loyal, and therefore told the truth about Gemeral 1. Since all of these generals said that General 1 is loyal, a loyal general, who always tells the truth, says that General 1 is loyal, so again we know that General 1 must be loyal and again we are done.

Alternatively, one of the generals, say General k + 1, may claim that General 1 is a traitor. But then we know that at least 1 of General 1 or General k + 1 is a traitor. That means we know that more than half of the remaining N - 2 generals are loyal, so by our inductive hypothesis, we can identify a loyal general using no more than k(k - 1)/2 additional questions. Adding the k questions we have already asked to reach this point gives us a total of k(k+ 1)/2 questions, as required. --Bob

[plasticene]

That's what I meant by my comment. 50 generals require a maximum of 276 questions, not 300.

[Bob78164]

That's what I meant by my comment. 50 generals require a maximum of 276 questions, not 300.

24*25/2=300. But the answer given in this week's column is N - 1, or 49. I'm in the air today so I can't yet verify the logic of the given solution. --Bob

[plasticene]

Oh, never mind, I'm just senile.