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.
Riddler Express
From Dave Moran, into the woods:
Xavier and Yolanda are on a road trip when they notice a hiking trailhead on the side of the highway. They decide to check it out and pull into the parking lot. The sign at the trailhead describes the trail like this: “Flat, with excellent scenery on both sides. The trail dead-ends about 3 miles from this trailhead.”
Xavier and Yolanda agree to go hiking on the trail. But Yolanda hikes at a faster pace than Xavier, and each prefers to hike at his or her own steady pace instead of adjusting it to stay with the other person. Neither Xavier nor Yolanda knows exactly how fast either of them walk; they only know that Yolanda is faster. To further complicate matters, both of their cellphones are dead, they have no other timepieces of any kind, and they have no idea, as they stand at the trailhead, whether there are any distance markers or memorable landmarks along the trail.
How can Xavier and Yolanda plan their hike such that (1) they start hiking down the trail at the same time, (2) they each hike at their own steady pace the entire time, (3) they only hike up and down the trail (i.e., no hiking in the parking lot or on the highway), and (4) they arrive back at the trailhead at the same time?
Riddler Classic
From Taylor Firman, the bell rings and it’s time for gym:
The following delightful video has been making the viral rounds:
Let’s call this game rock-paper-scissors-hop. Here is an idealized list of its rules:
- Kids stand at either end of N hoops.
- At the start of the game, one kid from each end starts hopping at a speed of one hoop per second until they run into each other, either in adjacent hoops or in the same hoop.
- At that point, they play rock-paper-scissors at a rate of one game per second until one of the kids wins.
- The loser goes back to their end of the hoops, a new kid immediately steps up at that end, and the winner and the new player hop until they run into each other.
- This process continues until someone reaches the opposing end. That player’s team wins!
You’ve just been hired as the gym teacher at Riddler Elementary. You’re having a bad day, and you want to make sure the kids stay occupied for the entire class. If you put down eight hoops, how long on average will the game last? How many hoops should you put down if you want the game to last for the entire 30-minute period, on average?
To get you started, here’s how a single game might unfold:
Solution to last week’s Riddler Express
Congratulations to 👏 JiHwan Moon 👏 of Seoul, South Korea, winner of last week’s Riddler Express!
Last week, I asked you to take a standard deck of cards and pull out the numbered cards (the cards 2 through 10) from one suit. After shuffling them and laying them face down in a row, you flipped over the first card. If you correctly guessed whether the next card in the row was bigger or smaller, you could keep going. If you played this game optimally, what was the probability that you could get to the end without making any mistakes?
It’s about 17 percent.
The optimal strategy is fairly simple: You should say “bigger” if there are more bigger cards remaining and “smaller” if there are more smaller cards remaining. (If there is an equal number of bigger and smaller cards, you can just guess randomly — for simplicity, let’s say you always guess “bigger” in this case.)
Getting to the probability of winning is a little trickier. Because we are dealing with cards 2 through 10, we are dealing with nine cards. Therefore, there are 9! — or 362,880 — ways that these cards might be arranged. What we need to do next is figure out how many of those arrangements will lead us to a win. If we divide the number of winning arrangements by the total number of arrangements, we’ll get the probability that we win the game.
To ease into these calculations, let’s first imagine a smaller game — just two cards, numbered 2 and 3. In this case, you’re guaranteed to win because you’ll know for sure after seeing the first card whether the second and final card is bigger or smaller. Now, let’s move to a slightly larger game — three cards, numbered 2, 3 and 4. Things get a little more interesting here. There are six (3!) decks you might face. Five of these — every arrangement except 324 — leads to a win. In a game with four cards, there are 24 (4!) possible decks, 16 of which lead to victory.
Solver Keith Hudson developed a clever way to find and visualize the underlying pattern here, which we can extend to solve our nine-card game. Imagine numbers in a pyramid, where each row going down represents a game of a certain size: one card, two cards, etc. The numbers in each row of the pyramid add up to the number of ways you can win that game. From left to right, the individual numbers in each row are the number of ways you can win that game if you happen to start with the lowest card, then the second-lowest card, and so on to the highest card. For example, in a one-card game, there is only one card you can start with and one way to win. In a two-card game, there are two cards you can start with, and one way to win in each of those cases. In a three-card game, there are three cards you can start with, and two, one and two ways, respectively, to win in those scenarios. The first six rows look like this:
1 1 1 2 1 2 5 3 3 5 16 11 8 11 16 62 46 35 35 46 62
We can build this pyramid with some pretty simple rules. If, for example, we start by drawing either the smallest or biggest card in our deck, we are essentially then playing the game as if we had started with one fewer card, so the outer numbers (for example, 62 and 62 in the bottom row above) in the rows are the sums of the whole row that comes above them.
You’ll notice that you want to draw the biggest or smallest cards — the closer you get to the middle, the fewer ways you have to win the game. For example, say you’re playing with six cards (the last row in our pyramid above). If you draw the biggest or smallest card (the outer numbers of the row), you have 62 ways to win. But if you draw the third-biggest or third-smallest, you have only 35 ways to win.
You’ll also notice that the numbers have a relationship with each other. If a number is on the interior of the pyramid and on the left side, it is the sum of everything above it and to the right. Same goes for a number on the interior of the pyramid and to the right — it’s the sum of everything above it to the left.
Why is this? Because if we draw the biggest or smallest cards (the outer numbers), it’s like we haven’t added a new card at all — we have the same number of ways to win as we did in total in the smaller game (the row above). But as you move closer to the middle of a row, you’re adding more and more complications, so your options to win are fewer. Remarkably, though, the past games help us calculate the number of winning paths in the new ones.
Continuing in this way, the sum of the numbers in the ninth row of this pyramid is exactly 62,000. So our probability of winning is 62,000/362,880, or about 17 percent.
Solution to last week’s Riddler Classic
Congratulations to 👏 Nicholas Ellens 👏 of Longmont, Colorado, winner of last week’s Riddler Classic!
Last week, Ariel, Beatrice and Cassandra — three brilliant game theorists — were bored at a game theory conference and devised the following game to pass the time. They drew a number line and placed a stack of $1 on the 1, $2 on the 2, $3 on the 3 and so on to $10 on the 10. Each player had a personalized token. They took turns — Ariel first, Beatrice second and Cassandra third — placing their tokens on one of the money stacks (only one token was allowed per space). Once the tokens were all placed, each player got to take every stack that her token was on or was closest to. (If a stack was midway between two tokens, the players split that cash.) How did this game play out?
Ariel begins by placing her token on the $5. Beatrice then places her token on the $9. And finally Cassandra places her token on the $8. Ariel wins $21 (1+2+3+4+5+6), Beatrice wins $19 (9+10) and Cassandra wins $15 (7+8). Somewhat surprisingly, going first in this game pays off!
There is no simple and elegant way to get to this solution, as far as I know. Brute force, or something similar to it, is the way to go. In addition to providing computer code, solver Aaron Zinger explained how this works:
“Work backwards: Find Cassandra’s best move in each situation, then Beatrice’s best move given that we now know what Cassandra will do, then finally Ariel’s best move. Ariel’s best outcome is to cause her opponents to cluster at the upper end of the number line, giving her most of the money to herself. If she plays higher than 5, someone will bid lower than her to capture all the lower values. If she plays lower than 5, everyone will still play higher than her, so she’s given up part of the upper range without getting anything in return.”
Ben Phillabaum and Thomas Bassine shared their Python and R code, respectively, on GitHub.
I offered a grab bag of extra credits for this problem: What if there were more players? What if it was played on a clock (with stacks of $1 to $12) rather than a line?
Laurent Lessard, as usual, provided some excellent solutions to these questions. For starters, the first-player advantage appears to hold for any number of players. If there are four players, for example, the payoffs are $17, $15, $13 and $10. If we get up to 10 players, the payoffs just become $10, $9, $8 and so on down to $1. The same is true on a clock. If Ariel, Beatrice and Cassandra were playing that version of the game, Laurent found, Ariel would play on the 7, Beatrice on the 11, and Cassandra on the 10, for final winnings of $31.50, $27.50 and $19.
Finally, solver Sawyer Tabony wrote in to share this extra-credit gem:
This week’s Riddler Classic has a really cool extension. If you want to solve it for higher and higher numbers of stacks of money, you can take it to the continuous limit and have the three players place tokens on different real numbers between 0 and 1. After the three tokens are placed, the payoff is the integral of the function \(f(x)=x\) over the parts of the interval that are closest to your token. You end up needing to solve a few quadratic equations. But it’s all doable on paper, and the final solution is pretty cool.
The optimal play turns out to be: A places a token at \(3/\sqrt{34} -\epsilon\) for some tiny number \(\epsilon\). B places a token at \(5/\sqrt{34} – \delta\) where \(\delta\) is tiny and a function of \(\epsilon\). And C places at the same position as B plus or minus \(\gamma\) for some tiny number \(\gamma\). The payouts work out to A earning 4/17 and B and C each earning 9/68 of the total 1/2 pot.
Sawyer’s work is shown below:
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.