Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the 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 the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter or send me an email.
From Christopher Kyba comes a bippity boppity puzzle:
Each morning, your fairy godmother appears and gives you a chance to play a game. In this game, she deals 10 cards face down. Nine of the cards are winners, and one card is a loser. If you pick a winning card, you get a prize. You can then either take your prize and walk away or play again for the chance to win a second prize. But if you lose on that second play, you walk away with nothing and the game is over for the day. Each time you succeed, she invites you to play again under the same conditions (win yet another prize or lose everything).
What strategy maximizes the average number of prizes you win each day? And what is that average?
Extra credit: Suppose your fairy godmother deals N cards each day (instead of 10 cards), with N−1 winning cards and one losing card. Now what is your strategy, and how many prizes do you expect to win each day?
A long time ago, there once was a riddle about cars getting caught in traffic jams. You could say that one really stuck with me.
In the original puzzle, there were N cars on a long, straight highway with a single lane. Each car traveled in the same direction but at a constant speed that was unique and randomly selected. However, if a driver caught up to another, slower car (or a group of cars similarly blocked by that slower car), they remained stuck behind that slower car.
This time around (as suggested by one of the original puzzle’s extension problems), a second lane opens up. The catch is that there is only one entry point into this second lane, so each car has exactly one opportunity to decide whether to proceed into this second lane.
From the first car in the original lane to the last car, each decides whether to make the switch to the second lane as it passes. Fortunately, each car knows the speed of every other car, so each will make the switch provided that it can ultimately proceed at a greater speed (whether on its own or as part of a faster group).
On average, how many total groups of cars will eventually form in the two lanes?
Solution to last week’s Riddler Express
Congratulations to ÐÐ±âÐ¯Ð¡ÐÐ±Ã· Roy McDonald ÐÐ±âÐ¯Ð¡ÐÐ±Ã· of San Mateo, California, winner of last week’s Riddler Express.
For an exponentially increasing quantity, like interest accrued on a principal, you can use the Rule of 72 to approximate the doubling time based on the interest rate. For example, for an interest rate of 4 percent — meaning the exponential growth is 1.04t, with t measured in years — the doubling time is approximately 72 divided by 4, or 18 years.
Last week, your task was to find the one interest rate for which the Rule of 72 told you the exact doubling time.
But before we get to that — yes, 1.04t represents interest that is compounded annually. Meanwhile, interest that is compounded continuously at a nominal “4 percent annual” rate would have been e0.04t, or roughly 1.0408t. Let’s set aside the ins and outs of financial terminology and focus on annual compounding, which was cited in the example given in the puzzle.
Suppose the interest rate was r percent, meaning the exponential growth was (1+r/100)t. To perfectly satisfy the Rule of 72, the amount would have doubled when t was equal to 72/r. As an equation, this meant (1+r/100)(72/r) = 2. Taking the logarithm (or natural logarithm, if you preferred) of both sides gave you the equation 72/r·log(1+r/100) = log(2), and rearranging the variables and the constants gave you r/log(1+r/100) = 72/log(2).
Unfortunately, this last equation was technically a transcendental equation, which meant that it couldn’t be solved analytically. You needed a computer or a calculator for some help! The value of r that solved the equation turned out to be approximately 7.847 percent.
Several solvers, such as Jeremy Hummel, found more precise values. Jeremy calculated the percentage to be 7.84687145301538, while the doubling time was roughly 9.17563138775925 years.
Finally, kudos to all the solvers who attempted to do this analytically. In particular, Amy Leblang used the Taylor expansion for the natural logarithm — i.e., ln(1+x) ≈ x−x2/2+x3/3 — and solved the resulting quadratic equation. With this approach, Amy found that r was approximately 75−25 √(200/3·ln(2)−39), or about 7.87 percent. That was pretty darn close to the exact result!
Solution to last week’s Riddler Classic
Congratulations to ÐÐ±âÐ¯Ð¡ÐÐ±Ã· Rich Erikson ÐÐ±âÐ¯Ð¡ÐÐ±Ã· of Warrenton, Virginia, winner of last week’s Riddler Classic.
Last week, I had been prescribed 1.5 pills of a certain medication every day for 10 days, so I had a bottle with 15 pills. Each morning, I took two pills out of the bottle at random.
On the first morning, these were guaranteed to be two full pills. I consumed one of them, split the other in half using a precision blade, consumed half of that second pill and placed the remaining half back into the bottle.
On subsequent mornings when I took out two pills, there were three possibilities:
- I got two full pills. As on the first morning, I split one and placed the unused half back into the bottle.
- I got one full pill and one half-pill, both of which I consumed.
- I got two half-pills. In this case, I took out another pill at random. If it was a half-pill, then I consumed all three halves. But if it was a full pill, I split it and placed the unused half back in the bottle.
Each pill — whether it was a full pill or a half-pill — was equally likely to be taken out of the bottle.
On the 10th day, I again took out two pills and consumed them. In a rush, I immediately threw the bottle in the trash before bothering to check whether I had just consumed full pills or half-pills. What was the probability that I had already taken the full dosage, meaning I didn’t have to dig through the trash for a remaining half-pill?
After the ninth day I had to have 1.5 pills remaining, which meant I either had a full pill and half-pill or three half-pills. This question was asking for the probability that I had a full pill and a half-pill after the ninth day, rather than three half-pills.
Suppose on a certain day I had F full pills and H half-pills. What were the probabilities for the various numbers of full and half-pills for the next day?
- The probability of getting two full pills was F(F−1)/[(F+H)(F+H−1)], after which I had F−2 full pills and H+1 half-pills.
- The probability of getting one full pill and one half-pill was 2FH/[(F+H)(F+H−1)], after which I had F−1 full pills and H−1 half-pills. The coefficient of 2 came from the fact that I could get the two different pills in either order.
- The probability of getting two half-pills and then a full pill was H(H−1)F/[(F+H)(F+H−1)(F+H−2)], after which I had F−1 full pills and H−1 half-pills. (Some solvers noted that this resulted in the same effect as the previous case.)
- The probability of getting two half-pills and then another half-pill was H(H−1)(H−2)/[(F+H)(F+H−1)(F+H−2)], after which I had F full pills and H−3 half-pills.
You could use these four probabilities to track the transitioning values of F and H from one day to the next. On the first morning, F was 15 and H was 0, which meant on the second morning F had to be 13 and H had to be 1. On the third morning, there was a 6-in-7 chance of having F = 11 and H = 2, and a 1-in-7 chance of having F = 12 and H = 0.
Continuing with these iterative calculations, day by day, solvers Amy Altchuler and Peter Exterkate found that the probability of having F and H both equaling 1 on the 10th morning was 80,529/101,920, or about 79 percent. Peter’s tree diagram is shown below:
Meanwhile, Laurent Lessard astutely used polynomials to arrive at the same answer. Both Laurent and Emily Boyajian further explored the probability of finishing with a full pill and a half-pill on the last day of the treatment as the number of days approached infinity (assuming the number of pills remained 50 percent more than the number of days). With more days, this probability went down — perhaps, asymptotically, to zero. Benjamin Dickman found a 2014 paper by Daniel J. Velleman that explored a similar problem in which the daily prescribed daily dose was 0.5 pills rather than 1.5 pills.
In the limit of this variant of the problem, Velleman found that the number of half-pills (normalized, i.e., divided by the initial total number of full pills) H was related to the number of full pills (also normalized) F by the relation H = −Fln(F). The derivative of H(F) was undefined as F approached zero, meaning the fraction of pills that were full pills eventually went to zero.
Applying this result to the case of 1.5 daily pills is left as an exercise to the reader!2
Want more puzzles?
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!
Want to submit a riddle?
Email Zach Wissner-Gross at firstname.lastname@example.org.