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-sized 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 (chosen at random) in next week’s column. If you need a hint, you can try asking me nicely on Twitter.
Riddler Express
From Jim Ferry, a puzzle that brings back fond memories:
The Cubs ended their famous 108-year World Series championship drought one month ago. But is 108 years really a long time? Suppose there were a league of 30 teams with a winner chosen uniformly at random every year. Each time the team that hasn’t won in the longest time does win, the length of that drought makes the headlines. (You can assume when the league starts that each team has a zero-year drought.) What are the lengths of these headline-making droughts, on average?
Riddler Classic
A holiday puzzle from Joe Zeng:
The 41 FiveThirtyEight staff members have decided to send gifts to each other as part of a Secret Santa program. Each person is randomly assigned one of the other 40 people on the masthead to give a gift to, and they can’t give to themselves. After the Secret Santa is over, everybody naturally wants to find out who gave them their gift. So, each of them decides to ask up to 20 people who they were a Secret Santa for. If they can’t find the person who gave them the gift within 20 tries, they give up. (Twenty co-workers is a lot of co-workers to talk to, after all.) Each person asks and answers individually — they don’t tell who anyone else’s Secret Santa is. Also, nobody asks any question other than “Who were you Secret Santa for?”
If each person asks questions optimally, giving themselves the best chance to unmask their Secret Santa, what is the probability that everyone finds out who their Secret Santa was? And what is this optimal strategy? (Asking randomly won’t work, because only half the people will find their Secret Santa that way on average, and there’s about a 1-in-2 trillion chance that everyone will know.)
Solution to the previous Riddler Express
Congratulations to 👏 Connor Hogendorn 👏 of Jersey City, New Jersey, winner of the previous edition of the Express puzzle! (We took Thanksgiving off.)
The previous problem asked about a photograph at the end of a dinner party. If five couples arrange themselves randomly in a line to pose for a photo, in such a way that all possible lineups are equally likely, there is about a 35 percent chance (47/135) that no person is standing next to his or her partner.
Here’s a nice explanation adapted from George Miller. One way to solve this problem is the inclusion-exclusion principle. First, notice that there are 10! (\(10\cdot 9\cdot 8\cdot \ldots \cdot 2 \cdot 1\)) ways of arranging 10 people in a line. That’s 3,628,800 ways. What we need to do now is to subtract off all the ways that do have couples standing next to each other, and see how many ways are left.
If you insist one couple must stand together, the two are bound together, so it’s essentially like removing one person from the lineup, leaving 9! possible arrangements. So the probability of one couple standing together (call it P1) is \(2\cdot 9!/10!=1/5\). (The “2” is because the couple could stand with either partner on the left or right.) The probability of two couples standing together (call it P2) is \(2^2 \cdot 8!/10!=2/45\). (The “\(2^2\)” is because the two couples can each be standing on either side of one another, and the “8!” because we’ve now bound two of the couples in the line together.) Similarly, the probability of three couples standing together is P3 = \(2^3 \cdot 7! / 10!\), the probability of four is P4 = \(2^4 \cdot 6! / 10!\), and the probability of five is \(P5 = 2^5 \cdot 5! / 10!\).
We are interested in one minus the probability that at least one couple stands together. This is where the inclusion-exclusion principle comes in. Say we wanted the total area of a simple Venn diagram. We can’t simply take Circle 1 + Circle 2, because this counts the middle intersecting section twice. Instead, we have to take Circle 1 + Circle 2 – the middle section. Similarly, adding more circles to the Venn diagram, you have to subtract or add intersecting sections until you don’t overcount (or undercount) them.
So, back to our couples. When we calculate the probability of, say, the P1 scenario — one couple standing together — we need to account for the chance that more than one couple is standing together, and include that probability in our calculation. When the scenarios overlap it’s the same concept as when the circles do.
The inclusion-exclusion principle helps us from there, offering the coefficients to apply to our five probabilities. This equals 5P1 – 10P2 + 10P3 – 5P4 + P5 = 88/135. One minus that — the probability that no couples stand next to each other — equals 47/135, or roughly 34.8 percent.
Solution to the previous Riddler Classic
Congratulations to 👏 Matthew Monaghan 👏 of Lincoln, Nebraska, winner of the previous edition of the Classic puzzle!
The previous Classic asked about a lonesome king who organized an elaborate game to pick a prince or princess for a day from among his many loyal subjects. The subjects assemble on the green. Each round, they all choose a random other subject. All subjects that were chosen are eliminated — not killed, just sent home — and the game continues again, with more choosing and eliminating and so forth. If there is, at some point, exactly one person left, he or she wins. If not, no one wins and the king is lonely. If there are 56,000 subjects, the chances that exactly one remains and moves into the castle are a touch less than one half, or about 48 percent.
The answer to this problem, for kingdoms of various populations, exhibits some strange behavior. The chance that someone wins (rather than a bunch of subjects all being simultaneously eliminated in the final round) hovers around 50 percent, but does not converge to it. Rather, the probability oscillates around one-half, sometimes slightly higher, sometimes slightly lower, depending on the exact number of subjects on the green. There does not seem to be a nice, intuitive explanation for this weird behavior — it’s a bit of a mystery! Even professional mathematicians are still at work on this problem.
Laurent Lessard provided this great illustration of the win probability as the kingdom grows in size:
As did Nick Schwartz, via computer simulation:
For a deep dive into the math underlying this, check out Laurent’s solution. You can find further discussion of this odd solution in this 2015 paper, which refers to the game, more disturbingly, as “group Russian roulette.”
Have a great weekend!
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.