Can You Sniff Out The Traitorous Generals?

Welcome to The Riddler. Every week, I offer up a problem related to the things we hold dear around here: math, logic and probability. These problems, puzzles and riddles come from lots of top-notch puzzle folks around the world — including you! You’ll find this week’s puzzle below.

Before we get to the new puzzle, let’s return to last week’s. Congratulations to 👏 Paul Duffell 👏 of Berkeley, California, our big winner. You can find a solution to the previous Riddler at the bottom of this post.

Now here’s this week’s Riddler, an ancient treachery puzzle that comes to us from Django Wexler, a fantasy novelist from Seattle.

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?

Need a hint? You can try asking me nicely. Want to submit a new puzzle or problem? Email me. I’m especially on the hunt for Riddler Jr. problems — puzzles that can stoke the curiosity and critical thinking of Riddler Nation’s younger compatriots?

And here’s the solution to last week’s Riddler, concerning two alien invaders and a guardian trying to save her planet. The two aliens destroy the planet if they meet each other before the guardian stops them. But if the guardian moves 20 times their speed, the planet will be saved roughly 99.27 percent of the time.

First, for some visual context, Zach Wissner-Gross slowed the guardian down to illustrate her task. Here’s what it looks like if she moves at five times the speed of the aliens:

And now the math, adapted from the excellent submission of Mike Seifert:

The easiest way to think of the solution is to think in terms of the aliens’ rendezvous point. The guardian can catch the aliens if and only if she can reach their rendezvous point before they do. If she can get to the rendezvous point first, she can then move directly toward one of them to catch them. (This simplification relies on the fact that the guardian moves faster than the aliens; a slower guardian would have to use a different strategy.)

If we select two points at random on a sphere, the angular distance $$\theta$$ that separates them has a probability distribution proportional to $$sin(\theta)$$. We can call the aliens’ initial angular distance from their rendezvous point $$\beta$$. The probability distribution of $$\beta$$ is proportional to $$\sin(2\beta)$$, since they are randomly selected points separated by an angle $$2\beta$$. Similarly, we can call the guardian’s angular distance from the rendezvous point $$\alpha$$. The probability distribution of $$\alpha$$ is proportional to $$\sin(\alpha)$$.

The overall probability distribution of $$\alpha$$ and $$\beta$$ together is therefore proportional to $$P(\alpha, \beta) = k \sin(2 \beta) \sin(\alpha)$$, and normalizing this to a proper probability distribution, whose integral equals 1, yields $$k = 1/2$$. (Note that by construction, $$0 < \alpha < \pi$$ and $$0 < \beta < \pi/2$$.) Finally, the guardian will be able to catch the aliens if her angular distance ($$\alpha$$) from the rendezvous point is less than 20 times the aliens’ angular distance ($$\beta$$) from the rendezvous point: $$\alpha < 20\beta$$. Integrating the above probability distribution over this appropriate region of the $$\alpha$$–$$\beta$$ plane, we get an overall success probability of about 99.27 percent.

It’s not too hard to extend this to other speed ratios as well. Of note: If the guardian travels at the same speed as the aliens, she only has a 1/6 chance of saving the world. If she travels at twice the speed of the aliens, her chances are 50-50. To get a 99 percent success rate, she needs to travel 17.1 times faster than the aliens; to get a 99.9 percent success rate, she needs to travel 54.2 times faster. If she wants to get Six-Sigma certified, such that she has a 99.99966 percent success rate, she needs to travel at least 929.4 times faster than the aliens.

For more details, as always, Laurent Lessard weighs in with his thoughtful solution, and you can find the solution from Roberto Linares, the puzzle’s submitter, in this document.

Elsewhere in the puzzling world:

Have a wonderful weekend!

Oliver Roeder is a senior writer for FiveThirtyEight.

Filed under