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 Dominic van der Zypen, a tennis tourney problem:
You’re hosting a round-robin tennis tournament with N players. That means everyone plays one match against every other player. In tennis, there are no ties: The winner of a match gets 1 point and the loser gets zero points. At the end of the tournament, after everyone has played everyone else, a fan notices a circular phenomenon among three players, A, B and C — in particular, A lost to B, B lost to C, and C lost to A. When going through the results table, the same eagle-eyed fan also notices that everyone in the tournament has a different final score.
Can both of the fan’s findings be true, or was a mistake made when the points were being added up?
Riddler Classic
A game theory puzzle from Juan Carrillo that indulges in international diplomacy:
Consider the following war game: Two countries are eyeing each other’s gold. At the beginning of the game, the “strength” of each country’s army is drawn from a continuous uniform distribution and lies somewhere between 0 (very weak) and 1 (very strong). Each country knows its own strength but not that of its opponent. The countries observe their own strength and then simultaneously announce “peace” or “war.”
If both announce “peace,” then they each stay quietly in their own territory, with their own gold, which is worth $1 trillion (so each “wins” $1 trillion).
If at least one announces “war,” then they go to war, and the country with the stronger army wins the other’s gold. (That is, the stronger country wins $2 trillion, and the other wins $0.)
What is the optimal strategy of each country (declaring “peace” or “war”) given its strength?
Extra credit: What if the countries don’t announce at the same time and instead one announces first and the other second? What if the value of winning the war were $5 trillion rather than $2 trillion?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Sreeram Ramachandran ÑÑâÐ of Santa Clara, California, winner of last week’s Express puzzle!
The Chicago Cubs recently snapped a 108-year title drought. But how crazy is that, really? Last week’s puzzle asked about the average length of drought-ending, headline-making championships in a 30-team league in which the winner is chosen each year uniformly at random and the team makes headlines only if it had gone without a championship longer than any other team. The average quenched drought that makes headlines will be about 119.85 years. Not bad, Cubbies!
How do we get there? From the problem’s submitter, Jim Ferry:
Imagine we’re making a list of all 30 teams, ordered by how recently they’ve won the World Series. Last year’s champ comes first, one year ago. But what about the second-most-recent champ? On average, it won 30/29 years earlier. The next team on the list won 30/28 years before that, and so on. (These numbers are simply the inverses of probabilities. There is a 29/30 chance that the winner of the title two years ago was a different team than the one that won last year, so the expected time since the second-most-recent champ’s last title is 30/29 years.) Thus, if the team with the \(k\)th-longest drought wins, the expected length of that drought is \(30 \cdot (\frac{1}{k} + \frac{1}{k+1} + \ldots + \frac{1}{30})\). What we want here is the \(k=1\) case — the victory only makes headlines if it’s the league’s single longest drought that is broken.
Therefore, our answer is given by \(30 \cdot (1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\ldots +\frac{1}{30}) \approx 119.85 \).
Jon Glassman simulated this hypothetical league over a million years, shown in the video below, finding an average of 119.7 years:
https://www.youtube.com/watch?v=QeGsx-ZZPw8
This Riddler is closely related to the coupon collector’s problem. But rather than calculating the expected amount of time it takes to collect 30 coupons, we’re calculating the expected average length of a drought that makes the headlines.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Jacob Colbert ÑÑâÐ of Cambridge, Massachusetts, winner of last week’s Classic puzzle!
It was about unmasking Secret Santas. The 41 staffers in the FiveThirtyEight office are each randomly assigned one of the other 40 people on the masthead to give a gift to, and they can’t give to themselves. If everyone in the office asks an optimal series of 20 questions of their co-workers, what are the chances that all the staffers will reveal the true identities of their Secret Santas? In an office that size, it’s only about 31.8 percent.
There are two things to work out here: First, what is the optimal question-asking strategy, and second, what chances of success does that strategy give?
The optimal strategy is to ask the person for whom you were Secret Santa who they were Secret Santa for, then ask that person who they were Secret Santa for, and then that next person, and so on and so on, following the chain. As long as there are no “loops” of Secret Santadom longer than 21 staffers, everyone will eventually arrive at their own Secret Santa! (Person A giving a gift to B, B to C, and C to A would be a loop of three, for example.)
So our problem becomes: What is the probability that there are no loops longer than 21 staffers? “It is a bit of combinatoric slog,” our winner, Jacob, wrote. But Riddler Nation, undeterred, presses on.
As Laurent Lessard explains in his typically excellent solution, we want to add up the number of ways we might arrive at a loop of length \(k\) and specifically, for our purposes here, the loops of length \(k\) where \(k>21\). We can then divide this by the total number of possible arrangements to arrive at our probability. In our case, there are \(41\choose k\) ways of picking our loop, \((k-1)!\) ways of ordering the staffers within that loop, and \(D_{41-k}\) ways of arranging the staffers who are not within that loop. D here represents the number of “derangements” — permutations such that no element appears in its original position. We need to use this concept because no one can be his or her own Secret Santa. All this leads us to the following expression for the answer in an office of 41 Santas:
\begin{equation}P=1-\frac{\sum_{k=22}^{41}{{41}\choose{k}}(k-1)! D_{41-k}}{D_{41}}\end{equation}
It equals about 0.318. Laurent also plotted the probability of a successful unmasking for offices of various sizes, where 2n+1 is the number of people in the office and n is the number of questions each staffer gets to ask:
The lesson here: The least mysterious way to play Secret Santa is to have only one co-worker.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.