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 Bart Wright, a classic arcade problem:
In the video game Tetris, you can, in certain circumstances, completely clear the board after the first five pieces are placed. Knowing that, how many arrangements of Tetris pieces (or tetrominoes) are there that form a solid block that’s two squares high by 10 squares wide?
Riddler Classic
From Thierry Zell, a “multiplication” problem he recalled from his grad school days:
At the beginning of time, there is a single microorganism. Each day, every member of this species either splits into two copies of itself or dies. If the probability of multiplication is p, what are the chances that this species goes extinct?
Solution to last week’s Riddler Express
Congratulations to 👏 Peter Sloan 👏 of Montreal, winner of last week’s Express puzzle!
Bored one afternoon, you and I decide to play a simple game with a coin we find in the couch cushions. Namely, we take turns flipping it, and the first to flip 10 total heads wins. What are the chances that whoever flips first wins this game? They’re about 53.3 percent.
About half of the solvers approached this problem analytically, and about half computationally. Let’s take a quick look at both methods.
Solver Satoru Inoue walks us through an analytical approach:
The probability that the first player gets 10 heads in 10 tries is \(P(10) = C(10, 10) / (2^{10}) = 1 / (2^{10})\), where \(C(n,k)\) is the number of combinations of size k chosen from n elements. The probability of getting to 10 heads on the 11th try, say, is \(P(11) = (C(10, 9) / 2^{10}))/2\), which is the probability of having nine heads after 10 tosses times the ½ chance of getting heads on the 11th toss. In general, the probability that a player gets heads for the 10th time on the nth toss is \(P(n) = (C(n-1, 9) / 2^{n-1}) / 2\), which is the probability of having nine heads after (n-1) tosses times the ½ chance of getting heads on the nth toss. The chance for the first player to win on the nth toss is \(P(n) \cdot (1 – \sum_{i=10}^{n-1} P(i))\), that is, the probability of getting heads for the 10th time on the nth toss times the probability that the second player does not have 10 heads after \((n-1)\) tosses. Adding the numbers you get with this calculation, you arrive at the answer: The first player wins with probability 0.5329097742513389…
For the computational approach, the basic idea is to create two variables, representing the two players, and set them equal to zero. Then, using a random-number generator, simulate an alternating series of coin flips, adding one to each variable if the “coin” comes up heads. Once one of the variables hits 10, stop the program. Keep a running tally of which “player” hit 10 first, and run the program many, many times. After, say, a million trials, you can divide the number of times your first “player” won by a million, and you’ll have arrived at a good estimate of the first flipper’s advantage. Solvers Samuel Scherl and Sujeet Akula, among others, were kind enough to post their code online.
From our winner, Peter, here is the evolution of the win probabilities for each player as we require different numbers of total heads for victory. As the number of heads required increases, the players’ chances of winning approaches 50-50:
Solution to last week’s Riddler Classic
Congratulations to 👏 Ben Weiss 👏 of Carpinteria, California, winner of last week’s Classic puzzle!
You’re speeding along at the speed limit of 100 kilometers an hour down a flat, straight road toward your destination 4 kilometers ahead. But there is a stoplight 2 kilometers ahead, at the midpoint of your route. It’s green now, but every second there is a 1 percent chance it will turn yellow, in which case it will stay yellow for five seconds and then turn red for 20 seconds. Your car can accelerate or decelerate at a maximum of 2 meters per second squared. If you must obey the traffic laws, what is the best strategy for arriving at your destination as soon as possible?
Here’s a summary — from our winner, Ben — of the optimal strategy, depending on when you first see the light turn yellow:
For the first 41 seconds of your journey, you’re far enough away that you can safely ignore it. If it turns yellow between seconds 42 and 47, you’re golden: Go full speed straight through the light and you’ll arrive in the minimum 0.04 hours, or 144 seconds. If it turns yellow between 48 and 58, constantly decelerate and then accelerate such that you get back to your top speed of 100 kilometers an hour exactly when the light turns green again. Between 59 and 60, slam on the brakes, and then re-accelerate until you hit the green light perfectly. (Although, in this case, you won’t be quite able to reach your top speed as you pass it.) If it’s between 61 and 67, slam on the brakes and then drive in reverse for a while! Then use that extra road to speed up and arrive at the light just when it turns green. If it hasn’t turned yellow by second 65, you’ll want to proactively brake just after that time. Safety first! At 68 seconds or later, you’ll want to have slowed down, then re-accelerate back to 100 kilometers per hour.
The end result: Your trip takes about 146.35 seconds on average, only about 2.35 seconds longer than if the stoplight weren’t there at all.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.