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]
The $N$ generals have the property that there is a loyal majority. This solution efficiently eliminates generals such that the remaining group of generals preserves the loyalty majority property. The strategy is:
- If there is an even number of generals, eliminate one of the generals (doesn’t matter which).
- If there is an odd number of generals, set one general aside. Pair up the rest of the generals and for each pair, ask the first general if the second one is a traitor.
- If the first general says the other is a traitor, eliminate both generals.
- If the first general says the other is loyal, eliminate the first general and keep the second.
- If we kept an odd number of generals, eliminate the general that was set aside. Otherwise, re-include the general that was set aside.
- If there is only one general left, this general is loyal and we may stop. Otherwise, return to the first step and repeat the process with the generals that are left.
Why does this work?
At each step, the loyalty majority property is preserved. To see why, let’s examine each case.
- If the first general says the second is a traitor, they cannot both be loyal. Therefore, by eliminating both, we eliminate at least as many traitors as loyal generals.
- If the first general says the second is loyal, we eliminate the first one. If the general that remains is a traitor, then both of them were traitors. This can happen for at most half of the pairs, since otherwise there would be a majority of traitors. If it happens for exactly half of the pairs, then the general we set aside must be loyal and so by re-including the general we set aside we retain loyal majority.
- If there is only one general remaining, then the loyalty majority implies that this general must be loyal.
How well does the strategy perform?
If we have $k$ generals, we ask $\left\lfloor{\frac{k-1}{2}}\right\rfloor$ questions. In the worst case, each question leads to only one elimination. We also re-include the general we set aside depending on parity. So the number of generals remaining in the next round is:
\[
\begin{cases}
\left\lfloor\frac{k-1}{2}\right\rfloor & \text{if }k\text{ is odd}\\
\left\lfloor\frac{k-1}{2}\right\rfloor + 1 & \text{if }k\text{ is even}
\end{cases}
\]
This is equivalent to
\[
1 + 2\left\lfloor\frac{1}{2}\left\lfloor\frac{k-1}{2}\right\rfloor\right\rfloor = 1 + 2\left\lfloor\frac{k-1}{4}\right\rfloor
\]
We can make this simplification thanks to the nested division property of the floor function. So if $q(k)$ is the maximum number of questions required, we have the recursion:
\begin{align}
q(1) &= 0 \\
q(k) &= \left\lfloor{\tfrac{k-1}{2}}\right\rfloor + q\left( 1 + 2\left\lfloor{\tfrac{k-1}{4}}\right\rfloor \right)
\end{align}
If we define $f(k) = k-q(k+1)$ and do some rearrangements, we can write the following recursion for $f(k)$:
\begin{align}
f(0) &= 0 \\
f(k) &= k- \left\lfloor{\tfrac{k}{2}}\right\rfloor- 2\left\lfloor{\tfrac{k}{4}}\right\rfloor + f\left(1+2\left\lfloor{\tfrac{k}{4}}\right\rfloor\right)
\end{align}
It turns out that $f(k)$ is the number of 1’s in the binary representation of $k.$ Or, equivalently, $f(k)$ is the sum of the binary digits of $k$. I’ll omit the derivation, but you can work it out by writing $k$ in binary and noting that each operation does something simple to the digits. For example, if $x = abcde_2$ then $\lfloor x/2 \rfloor = abcd_2$. Therefore, we conclude that if there are $N$ generals, the number of questions required in order to ensure we can select a loyal general is:
$\displaystyle
q(N) = N-1-f(N-1)
$
where $f(k)$ is the number of 1’s in the binary representation of $k.$ Here is a plot showing the questions needed as a function of the number of generals.
We always require slightly fewer questions that there are generals, and we can bound the number of questions as:
\[
N-1-\log_2(N) \le q(N) \le N-2
\]
On your way towards asking the 2k generals, as you say, the worst case is that all traitors tell the truth. But then you can stop after the k+1st answer, no?
This is an interesting problem, but your solution is not optimal. Assuming that questions can depend on previous answers, I got a strategy that uses at most
N-1-f(N-1) questions where f(k) is the number of ones in the binary representation of k. I do not know whether it is optimal.
Interesting Variations:
* You can use randomness in your strategy. The worst case appears to be when the number of disloyal generals is maximum and disloyal generals answer incorrectly; the expected number of questions is then 3/4*N-o(N).
* Questions cannot depend on previous answers. Your strategy has this property, but it is not optimal either. If k=1, it is enough to ask one question: If A says that B is loyal, then B is loyal, and otherwise C is loyal. If there is a constant c>2 such that N/k>c (where k is number of traitors), then I think O(N) questions suffice (with a majority of possible choices of the set of questions guaranteed to work), but I do not have a general answer.
Here is my strategy (do not read if you want to figure it out on your own):
For each general, assign a number, initially 1.
While the highest number is less than half of the sum of all numbers:
Pick any two generals with the same number for the highest number that such a pair exists, and ask the first one whether the second one is loyal
– if no, remove both generals (and their numbers)
– if yes, remove the first general and double the second general’s number
Pick a general with the highest number.
Also, correction: For the problem variation that allows randomness, the expected value should have been 2/3*N-o(N).
I agree with Dmytro Taranovsky. The optimal solution requires N-1-f(N-1) questions.
The key is to efficiently reduce the number of generals while maintaining the property that at more than half of the generals who remain are loyal. A step in this procedure is, for N odd, to break the generals into floor(N/2) pairs plus a leftover. (If N is even, ignore one general and solve the problem with the remaining N-1 generals.) For each pair of generals, ask one if the other is loyal. If the answer is “no,” then at least one is disloyal. Discard the pair; among all remaining generals we still have a majority of loyal generals. Now build a set using the generals whose colleague claimed that they were loyal, plus the leftover general if the number of claimed-loyal generals is even. This set has at most 1+2 floor((N-1)/4) generals and the majority are loyal. (If a general is claimed loyal but is really a traitor, then both generals in that pair were traitors. At most half of the pairs can have this property, and if exactly half of pairs do have this property then the leftover general is loyal and is included.)
Therefore, using floor((N-1)/2) questions, we have lowered the number of generals from N to at most [1+2 floor((N-1)/4)]. This procedure will indeed lower the number of generals to 1 (who is then loyal) using at most N-1-f(N-1) questions.
I don’t see how to use randomness in the strategy, though. Maybe you could clarify?
Thank you both for your insights! Guy and Dmytro, I removed my solution which was quite suboptimal and I posted a write-up adapted from the comments above. Thanks again!
It’s difficult to make sense of the layers of complexity imbued in portions of the response, but clearly it has an audience of considerate choir members.
Conventionally the responses appear both constrained and simple:
N of Questions = the total (N)umber of Generals when the total N of generals is odd, accounting for more than 2.
N of Questions = total (N)umber of generals minus one when the total N of generals is even, accounting for more than 2.
N of Questions= Zero when the total (N)umber of generals is 2 or less.
There is another prospect, and it is far more interesting. The unconventional solution is constant irrespective of the total (N)umber of generals:
N of Questions is ONE, FOLLOWING ONE COMMAND. There were no limitations placed on commamds. Any rate, it can go as follows:
Irrespective of the number of N, only one command and one question need be posed one time in a whole group lineup of generals:
(COMMAND)
Form a complete cohort/grouping of generals that are loyal to me by holding hands only with loyal generals, closing your circle only when all loyal generals are holding hands, and do not answer me until you have completed this task with absolute accuracy!
(QUESTION)
Are there any disloyal generals among you? / Has every loyal general identified every other loyal general?
Now then, let us usher in the world of Ultimate Prosperity!
With that, since all of the loyal generals can only speak correctly, they would only answer when they have achieved the accurate accounting of all loyal generals, which incidently they would all know once asked, if not earlier.
The result will be that the grouping of identified loyal generals will represent a quantity greater than half the total number of generals.
This beneficent leader would prefer to save both his pipes and time, alotting each for useful questions and instructions given to the most competent of the loyal generals so that we can Harmonize the World with Plans that will enable it to experience peaceful abundance. But whatever the leader’s ambitions, with the unconventional solution, they will be freed to identify their preferred traits among the full spectrum of loyal generals available. To be sure, some of the so-called leaders will waste plenty of talent due to their preference for irrelevant traits and inherent distrust of people with qualities they somehow find personally objectionable, despite the fact that such traits do not otherwise disfavorably impact a general’s competence, capacity nor performance.
N=ONE!
As I am of considerably low mathematical maturity, I was wondering whether anybody here can go into the details of the solutions including steps that might be to you relatively trivial. I worked on this problem for quiet a few hours so I want to understand how it is solved starting with the statement about the floor being 1+2floor
I added more detail to my solution and fixed some errors. Hopefully it should be clearer now — let me know if you have any more questions!
I am not convinced about the majority argument. Say there are 5 generals. We group them as LT LL and T. In the first pair both of them will be eliminated. In the second pair only first general will be eliminated. We will be left with LT and majority is lost for loyal. The problem persists in all case when traitor is set aside. Among the pairs all are LT and one pair is LL. Then all LTs will be eliminated and we will be left with one L and one T.
Thanks for the comment — I fixed the solution and it should be correct now. Basically, you only keep the general that was set aside if there is an even number of generals remaining.
I don’t understand why did the Riddler just post a different answer to the problem on their website?