How Much Will It Cost To Sniff Out The Spies?

рџљЁрџљЁрџљЁ “The Riddler” book comes out this Tuesday! It’s practically imminent! It’s chock-full of the best puzzles from this column (and, fret not, their answers) and some that have never been seen before. Pre-order now, or tell Siri to remind you to grab a copy from your favorite local bookstore next week. I hope you enjoy it, and thank you for riddling with us these past three years. рџљЁрџљЁрџљЁ

Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,¹ and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.

Riddler Express

From Peter Hadiaris, let’s warm up with a little game of what-comes-next:

What’s the next number in this series?

9, 10, 19, 24, 31, 40, 51, 64, 79, 90, ?

Submit your answer

Riddler Classic

From Moin Qureshi, international intrigue besets Riddler Nation:

There are N agents at the RIA (that’s the Riddler Intelligence Agency), and K of them are spies. Your job is to identify all the spies. (No, this is not a game of Codenames.)

You can send a given number of agents to a “retreat” on a remote island. If all K spies are present at the retreat, they will meet to strategize. If even one spy is missing, this spy meeting will not take place. The only information you get from a retreat is whether or not the spy meeting happened. You can send as many agents as you like to the retreat, and the retreat can happen as many times as needed. You know the values of N and K.

What’s the minimum number of retreats needed to guarantee you can identify all K spies? If each retreat costs $1,000 per person, what is the total cost to identify all K spies?

To begin with, let’s assume you know that N = 1,024 and K = 17.

Submit your answer

Solution to last week’s Riddler Express

Congratulations to рџ‘Џ Richard Campbell рџ‘Џ of New Orleans, winner of last week’s Riddler Express!

The midterm elections are fast approaching, and last week brought a puzzle to that effect. FiveThirtyEight’s House forecast gives Democrats an 80 percent chance of winning the House. Our Senate forecast gives Republicans a 70 percent chance of holding the Senate. Assuming that those individual probabilities are correct, and assuming for the purposes of this problem that we know nothing else about voters or how the outcomes of those legislative races are likely to interact with one another, what is the lowest possible probability of a split Congress — where one party controls one chamber and the other party controls the other? What is the highest possible probability of a split Congress?

The question here is really about the correlation between the results of the House elections and the Senate elections. If the outcomes were uncorrelated — that is, if they were independent — we could multiply (0.8)(0.3) = 0.24 to find the chance of a Democratic Congress, and (0.2)(0.7) = 0.14 to find the chance of a Republican Congress, leaving us with a 1 – 0.24 – 0.14 = 0.62, or 62 percent, chance of a split Congress.

But, as the problem said, we didn’t know anything about how the races interacted, we only knew the marginal probabilities for control of each house, and they needn’t have been independent. (In fact, in reality, they aren’t.)

The lowest probability of a split Congress is 50 percent. The highest such probability is 90 percent.

Solver Barry Nalebuff, a game theory professor at Yale, provided the following tidy argument to get to those solutions:

1. Start with 100 white balls.
2. Paint half of each with a “House” color. Therefore, 80 of those balls need to be half-blue blue and 20 half-red (that’s the given marginal probability for House control).
3. Next, add a “Senate” color to the other half of each ball. Therefore, 70 need red halves and 30 need blue halves (that’s the given marginal probability for Senate control). But before you paint the Senate color, we have some choices to make in our painting. That’s because while we know the marginal probabilities, the joint probabilities for the two bodies together aren’t given to us.
4. If we were to paint all of the House-red balls Senate-red, the fewest red-and-blue balls available us to paint is 50. Therefore, the smallest probability of a split Congress is 50 percent.
5. If we were to paint all of the House-red balls Senate-blue, the most red-and-blue balls available for us to paint is 90. Therefore, the largest probability of a split Congress is 90 percent.

In reality, at least as experienced through FiveThirtyEight analysis, we do know something about the interaction of these races, of course. Our Classic model gives a roughly 53 percent chance of a split Congress.

Solution to last week’s Riddler Classic

Congratulations to рџ‘Џ Holly Zhou рџ‘Џ of Mountain View, California, winner of last week’s Riddler Classic!

Last week, you were hard at work at your company, RoboRackers™, that makes robots that can rack pool balls. To operate one of your robots, you give it a template, like this:

(The template only recognizes the differences among stripes, solids and the eight ball. None of the other numbers matters.) First, the robot randomly corrals all of the balls into the wooden triangle. From there, the robot can either swap the location of two balls or rotate the entire rack 120 degrees in either direction. It continues performing these operations until the balls’ formation matches the template, and it always uses the fewest number of operations possible to do so. Using the template shown above — i.e., a correct rack for a standard game of eight ball — what is the maximum number of operations the robot would perform? What starting position would yield this? How about the average number of operations?

The most operations your robot would ever need to properly assemble the balls is six. The average number of operation it will need is about four.

According to the work shared by solver Jeremy Hummel (complete with expert emoji usage) and others, there are 51,480 different ways that the robot might initially corral the balls into the wooden triangle. One of these arrangements (if you get very lucky) requires no robotic operations. Sixty-five require one operation, 1,253 require two operations, 9,653 require three, 27,422 require four, 12,946 require five, and just 140 (if you get very unlucky) require six. The average of those requirements, before your robot randomly corrals the balls, is about four expected operations. Not bad! You’ll be shooting pool before you know it.

Solver Thomas Mack also shared his thorough solution, as did Daniel Lenski, and this week’s winner, Holly Zhou, shared her Python code. And solver Laurent Lessard, in addition to writing up his excellent solution, illustrated an example of one of the “bad” arrangements, which would take your robot the maximum six operations to set straight:

Want to submit a riddle?

Email me at oliver.roeder@fivethirtyeight.com.