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 Keith Wynroe, a battle for the tokens:
You have one token, and I have two tokens. Naturally, we both crave more tokens, so we play a game of skill that unfolds over a number of rounds in which the winner of each round gets to steal one token from the loser. The game itself ends when one of us is out of tokens — that person loses. Suppose that you’re better than me at this game and that you win each round two-thirds of the time and lose one-third of the time.
What is your probability of winning the game?
Riddler Classic
Also from Keith, a dangerous mathematical rendezvous:
During their descent, three paratroopers were blown off course and crash-landed in the desert — an infinite, uniform, two-dimensional plane. They come to at a random time after the crash and must find a way to meet up. The only tool they each have is a device that displays a snapshot of the positions (but not the velocities) of all three of them in the desert. They can each use this tool only once. To make things more annoying, they’ve all been nearly blinded by sandstorms and won’t be able to physically see the others until they’ve all arrived at the same point.
Can you devise a strategy that they can agree upon beforehand and that will guarantee they will meet up? (Note that the snapshot does not indicate the specific identities of the other paratroopers, so a strategy like “let’s agree that A stands still and B and C walk to him” will not work.)
Extra credit: Is there a strategy that would work for any number of paratroopers?
Solution to last week’s Riddler Express
Congratulations to 👏 Gray Safford 👏 of Abington, Pennsylvania, winner of last week’s Riddler Express!
Last week took us to the playground and a three-way dodgeball duel — er, “truel.” Two of the players were fast throwers and one was slow. If a fast player decided to target the slow player, the fast player would eliminate the slow player for sure. If the two fast players targeted each other, each would have a 50 percent chance of surviving. And if the slow player targeted a fast player who wasn’t targeting him, the slow player would eliminate the fast player. If all three players play this game optimally, how likely is each to win?
Each fast player will win 25 percent of the time and the slow player will win 50 percent of the time. It’s a somewhat surprising result. The worst dodgeball player wins the dodgeball game most often — survival of the unfittest! This happens when the players follow these optimal strategies: Each fast player targets the other fast player, and the slow player chooses one of the two fast players at random.
Let’s walk through the strategies for each player to see why the particular strategies above are optimal. Let’s call the two fast players F1 and F2 and the slow player S. Each fast player must decide whether to target the other fast player or the slow player, and the slow player doesn’t really have a substantive choice — he must simply decide which of two identical fast players to target. That gives us eight (2×2×2) combinations of outcomes to look at:
Eight combinations of possible strategies
| Each player’s target … | … and win percentage | ||||||
|---|---|---|---|---|---|---|---|
| Strategy | F1 | F2 | S | F1 | F2 | S | |
| 1 | F2 | F1 | F1 | 0% | 50% | 50% | |
| 2 | S | S | F1 | 50 | 50 | 0 | |
| 3 | F2 | S | F1 | 100 | 0 | 0 | |
| 4 | S | F1 | F1 | 0 | 100 | 0 | |
| 5 | F2 | F1 | F2 | 50 | 0 | 50 | |
| 6 | S | S | F2 | 50 | 50 | 0 | |
| 7 | F2 | S | F2 | 100 | 0 | 0 | |
| 8 | S | F1 | F2 | 0 | 100 | 0 | |
To find the players’ optimal plays, we’re looking for what game theorists call a Nash equilibrium — a set of strategies such that no single player has an incentive to change his own strategy and target a different player. For starters, we can eliminate the strategies listed as Nos. 2 and 6 in the table above — in which both the fast players target the slow player and the slow player targets one of the fast players. In each case, one of the fast players could switch to targeting the other fast player and then win the truel for sure. You can see this in the table: For example, by changing his strategy from targeting the slow player to targeting F2 (moving from strategy 2 to 3), F1 is able to increase his winning percentage from 50 percent to 100 percent.
In fact, the fast players never profit from targeting the slow player; each always does as well or better by targeting his fast rival. And the two cases in which both fast players target the other — strategies 1 and 5 — are indeed Nash equilibria; no player can profitably change his strategy. In those cases, the slow player is indifferent between targeting F1 and targeting F2. From his point of view, the two fast players are indistinguishable. Therefore, to figure out how likely each is to win, we can blend strategies 1 and 5 — the slow player wins half the time and each fast player wins either never or half the time, so one quarter of the time overall. Sometimes it pays to take it slow.2
Solution to last week’s Riddler Classic
Congratulations to 👏 Greg Gothie 👏 of Avalon, New Jersey, winner of last week’s Riddler Classic!
Last week’s Riddler Classic was also a dodgeball truel, but with different types of players. In this case, each player was equally fast but unequally accurate. The players — named Abbott, Bob and Costello — each hit their intended targets with a different likelihood. Abbott is perfectly accurate. You were asked to identify, for every possible combination of the abilities of Bob and Costello, which player was most likely to win the game.
The concepts used to approach this problem are the same as those in the Riddler Express. We want to look for sets of strategies that are Nash equilibria. From there, we can calculate the likelihood of each player winning given those strategies and then identify which player is the likeliest to win. In most cases, these equilibria will have the same flavor as the solution above: Target your strongest opponent.
For example, suppose that Abbott has accuracy of 1, Bob has accuracy of 0.8 and Costello has accuracy of 0.5. In equilibrium, everyone targets their most skilled opponent: Abbott targets Bob, Bob targets Abbott, and Costello targets Abbott. (As in the Express problem, if both players’ throws are successful, we assume that the survivor is determined by a 50-50 coin flip. A second round of throws may be necessary if there is more than one survivor.) Costello is not being targeted, so he survives the first round 100 percent of the time. Bob hits Abbott 80 percent of the time but is himself always hit, so he advances half of that 80 percent, via a coin flip, or 40 percent of the time. Abbott, who is double-teamed, advances only 30 percent of the time, and Costello wins the truel outright in the first round 30 percent of the time.3 In the second round, if there is one, there’s only one player to target. If it’s Abbott versus Costello, Costello wins 25 percent of the time.4 Similarly, if it’s Bob versus Costello, Costello wins one-third of the time. Combining those first- and second-round results: Abbott wins the truel about 23 percent of the time, Bob 27 percent and Costello 51 percent. The worst player wins most often!
After repeating this process for many different values of accuracy, either mathematically or computationally, a picture of the outcomes of this strange game emerges. Solver Guy Moore illustrated which player was most likely to win given the accuracies of Bob (on the x-axis) and Costello (on the y-axis) as they ranged from 0 percent to 100 percent.
We often see the same odd phenomenon as the earlier puzzle: survival of the unfittest. Abbott, the perfectly accurate player, is favored to win in certain cases. However, in other cases, like our 0.8 and 0.5 example, a player actually does better in the game the worse he or she is at playing it.
While the problem only asked you to consider the case where one player was perfectly accurate, solver Laurent Lessard went above and beyond, animating this outcome chart for various levels of Abbott’s accuracy. It’s a beautiful illustration of the totally weird game theoretic interactions of the truel. “Prepare to have your mind blown,” Laurent wrote.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.