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 growing our nation by sharing the book with loved ones.
And now, to this week’s puzzles!
Riddler Express
From Dave Moran, this is the final boarding call for flight RDLR 100:
Michelle decided to get some extra exercise at the airport by walking toward her departure gate at her normal pace, but on a lengthy moving walkway … going the wrong way. Gotta get those steps in.
After going 100 meters (that is, getting 100 meters closer to her departure gate), Michelle dropped her boarding pass onto the walkway. But she didn’t notice at first and continued walking toward her gate. After walking another 90 seconds, she finally realized that she had dropped her boarding pass. She then immediately turned around and jogged in the direction of the walkway’s movement. Michelle’s jogging pace is exactly twice as fast as her walking pace. She caught up with her boarding pass 10 meters from the start of the moving walkway.
How fast does the walkway move?
Riddler Classic
As suggested by Ian Horn: What time is it?! Game time! As in, time for the inaugural Riddler Rock-Paper-Scissors Tournament!
You know how the game works: Rock beats scissors, scissors beats paper, paper beats rock.
To enter this battle royale, submit the following two things via the button below: 1) The probabilities that you will play rock, paper and scissors on the initial throw of a match, and 2) the conditional probabilities that you will play rock, paper and scissors after you observe your opponent play either rock, paper or scissors.2
I’ll match each of your submissions against every other submission in a series of best-two-out-of-three rock-paper-scissors matches. Whoever wins the most matches will be crowned Rochambeau Raja of Riddler Nation — and there may be a little prize, too.
May the best hand win!
Solution to last week’s Riddler Express
Congratulations to 👏 Mark Tiefenbruck 👏 of San Diego, winner of last week’s Riddler Express!
Last week, we grabbed our smartphones to consider a puzzle about the live game show app sensation, HQ Trivia. In the game, there is a series of 12 multiple-choice questions, each with three choices. Get them all right and you win; miss one and you’re eliminated. How many phones would you need to guarantee victory in this game? And for extra credit, how many phones would you need if each phone was equipped with one “extra life,” allowing you to keep playing even after missing a question?
You’d need \(3^{12}\) — or 531,441 — phones to guarantee a win. To guarantee you’d get the 12th question right, you’d need three phones to cover the three answer choices. To arrive at that point, assume that on each question, you’re splitting your remaining phones up evenly between all the answers, which means two-thirds of your stash of phones is getting eliminated on each response. So to be left with three phones for Question 12, you’d need three phones for each of the answers in Question 11, and nine phones for each of the answers in Question 10, and so on back to the beginning of the game. That’s 3×3×…×3, 12 times. In other words, there are \(3^{12}\) “paths” through the game that you’ll need to cover. If they were iPhone Xs at retail price, that’d set you back $530,909,559.00 (plus tax).
For extra credit, if each of your phones had an “extra life,” you’d need “only” 21,258 phones to guarantee a win. (If you aren’t allowed to use an extra life on the final question, as in the real-life game, you’d need slightly more: 23,107 phones.)
Here’s one way to get to these answers, as adapted from the solution of Guy D. Moore. Let’s describe a phone that never made a mistake, and therefore still has an extra life, as “good” — or “g” for short. Let’s describe a phone that has made a mistake as “bad” — or “b.” Work backward, thinking about what you’ll need to do in the final rounds.
After Question 12, you need 1g or 1b remaining. You just need at least one surviving phone to win.
After Question 11, you need 1g or 3b. One good phone is sure to survive the final round no matter what, or three bad phones can cover all the answer possibilities.
After Question 10, you need 1g + 4b or 9b. Either of these combinations are guaranteed to deliver you one of the sets of phones you want in the following round, regardless of the correct answer.
After Question 9, you need 1g + 20b or 2g + 13b. Either of these will deliver what you need after Question 10.
Continuing this logic, it turns out that 21,258 “good” phones to begin the game is sufficient. This number is about 25 times fewer phones than were required before we factored in extra lives. In fact, this answer is just \(3^{12}/25\), rounded up.
Solution to last week’s Riddler Classic
Congratulations to 👏 Alan Davidson 👏 of New York City, winner of last week’s Riddler Classic!
Last week, a 1-year-old child was playing a matching game app similar to Concentration. There were 10 pairs of cards, each pair depicting a different animal, arrayed facedown. The child selected two cards at random. If they matched, the pair made an animal sound and stayed face up. If they didn’t match, they flipped back down. The game ended when all the cards were face up. If the selection took 1 second, and the animal sound or flipping back down took 1 second, how long, on average, would it take for this game to end?
It would take 200 seconds, or 3⅓ minutes.
As our winner Alan explained, we can solve this problem fairly quickly using dynamic programming. Let T(i) be the expected number of seconds remaining if there are i pairs of cards still facedown. The answer to the Riddler is T(10) — that’s what we want to solve for.
First, let’s start with a base case. It is clear that T(0) = 0. If there are no pairs to flip over, the game is already done and will take 0 seconds to complete. Second, let’s write down the inductive case, that is, the equation that will allow us to move from the base case to higher numbers of pairs remaining. That looks like this:
\begin{equation*}T(i) = 2 + \left(\frac{1}{2i – 1}\right)T(i-1) + \left(1-\frac{1}{2i – 1}\right)T(i)\end{equation*}
In other words, if there are i pairs remaining, it will take us 2 seconds to complete this turn, and there is a 1 out of 2i-1 chance that we reduce the remaining pairs to i-1 and find ourselves in the situation T(i-1). The rest of the time we don’t reduce the remaining pairs and remain in the situation T(i). We can rearrange this equation to get
\begin{equation*}T(i) = 4i – 2 + T(i – 1)\end{equation*}
From there, we can simply build up our expected times, in seconds, for any size of matching game. Put another way, \(T(i) = 2i^2\).
T(0) = 0
T(1) = 2
T(2) = 8
T(3) = 18
T(4) = 32
T(5) = 50
T(6) = 72
T(7) = 98
T(8) = 128
T(9) = 162
T(10) = 200
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.