Ever since the emperor Chin, tyrants been caught in a dilemma: they know they need physical protection, but know also that their bodyguards might betray them.
Tyrant T has a corps of 7 bodyguards. He knows that if there are ever as many or more traitors than loyal guards in the room, he will be attacked.
One day, mustering his courage, he brings all 7 into a room. He is not attacked so he knows the majority of his guards are loyal. The trouble is that even bodyguards have to rest, so each bodyguard is on duty for 16 hours and off duty for 8 hours.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
T must therefore divide his guards into groups such that each has a majority of loyalists and each group consists of two loyalists or more. We call such a group Solid. He asks his courtroom mathematician M to help him.
M enters, bows and says: "Sire, why not ask the bodyguards themselves? They may know."
"Yes, but I won't know which accusations to trust," T replied.
"The emperor is very wise in his judgments," said the mathematician M, "but we can still learn something. A loyal guard will tell the truth, we can assume. A disloyal one may or may not. The necessary conclusion, Sire, is that every accusation means that at least one of the accuser or the accused is disloyal. Perhaps both in the case of a disloyal guard making an accusation."
Warm-Up:
Suppose the emperor had only five bodyguards whose accusation profile is as in
where an arrow from a guard X to Y means that X accuses Y of being disloyal. Assuming that a majority of guards are loyal, which ones must be loyal?
Solution to Warm-Up:
C and E must be loyal and so must one of A and D. Why? Among A, B, C, D, there must be at least two betrayers. This holds because, for example, the accusation from D to A suggests that at least one of A and D is disloyal; similarly, one of B and C must be disloyal. For this reason, E must definitely be loyal.
Two is also the maximum number among A, B, C and D who could be disloyal, because any more betrayers among that group would mean that there were only two loyal guards. Now, if C were disloyal, then there would be three disloyal ones among A, B, C and D, because two of A, B and D must be disloyal (accusations A to B, B to D, and D to A). C is loyal and B is disloyal (because B lies about C). Therefore, there is exactly one loyal one among A and D but this analysis doesn't tell us who that might be.
Now for the questions:
1. Continuing with this accusation profile:
Can you form a schedule to guarantee that tyrant T is always guarded by a Solid group?
2. Now consider a new accusation profile:
Can tyrant T be sure to be guarded at all times by groups of bodyguards having at least two loyal members and having a majority of members who are loyal? Remember guards work 16 hours on and 8 hours off.
Now, here is an open question: what is the maximum number of accusation edges there could be among seven guards if at least four of them are loyal? Count an edge where A accuses B as distinct from one where B accuses A.
