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, a vexing vehicular puzzle:
Andrea and Barry both exercise every day on their lunch hour on a path that runs alongside a parkway. Andrea walks north on the path at a steady 3 mph, while Barry bikes south on the path at a consistent 15 mph, and each travels in their original direction the whole time — they never turn around and go back the other way. The speed limit on the parkway is the same in both directions and vehicle traffic flows smoothly in both directions exactly at the speed limit.2
In order to pass the time while they exercise, both Andrea and Barry count the number of cars that go past them in both directions and keep daily statistics. After several months of keeping such stats, they compare notes.
Andrea says: “The ratio of the number of cars that passed me driving south on the parkway to the number of cars that passed me driving north was 35-to-19.”
Barry retorts: “I think you’re way off. The ratio for me was 1-to-1 — the number of cars that passed me going south was the same as the number that passed me going north.”
Assuming Andrea and Barry are both very good at stats, what is the speed limit on the parkway?
Riddler Classic
From Al Zimmermann, inspired by the work of mathematician John Conway, a specific shuffling problem:
Suppose you have a shuffled deck containing 13 cards. Each card has a number from 1 to 13 and each number appears on exactly one card. You look at the number on the first card — suppose it’s k — and then you reverse the order of the first k cards. You continue this procedure — reading the first card’s number and then reversing the order of the corresponding number of cards — until the first card reads 1. Clearly, the number of reversals depends on the initial order of the cards. What is the largest number of reversals that you might have to do? What order are the cards in before you start shuffling the maximum-reversal deck?
Extra credit: What if the deck contains 53 cards?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Brittney Lew ÑÑâÐ of Greenwich, Connecticut, winner of last week’s Riddler Express!
Last week, you began with one token, and I began with two tokens, and we played a game of skill that unfolded over a number of rounds. The winner of each round got to steal one token from the loser. The game itself ended when one of us was out of tokens — that person lost. Further, you were better than me at this game and won each round two-thirds of the time and lost one-third of the time. What was the probability that you would win this game?
It was 4/7, or about 57 percent.
Call your chance to win the game P1 when you have one token and P2 when you have two tokens. At the start of the game, you have a 2/3 chance to steal my token and a 1/3 chance to lose outright, or:
P1 = (2/3)(P2) + (1/3)(0)
If you do win a second token, you then have a 2/3 chance to win outright and a 1/3 chance to fall back to one token, or:
P2 = (2/3)(1) + (1/3)(P1)
We can substitute the second equation into the first:
P1 = (2/3)[2/3 + (P1)/3] = 4/9 + 2(P1)/9
That simplifies to P1 = 4/7, our solution!
Solver Jimmy Tancabel shared a graph of the probability of your winning this game for every probability of your winning an individual round’s token. Our specific solution is pointed at by the blue lines:
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Josh Feingold ÑÑâÐ of Chicago, winner of last week’s Riddler Classic!
Last week, three paratroopers were blown off course and crash landed in a desert, represented mathematically by an infinite, uniform plane. They woke up at a random time and in random places and wanted to follow their emergency plan to rendezvous, all arriving at one specific point in the desert. The only tool each had at his disposal was a device that could display — just once! — a snapshot of the positions (but not the velocities or identities) of all three of paratroopers. Your task: Devise a strategy that guarantees that the three will rendezvous.
This Riddler, perhaps more than any other, generated vigorous debates online. It became a fascinating mathematical Rorschach test thanks, in part, to the rich universe of possible rendezvous strategies and also thanks, perhaps in larger part, to some ambiguities built into the puzzle. The latter was the fault of your humble puzzle editor. Are the paratroopers guaranteed to wake up at the exact same time? Are the paratroopers able to choose their direction of travel — can they navigate by the sun or an internal compass of some kind? Do they know which way is true north? The paratroopers don’t know who the others pictured on their device are, but does each know which he is? Do they have access to some kind of random number generator? Are they wearing watches? The answer to each question changes the flavor of what the paratroopers are able to do and therefore what strategies would be successful. Never deterred, Riddler Nation turned these ambiguities into some exciting mathematical strategies.
If the paratroopers can identify themselves on the device and can navigate well, the problem admits a fairly trivial solution: Two of them can simply walk to the northernmost paratrooper, who stays put. (If you’re worried about the rare case of ties for northernmost, you could break the tie by choosing the westernmost and so on.)
Solver Tim Black, who authored a lovely blog post of his desert rendezvous thinking, also hypothesized that the three could agree ahead of time to meet at the centroid of the triangle formed by their positions, like so:
However, this doesn’t work if the paratroopers wake up at different times or use their locating devices at different times! In that case, they would calculate different centroids, head for different points, and never meet up, dying a slow desert death, illustrated like so:
So, Tim and others next tackled what to do when the paratroopers are excellent directional navigators but wake up at different times. The paratroopers can leverage the fact three points uniquely define a circle, and therefore they could walk, each at his own unique speed, along this circle, eventually meeting up. Adam Chatterley illustrated how that process might unfold:
Tyler Barron argued that this sort of solution could be extended to the extra credit case of more than three paratroopers. “For four we can use an ellipse with horizontally constrained foci, for five we can use an ellipse with unconstrained foci, etc.”
There are other approaches. Ben Weiss proposed one solution based on prime numbers and Traveling Salesman paths, and another based on Fermat points, which minimize the total distance of travel.
Michael Schapowal proposed a robust solution where the paratroopers simply embark on a random walk — one paratrooper decides to stand still, while the others walk in constantly randomized directions, for as long as it takes. They are guaranteed to arrive at their compatriot’s location … eventually. I suppose I should have stipulated they had infinite rations, as well.
Jim A., perhaps most realistically, suggested that no solution exists, pointing to research saying that people cannot walk in straight lines in unfamiliar terrain.
Thank you all for walking through this desert of mathematical ambiguity. I’ll try to ensure that the rains of clarity fall in the future.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.
CORRECTION (March 2, 2018): An earlier version of this Riddler column misspelled Al Zimmermann’s name. It has since been corrected.