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-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.
Quick announcement: Have you enjoyed the puzzles in this column? If so, I’m pleased to tell you that we’ve collected many of the best, along with some that have never been seen before, in a real live book! It’s called “The Riddler,” and it will be released in October — just in time for loads of great holidays. It’s a physical testament to the mathematical collaboration that you, Riddler Nation, have helped build here, which in my estimation is the best of its kind. So I hope you’ll check out the book, devour the puzzles anew, and keep adding to our nation by sharing the book with loved ones.
And now, to this week’s puzzles!
Riddler Express
From David Nusbaum, a paradoxical navigational puzzle:
Describe where on Earth from which you can travel one mile south, then one mile east and then one mile north and arrive at your original location.
Hint: There is more than one such location.
Riddler Classic
Jerry Meyers welcomes you to the rug game, kid:
A manufacturer, Riddler Rugs™, produces a random-pattern rug by sewing 1-inch-square pieces of fabric together. The final rugs are 100 inches by 100 inches, and the 1-inch pieces come in three colors: midnight green, silver, and white. The machine randomly picks a 1-inch fabric color for each piece of a rug. Because the manufacturer wants the rugs to look random, it rejects any rug that has a 4-by-4 block of squares that are all the same color. (Its customers don’t have a great sense of the law of large numbers, or of large rugs, for that matter.)
What percentage of rugs would we expect Riddler Rugs™ to reject? How many colors should it use in the rug if it wants to manufacture a million rugs without rejecting any of them?
Solution to last week’s Riddler Express
Congratulations to 👏 Catriona Biggs 👏 of Edinburgh, Scotland, winner of last week’s Riddler Express!
Last week found you operating a going dried-fruit concern. One day, you loaded your drying shed with 1,000 kilograms of apricots, which were 99 percent water. After a day in the shed, they were 98 percent water. How much did they weigh then?
They weighed 500 kilograms.
At first blush, this number seems way too low. Their water content only decreased 1 percentage point, after all. But let’s break it down.
The apricots started off as 99 percent water — that is, 1 percent not water. That 1 percent weighs 10 kilograms.
After the drying, they are 98 percent water — so the 10 not water kilograms are now 2 percent of the total weight.
The percentage of nonwater doubled, which means the weight of the apricots was cut in half. Therefore, the total weight must be 500 kilograms.
Delicious.
Solution to last week’s Riddler Classic
Congratulations to 👏 John Chessant 👏 of Melville, New York, winner of last week’s Riddler Classic!
Last week we flipped a coin to play a game. If we flipped heads, we won. But if we flipped tails, the game continued, and we then needed to flip two heads in a row to win. If we happened to flip another tails before we did that, we then needed three heads in a row to win, and so on. We may flip a potentially infinite number of times, always needing to flip a series of N heads in a row to win, where N is T + 1 and T is the number of cumulative tails tossed. We won if and when we flipped the required number of heads in a row. What are the chances of winning this game?
They are about 71.1 percent.
It’s natural, at first, to guess that your chances of winning are 100 percent. You can flip the damn coin forever, after all, and given enough time it seems like you’d be guaranteed to get the heads you need. But that isn’t quite right. It becomes so difficult to win if you start to toss a few dreaded tails that your chances of winning, even with an infinite number of flips, converge to something less than 100 percent. Don’t get unlucky early, or there may be no coming back.
To figure this one out, it helps to think first about the chances of losing rather than the chances of winning.
Let \(P(T)\) be that probability of losing when we’ve flipped our Tth tail. Two things can happen from here. One, we could flip the \(T+1\) heads in a row that we need to win. This happens with probability \((1/2)^{T+1}\). Or two, we could flip another tails before we do that. That happens the rest of the time. So now \(P(T)\), or probability of losing, looks like this:
\begin{equation*}P(T)=\left( 1 – \frac{1}{2^{T+1}} \right) P(T+1) \end{equation*}
In other words, if we don’t flip our requisite \(T+1\) heads in a row, we wind up in the situation where we lose with probability \(P(T+1)\).
The probability of winning this game is one minus the probability of losing at the beginning, or \(1-P(0)\). We can get to that number by multiplying together all the chances throughout the game that we don’t win and subtracting that from one:
\begin{equation*}1-\prod_{T=1}^{\infty}\left(1-\frac{1}{2^{T+1}}\right) \end{equation*}
That expression equals about 0.711, or about a 71.1 percent chance of winning.
As solver Keith Hudson and others pointed out, this is a special case of the delightfully named Euler (non-totient) function, which itself is a special case of the delightfully named q-Pochhammer symbol.
Tess Huelskamp shared her programmatic approach using Python, and Lewis Curtis Millholland V created a simulator where you can play the game yourself — you don’t even need to go digging in your couch for a real coin!
Happy flipping.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.