538 Riddler: Traitorous Generals
30 July ’16
We begin by selecting one general at random. Our goal will be to determine if this specific general is loyal or traitorous, which we can figure out by polling the other generals. As we go around the circle, there are two stop conditions:
- The selected general receives loyal votes
- The selected general receives traitorous votes
If  happens, we know the selected general to be loyal. If  happens, we know the selected general to be traitorous. This works because we know that there is a majority of loyal generals and that all loyal generals are honest. If, during this inquisition, we identify a loyal general, then we're obviously done. If we identify a traitorous general, then we incarcerate him (or perhaps a more sinister punishment) and pick a new general to evaluate. We begin a new inquisition and reduce our stop conditions by 1. Through this process, we are guaranteed to find a loyal general. How many questions will it take though?
The maximum number of questions it takes to get to one of these two stop conditions is dependent on how the traitors behave. This requires a little explanation. Let's say we pick a traitorous general for our first inquisition. All the other traitors shouldn't try to vouch for him (i.e. claim he is loyal) because (1) it will not save him and (2) it will doom them individually. We're going to get to the right answer regardless, and anyone who said the traitor was not a traitor will be outed along with him. If our traitors choose the "band together" route, this whole thing will be over after this inquisition since we'll be able to pinpoint all of the traitors (the selected general and anyone who said he was loyal). If our traitors are self-preservational, we will confirm that the selected general is a traitor in exactly questions but will then need to begin another inquisition.
Why might we assume that traitors are self-preservational? Depends on whether the generals know what the emperor is trying to accomplish here. If the generals know the emperor is trying to identify a single loyal general for a super-important mission, then it makes sense for them to be self-preservational. If the generals think the emperor is going to methodically proceed through the ranks until he has killed every last traitor...well then I guess the traitors will be somewhat ambivalent, given that they're all going to get outed either way. Let's assume the generals don't know what the emperor is trying to do. And since there is a non-zero probability that the emperor is just trying to find a single loyal general, it makes sense for the traitorous generals to behave in a self-preservational way.
More importantly, does our assumption that "traitors will be self-preservational" impact our answer? Fortunately, I believe this assumption aligns with the upperbound. If a traitor says that another traitor is loyal, this can increase the number of questions required to identify the traitor in that inquisition, but also decreases the number of potential inquisitions needed because we'll be able to rule out both of those traitors by the end of that inquisition (two birds with one stone). In essense, self-preservational traitors make it most difficult for the emperor...by telling the truth.
We will need to do, at most, inquisitions; if we pick traitors in all of those, then we know any one of the remaining generals is loyal. Each subsequent inquisition distills our pool of generals to a smaller, more loyal group, making it easier and easier to assess the loyalty of our selected general. In other words, we need one fewer vote to confirm the selected general's loyalty.
Putting this all together, the maximum number of questions we would need is:
Let's quickly go through the N=5 example. Best case scenario, we pick a loyal general for our first inquisition. We only need 2 "loyal" votes to confirm he's loyal. We'll get this confirmation in 2-4 questions, depending on what happens. And we're done. Worst case scenario, we pick a traitor general for our first inquisition. We need 3 "traitor" votes to confirm he's a traitor. We'll get that in a 3-4 questions. If it takes 4 questions, then we've outed both of the traitors (the selected general and the guy who said he was loyal), and we're done. If it takes 3 questions, then we will need to begin another inquisition with the 4 remaining generals (3 loyal, 1 traitor). And in that round, we'll need a maximum of 2 questions to identify one of the loyal generals (just takes one "loyal" vote) or the lone remaining traitor (only takes two "traitor" votes). So the maximum number of questions we'll need is 5. This aligns with the above equation: .