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.
From Ben Pyle, how about a nice game of Nim?:
You challenge your friend to a friendly game: You will each take turns taking matchsticks from the arrangement shown below.2 You alternate taking sticks, and the person who picks up the last stick loses. On your turn, you can pick up as many sticks from any single row as you want, but you must pick up at least one stick. You go first.
| | |
| | | | |
| | | | | | |
Do you win? If so, what was your strategy? (Ben also created an applet where you can practice this game against the computer.)
From Brian Sun, an amphibious enigma:
A frog needs to jump across 20 lily pads. He starts on the shore (Number 0) and ends precisely on the last lily pad (Number 20). He can jump one or two lily pads at a time. How many different ways can he reach his destination?
What if he can jump one, two or three at a time? Or four? Five? Six? Etc.
Solution to last week’s Riddler Express
Congratulations to 👏 Valerie Kim 👏 of Toronto, winner of last week’s Express puzzle!
Last week you, a very wealthy aristocrat, owned 25 horses. You were bored one day (you’re bored every day) and decided to amuse yourself by identifying the three fastest horses in your stable. However, your personal racetrack was severely lacking in capacity, and you could only race five horses at a time. What is the minimum number of races you needed to organize to identify your three fastest horses?
You needed to organize seven races.
Here’s how to organize them. First, run five full races so that each horse races once. Keep the top three from each race in contention and eliminate the bottom two. (You can’t be the third-fastest overall if you finish in fourth or fifth.) That leaves 15 horses after five races.
Second, race the five winners from the first step. The winner of this race is sure to be your fastest horse, so you can cement one of your top three and send that fastest horse back to the stable. The second- and third-place horses from this race are still in contention. You can eliminate the bottom two. That leaves 12 horses vying for two spots.
But some of these 12 don’t even need to race again. You can eliminate all the horses that finished behind the second heat’s bottom three the first time around, since they can’t be one of the three fastest horses. That’s a total of six horses you hadn’t already eliminated. And there’s one more horse to rule out: the one that raced with the second heat’s second-place finisher, but finished in third in that first heat. That’s because there are at least three horses we know for sure are faster than that horse. That leaves you with five horses vying for two spots after six races.
Finally, race those five remaining horses. The top two are your second- and third-fastest horses. And you’re done! You can now relax and sip champagne and eat caviar on the deck of your yacht, dreaming of all the very-fast galloping you have ahead of you.
Solution to last week’s Riddler Classic
Congratulations to 👏 Roberts Veics 👏 of Riga, Latvia, winner of last week’s Classic puzzle!
On the game show “The Price Is Right,” there is a segment called the Showcase Showdown. Three players step up, one at a time, to spin an enormous wheel. The wheel has 20 segments at which it can stop, labeled from 5¢ up to $1, in increments of 5¢. Each player can spin the wheel either one or two times. The goal is for the sum of a player’s spins to get closer to $1 than the other players’ sums, without going over. (Any sum over $1 loses. Ties are broken by a single spin of the wheel, where the highest number triumphs.) For what amounts should the first spinner stop after just one spin, assuming the other two players will play optimally?
The first player should stop with 70¢ or higher. She should spin again with 65¢ or lower.
We can get there by working backward, starting with the strategy of the third player to spin the wheel. Call the value of the third player’s first spin \(A_3\), and let \(X_3\) be the total amount that the player needs to achieve to have any chance of winning the Showcase Showdown. For the third player, \(X_3\) is equal to whichever of the other two players’ amounts is highest. (Define all these variables similarly for the other two players: \(A_1\) and \(X_1\), \(A_2\) and \(X_2\).)
Player 3 spins the wheel and it lands on \(A_3\). If \(A_3>X_3\), he will stop, since he’s secured victory. If \(A_3<X_3\), he will spin again. If \(A_3=X_3\), his decision depends on the number of players he’s tied with. If he’s tied with one player, he’ll spin again if \(A_3 \leq 50\) — that’ll give him a better than 50-50 shot of breaking the tie without going over a dollar. Similarly, if he’s tied with two players, he’d have a ⅓ chance of winning the tiebreaker, so he’ll spin again if \(A_3 \leq 65\). That’s the threshold because if he spins at 65 or below, more than ⅓ of the wheel would yield a victory, so it’s worth taking the gamble.
So now that we know what Player 3 will do, we move backward: Player 2 spins the wheel and it lands on \(A_2\). For Player 2, \(X_2\) will equal the total achieved by Player 1. If \(A_2<X_2\), he has no choice but to spin again. If \(A_2=X_2\) and he’s tied with Player 1, he will spin again if \(A_2\leq 65\), giving himself a decent chance of beating the third player and not a huge chance of busting. And if \(A_2>X_2\), the player has a real decision to make. He’s in the lead, but he still has Player 3 to worry about. Computationally, we can find that Player 2 should stop if \(A_2 > 55\). (You can find a table for this decisionmaking process put together by Matthew Olsen, and solver Lucas Fagan shared the Python code he used.)
Moving backward one last time: Player 1 spins the wheel and it lands on \(A_1\). She has no idea what the number to beat will be, but she does know she has Players 2 and 3 to worry about. In this case, \(X_1=0\), so it’s always the case that \(A_1>X_1\). Given the strategies outlined above, computationally we find that Player 1 does best to spin again if and only if \(A_1<70\). Solver Hector Pefo walked through these calculations in detail and shared some more Python code.
You can find an exhaustive treatment of this “The Price Is Right” problem, including an empirical analysis and the complications introduced by the show’s bonuses, in this paper by Rafael Tenorio and Timothy Cason. It turns out that actual players “show a clear bias for failing to spin again when it is optimal to do so, as opposed to spinning again when it is not optimal to do so.”
Want to submit a riddle?
Email me at firstname.lastname@example.org.