Welcome back to The Riddler — I hope you had a wonderful Thanksgiving. 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 Graydon Snider, road race intimidation tactics:
Two runners, Alice and Bob, are participating in a footrace. The route is a straight line out some distance and the same straight line back — the starting point and the finish line are the same. As the starting gun is about to go off, Alice hatches a race plan: Her legs feel good and she wants to run fast enough compared to Bob that after the U-turn, they are staring face-to-face for as long as possible. How much faster than Bob should Alice run to spend the maximum amount of time facing Bob before they pass each other going in opposite directions? Assume that, on the advice of their coaches, they’ve each committed to running at a constant speed the whole time, and that the turn-around time at the halfway point is negligible.
Riddler Classic
From Dan Johnston, in which Alice and Bob then fall in love:
After their Riddler Express footrace, Alice and Bob fell in love and got married. Now they want lots of kids. However, as you may know, having one child, let alone many, is a lot of work. But Alice and Bob realized children require less of their parents’ time as they grow older. Alice and Bob, romantics that they are, decided to calculate how this relationship worked. They figured out that the work involved in having a child equals one divided by the age of the child in years. (Yes, that means the work is infinite for a child right after they are born. That may be true.)
Anyhow, since having a new child is a lot of work, Alice and Bob don’t want to have another child until the total work required by all their other children is 1 or less. Suppose they have their first child at time T=0. When T=1, their only child is turns 1, so the work involved is 1, and so they have their second child. After roughly another 1.61 years, their children are roughly 1.61 and 2.61, the work required has dropped back down to 1, and so they have their third child. And so on.
(Feel free to ignore twins, deaths, the real-world inability to decide exactly when you have a child, and so on.)
Five questions: Does it make sense for Alice and Bob to have an infinite number of children? Does the time between kids increase as they have more and more kids? What can we say about when they have their Nth child — can we predict it with a formula? Does the size of their brood over time show asymptotic behavior? If so, what are its bounds?
Solution to the previous Riddler Express
Congratulations to ÑÑâÐ Chris Sears ÑÑâÐ of Maysville, Kentucky, winner of the previous Riddler Express!
The World Chess Championship ended this week after 12 straight draws followed by a series of speedier tie-breaking games. That’s fitting, because two weeks ago we posed this question: What are the chances that the better player wins a 12-game match? Specifically, suppose one of the players is better than his opponent to the degree that he wins 20 percent of all games and loses 15 percent of games; the other 65 percent end in draws.2 What are the chances the better player wins a 12-game match? How many games would a match have to be in order to give the better player a 75 percent chance of winning the match outright? A 90 percent chance? A 99 percent chance?
That better player wins a 12-game match about 52 percent of the time. The number of games required for those larger thresholds are, in order, 82, 248 and 773. (Call me crazy, but I’m totally game for a two-year-long World Chess Championship.)
So how do we get there? Solver Dan Swenson suggested this tidy approach. Consider the following expression:
\begin{equation*}\left(0.2x + 0.65 + 0.15x^{-1}\right)^{12}\end{equation*}
The coefficients 0.2, 0.65 and 0.15 are the probabilities of the three outcomes of an individual chess game, and the whole thing is raised to the 12th power because of the 12 games of the match. Expand that expression, multiplying it all out and grouping its like terms. Then, the coefficient on \(x^r\), where the exponent \(r\) is some integer, is the probability that the better player wins the match by \(r\) games. Finally, add the coefficients on all the positive powers of \(x\), which gives the probability that the better player wins the match. The result is about 0.5198, or about 52 percent.
For the second part of the problem, we can use that same approach, and just change the “12” in the exponent of the expression, and then, the same as before, expand it and sum the coefficients on the positive powers of \(x\). The smallest exponent that gives a 75 percent chance or better is 82, the smallest that gives a 90 percent chance or better is 248, and the smallest that gives a 99 percent chance or better is 773.
Solver Chris Sears illustrated how the probability that the better player wins the match increases as the number of games increases.
Somebody get FIDE on the phone!
Solution to the previous Riddler Classic
Congratulations to ÑÑâÐ Scott Wu ÑÑâÐ of Baton Rouge, Louisiana, winner of the previous Riddler Classic!
Two weeks ago, we presented you with a sort of Riddlerified version of beer pong. You had an infinite supply of ping-pong balls, each labeled with some number 1 through N. There was also a group of N cups, labeled 1 through N, each of which could hold an unlimited number of ping-pong balls. The game was played in rounds that had two phases: throwing and pruning. During the throwing phase, you draw balls randomly, one at a time, from the supply and toss them at the cups. The phase ends when every cup contains at least one ball. Next comes the pruning phase, in which you go through all the cups and remove any ball whose number does not match the number on its cup. Every ball drawn had a uniformly random number, every ball landed in a uniformly random cup, and every throw landed in some cup. The game was over when, after a round was completed, there were no empty cups.
How many balls would you expect to need to draw and throw to finish this game? How many rounds would you expect to need before finishing this game?
The first question — how many throws would you expect to need — is like a “coupon collector’s problem,” and versions of it have appeared in this column before, for example in a problem about collecting Riddler League football cards. In this case, we’re filling cups instead of collecting coupons.The solution to this problem is well-known and stems from the fact that as we collect coupons — or fill cups — it becomes more and more difficult to collect or fill the ones that remain. The specific solution is quite mathy and involves something called the Euler-Mascheroni constant, but the main takeaway is that the more coupons or cups there are, the more and more time we can expect to spend collecting coupons or throwing balls.
Solver Laurent Lessard illustrated how the expected number of throws increases roughly quadratically as the number of cups (and numbers on the balls) increases:
The second question — how many rounds would you expect to play — turns out to be much trickier. Lessard also illustrated his mathematical approach when playing with three cups. The cups in his diagram are either empty (white), filled with a correct ball (green), or filled with an incorrect ball (red). The arrows and the numbers next to them represent transition probabilities — the chances a cup goes from empty to correctly filled, for example, are 1/N. Our goal, of course, appears in the bottom right of the diagram, where all three cups are correctly filled and the game is over.
From there, Laurent describes how to turn this diagrammatic approach into an answer. He uses a Markov chain, which describes probabilistic sequences of events that depend on the current state of events — such as the balls currently in our cups. And from there he invokes a holy Riddler trinity: absorbing states and limiting distributions and nilpotent matrices.
The result of all this is that while the number of throws required grows roughly quadratically, the number of rounds required grows roughly linearly.
Of course, this is also a problem that admits programmatic, simulation-based approaches. Solver Robert Chin shared Python code for a Monte Carlo simulation, and Michael Branicky shared his code as well. Finally, solver Tim Book shared the results of his computer simulations, which illustrate how the expected number of rounds increases as the number of cups (and the number of numbers on the balls) increases — roughly linearly:
Happy tossing!
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now! Consider your holiday shopping done.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.
CORRECTION (Nov. 30, 2018, 11:50 a.m.): An earlier version of this article misstated the name of one of the solvers. It is Robert Chin, not Robin Chin.