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,1 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 Tim Challener, a participatory, game theoretic, and cinematic engineering puzzle:
You are a super villain whose two roommates also happen to be super villains.
A problem: James Bond has discovered your whereabouts and is coming to get you. Good thing all three of you are great at designing spy-capturing nets. Time to fortify your defenses.
You and all your roommates will place one net each, but you’re villains, so you each want to design the trap that actually nabs Bond. One major thing to keep in mind: Villains’ nets, as everyone knows, are always placed in threes, and in increasing order of effectiveness. So if your lair is equipped with nets that capture an invader 10, 20 and 50 percent of the time, for example, James Bond has to try to get past them in that order. Unless, of course, he gets captured first. So you each need to design not the most effective net, but the net you think is most likely to grab Bond before someone else’s. (You don’t know what traps your roommates are designing before all three are deployed.)
Keep that in mind as you design and name your new net. Specifically, calibrate the percentage chance that it will capture James Bond if he tries to pass by it. Remember, your goal is for your trap to ensnare James Bond. Ninety-nine percent effectiveness sounds like a great trap, but it is also likely to come at the end of the three traps, and Bond may have already been captured before he gets to it.
After Riddler Nation submits its designs, I’ll pick your roommates for you, too. I’ll pluck three traps at random from your submitted designs, place them in a lair in the proper order, and keep track of whose trap, if any, is the one that nabbed Bond. I’ll do that over and over and over again, simulating the captures of millions of James Bonds, and the effectiveness of your traps. Whoever’s trap is the best at capturing James Bonds shall be declared the 😈 Chief-Arch-Super-Villain Engineer Extraordinaire 😈 of Riddler Nation. Go forth and capture.
Riddler Classic
From Matt Ginsberg, shuffle up and deal … and rearrange … and calculate:
You love to play cards. Bridge, spades, hearts, euchre, whist, setback, pitch, pinochle, bezique, sheepshead, écarté, krutzjass, baloot, königrufen … you name it. If there are tricks to be taken, you want to take them.
You play so many card games that you’ve developed a very specific organizational obsession. When you’re dealt your hand, you want to organize it such that the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent. (Numbers don’t matter to you.) Moreover, when you receive your randomly ordered hand, you want to achieve this organization with a single motion, moving only one adjacent block of cards to some other position in your hand, maintaining the original order of that block and other cards, except for that one move.
Suppose you’re playing pitch, in which a hand has six cards. What are the odds that you can accomplish your obsessive goal? What about for another game, where a hand has N cards, somewhere between 1 and 13?
Editor’s note: Matt has no idea what the answer is (yet). His guess, for the record, is 57 percent.
Solution to last week’s Riddler Express
Congratulations to 👏 Hunter Collins 👏 of Louisville, Kentucky, winner of last week’s Riddler Express!
Last week brought a scheduling challenge. There was only one remaining undefeated team in the NFL right now: the 6-0 (and now 7-0) Los Angeles Rams. But theoretically, what’s the biggest number of NFL teams that could finish a given season with an undefeated, 16-0 record, given the way the NFL schedule works?
It’s four — two in each conference.
Solver Ray Crawford explained it like so: First, each team has to play the other teams in their entire division, eliminating three of the four teams from each of the eight divisions. (Ties don’t get you to 16-0, so we’ll pretend like every game ends with a winner and loser in this solution.) Best-case scenario, that leaves eight unbeaten teams, one from each division. Next, the schedule demands that each team must play all the teams in another division in their own conference. Since that’ll pit more undefeated teams against each other, this eliminates half of the unbeaten teams, leaving four total, two in each conference. Finally, each division plays another from the other conference. If the two remaining unbeaten teams in each conference get lucky, they’ll play a division where all teams have already lost. The largest possible unbeaten cohort, therefore, is four unbeaten teams, two in each conference, each in a different division.
Solution to last week’s Riddler Classic
Congratulations to 👏 Silas Johnson 👏 of St. Louis, winner of last week’s Riddler Classic!
Last week, your archipelago was exploding. (Sorry about that.) Specifically, your archipelago was made up of N islands, each of which had a volcano. Your archipelago was connected by a series of ancient bridges. To conserve resources, your ancient ancestors built these bridges such that there was exactly one path from any one island to any other island. The ground began to rumble and you knew that there was a probability, p, that any given volcano would erupt, taking the island and any connected bridges with it. Sensibly, you fled to the safety of the mainland. Following these potential disasters, how many disjointed communities can you expect to find when you return to your archipelago? What value of p maximizes this number?
It seems, at first, like there is not enough information to answer this question. We’re told very little about where the bridges were built, for example. But that, quite coolly, turns out not to matter.
The answer is \(1-p+(N-1)p(1-p)\) disjointed communities. That value is maximized when \(p=\frac{2-N}{2-2N}\). What follows is how we get there, as adapted from this puzzle’s submitters, Ricky Jacobson and Ben Holtz.
This is essentially a problem in graph theory. This problem is equivalent, in the language of that discipline, to asking: “If you start with a tree with N nodes, how many trees will you have on average in the forest created by deleting each node with probability p?”
To answer this, it helps to give the tree hierarchy — that is, to transform it from the graph version of a tree to the data structure version of a tree. To do this, let’s assign one island to be the root of the archipelagic tree — the biggest island, say. All the islands connected to the root are the root’s children. All the islands connected to those children are their children, and so on. Now consider what happens when nodes (islands) are removed thanks to volcanic eruptions. It is easy to see that, for every new tree created, there must be a new root, and vice versa. Therefore, the number of roots is exactly the number of trees in the forest. We can now ask: What causes a node to become a root? We can show that a node becomes a root when (1) its parent node is removed and (2) it itself is not removed. From here, we can construct a simple variable.
Let \(X_i\) equal 1 if island i is a root, and 0 otherwise. The expected value of that variable for all the islands except the original root is the probability of event (1) times the probability of event (2), or \(p(1-p)\). For the original root, the expected value is just \(1-p\), since it has no parent island.
What we want now, to arrive at our solution, is the expected value of the sum of all of those probabilities, or \(E\left[\sum_{i} X_i\right]\). After a tiny bit of algebra, we get
\begin{equation*}E\left[\sum_{i} X_i\right]=1-p+(N-1)p(1-p)\end{equation*}
Voila! For the second part of the solution, we can use a little Calc 101. First we take the derivative of the number of communities with respect to p. Second, we set that derivative equal to zero. And third, we solve for p. That looks like this:
\begin{equation*}\frac{\partial}{\partial p}(1-p+(N-1)p(1-p))=(2-2N)p+N-2\end{equation*}
\begin{equation*}(2-2N)p+N-2=0\end{equation*}
\begin{equation*}p=\frac{2-N}{2-2N}\end{equation*}
As N increases, this fraction approaches 1/2.
Solver Tim Black simply could not get enough of this volcanic archipelago (and who could blame him?) and provided “four different, bite-size solutions.” In his fourth — and favorite — solution, Tim suggested Riddleria name one of the islands as its capital (that’s the root), shown in red in the hypothetical archipelago below. Because of the way the bridges were built, there is exactly one path from any island to the capital.
After the disaster strikes, suppose every Riddlerian walked toward the capital. If they get stuck, they declare the island on which they got stuck the new capital of their now disjointed community, as show below.
There is one capital per community, just as there was one root per tree.
Good luck, Riddlerians. The rest of the world is rooting for you.
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best of them and some never seen before, called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.