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 Christopher Dierkes, a lazy day puzzle:
You and I find ourselves indoors one rainy afternoon, with nothing but some loose change in the couch cushions to entertain us. We decide that we’ll take turns flipping a coin, and that the winner will be whoever flips 10 heads first. The winner gets to keep all the change in the couch! Predictably, an enormous argument erupts: We both want to be the one to go first.
What is the first flipper’s advantage? In other words, what percentage of the time does the first flipper win this game?
Riddler Classic
From Sebastian de la Torre, an open road puzzle:
You are driving your car on a perfectly flat, straight road. You are the only one on the road and you can see anything ahead of you perfectly. At time t=0, you are at Point A, cruising along at a speed of 100 kilometers per hour, which is the speed limit for the whole road. You want to reach Point C, exactly 4 kilometers ahead, in the shortest time possible. But, at Point B, 2 kilometers ahead of you, there is a traffic light.
At time t=0, the light is green, but you don’t know how long it has been green. You do know that at the beginning of each second, there is a 1 percent chance that the light will turn yellow. Once it turns yellow, it remains yellow for 5 seconds and then turns red for 20 seconds. Your car can accelerate or decelerate at a maximum rate of 2 meters per second-squared. You must always drive at or below the speed limit. You can pass through the intersection when the traffic light is yellow, but not when it is red.
What is the best strategy to reach your destination as soon as possible?
Solution to last week’s Riddler Express
Congratulations to 👏 Eyal Rosin 👏 of Rosh Ha’ayin, Israel, winner of last week’s Express puzzle!
It’s your 30th birthday, and your friends got you a cake with 30 lit candles. You try to blow them out, but each time you blow you successfully extinguish a random number of candles, between one and the number that remain lit. How many blows will it take, on average, to extinguish them all? Very, very close to four.
More precisely, it will take about 3.994987 blows. Why?
Let’s start with a smaller number of candles and work our way up. Suppose you have a cake with just a single candle. You’ll blow it out in one blow, for sure. Suppose there are two. Half the time you’ll blow them both out in one go, and half the time it’ll take two blows. Let’s make a list:
One candle: 1
Two candles: \((1/2)\cdot 1 + (1/2)\cdot 2 = 1.5\)
Three candles: \((1/3)\cdot 1 + (1/3)\cdot (1+1.5) + (1/3)\cdot (1+1) = 1.8\bar{3}\)
Four candles: \((1/4)\cdot 1 + (1/4)\cdot (1+1.8\bar{3}) + (1/4)\cdot (1+1.5) + (1/4)\cdot (1+1) = 2.08\bar{3}\)
With each additional candle, you have an equal chance of blowing them out in one go and of only snuffing some specific number, leaving some to tackle on the next blow. Notice the pattern! For one candle, the average number of blows is one. For two, it’s 1+1/2. For three, it’s 1+1/2+1/3. For four, it’s 1+1/2+1/3+1/4. And so on. So to get the answer, we simply compute this harmonic sum:
\begin{equation} \sum_{i=1}^{30} \frac{1}{i} \approx 3.994987 \end{equation}
Happy birthday!
Solution to last week’s Riddler Classic
Congratulations to 👏 Art Roth 👏 of Skokie, Illinois, winner of last week’s Classic puzzle!
You and I just purchased a nifty 100-sided die at our local game shop. We aren’t quite sure what to do with this new toy, so we invent a simple game. We keep rolling it until it shows a number smaller than the number before. Feeling generous, I give you $1 every time we roll. How much money do you expect to win? About $2.73.
More precisely, you can expect to win \((100/99)^{100} \approx 2.731999\) dollars. Why? I’ve adapted the excellent solution from reader Sam Elder here:
The idea is similar to this week’s Riddler Express solution above: We set up a recurrence and then compare consecutive values to get an easier recurrence. Suppose the most recent roll was \(n\). Since we don’t care about the rolls that came before the most recent roll anymore, we can simply call the number of expected remaining rolls \(t_n\). For starters, if \(n = 100\), unless we roll another 100, we’re going to stop after one roll. So \(t_{100} = 1 + 1/100 t_{100}\), which means that \(t_{100} = 100/99\). In general, if we roll a number equal to or higher than \(n\), we’re going to keep rolling, but update our latest roll to that number. So, for any \(n\), \(t_n = 1 + (1/100) (t_n + t_{n+1} + \ldots + t_{100})\). We then apply a very similar trick to that in the Express solution and compute that \(t_{n-1} – t_n = 1/100(t_{n-1})\), so \(t_{n-1} = t_n \cdot (100/99)\). So this is just a geometric sequence! In general, \(t_n = (100/99)^{101-n}\). To compute the expected total number of rolls, we have to take into account our first roll and then average all of the \(t_n\)’s. So the total expected number of rolls is \(1 + (1/100) (100/99 + (100/99)^2 + \ldots + (100/99)^{100}) = \\ 1 + (1/100)((100/99)^{101} – 100/99)/(100/99 – 1) = \\ 1 + (99/100)((100/99)^{101} -100/99) = \\ (100/99)^{100}.\)
As the number of sides on the die increases, from 100 toward infinity, your expected winnings approach $e, where e is Euler’s number—the mathematical constant equal to about 2.71828. You can find a thorough discussion of your expected winnings for dice of various sizes in this great post by Laurent Lessard.
Don’t spend all your $2.73 in one place.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.