How Hard Is It To Find A Running Buddy?

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 the next column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.

Programming note: The Riddler is going on vacation for the next two weeks! Enjoy the problems below and have a beautiful remainder of your May.

## Riddler Express

From Steven Pratt, a grocer’s dilemma:

At the grocery store you work at, the evening manager divvies up the store’s 15 aisles and assigns them to the five night stockers on that evening’s shift. Assume that the aisles are assigned randomly.

You have some aisles you prefer over others, so you’re curious: How many different ways can you be assigned three aisles out of the 15? How many different ways are there to assign the 15 aisles to the five different stockers, assuming they are each assigned three aisles? And finally, if the store manager can assign any number of aisles to any stocker, how many possibilities are there?

## Riddler Classic

From Jay Hennig, the meaty mathematics of marathon momentum mates:

Running is more fun when you have someone to run with, but you only want to run with someone if they run about as fast as you do. Perhaps if enough people run together, it becomes more likely that everyone can find a running buddy.

Let’s say there are N people going for a run, and assume that each person’s preferred running speed, call it $$X_i$$, is independent and normally distributed, with a mean of $$\mu$$ and a variance of $$\sigma^2$$. Or, mathematically,

\begin{equation*}X_i \sim N(\mu, \sigma^2)\end{equation*}

Now, for any given person, let’s assume that the person has a running buddy if there’s another person in the group whose preferred speed is about the same as theirs. Specifically, we’ll say that person $$i$$ and person $$j$$ can be running buddies if their preferred speeds are within some number $$s$$ of each other — that is, if $$|X_i - X_j | \leq s$$.

How large does N need to be before the probability of each person having a running buddy is 99 percent? (Assume $$\mu$$, $$\sigma^2$$ and $$s$$ are fixed.)

Extra credit: Using some data — from a large marathon, perhaps — can you provide some empirical estimates of $$\mu$$, $$\sigma^2$$ and $$s$$?

## Solution to last week’s Riddler Express

Congratulations to 👏 Shannon Thaden 👏 of London, winner of last week’s Riddler Express!

If A, B, C, D and E are all unique digits, what values would work with the following equation?

ABC,CDE × 4 = EDC,CBA

The correct values are: A = 2, B = 1, C = 9, D = 7 and E = 8. The final equation then becomes 219,978 × 4 = 879,912.

It might be easy enough to solve this puzzle using a programming language and brute force, simply having your computer run through all of the possible digits until it found the combination that works. But where’s the fun in that? (OK, that actually does sound kind of fun to me.) But we can also arrive at the solution using nothing more than a little bit of logic, a pencil and a piece of paper. This puzzle’s submitter, Charlie Drinnan, explained how:

The digit A must be even because it is in the ones place after some number is multiplied by 4, and it can’t have any carryover because it would add an extra digit to the equation, so it must be less than 3. Also, it can’t be 0, or else it wouldn’t need to be in left-hand side of the equation. Therefore, A = 2. So now we have:

2BC,CDE × 4 = EDC,CB2

The last digit of 4×E must now be 2, which leaves 3 and 8 as possibilities for E. But we also know that the only digits that would work for E are 8 or 9 because it is the first digit of the result of 2XX,XXX × 4. The number that recurs in each: 8. That means E = 8:

2BC,CD8 × 4 = 8DC,CB2

Since E is 8, and 2×4 = 8, then B×4 must have no carryover. Therefore, B is less than or equal to 2, but 2 is already taken, so B is either 0 or 1. So 4×D + 3 (the carryover from 4×8 in the ones place on the left) must end in either 0 or 1. Thus, 4×D must end in either 7 or 8, and since 4×D must be even, then it has to be 8 and therefore B = 1:

21C,CD8 × 4 = 8DC,C12

Since 4×D must end in 8, then D can only be 2 or 7. Since 2 is taken, we know D = 7.

21C,C78 × 4 = 87C,C12

To make 4×1 equal to 7 (remember, we can’t have carryovers in this slot), we will need 4×C to have a carryover of 3. The only values that would work with possible carryovers are if C = 6, 7, 8 or 9. We can remove 7 and 8 as they have been used already. For 6 to work — that is for 6×4 to “equal” 30-something — the carryover from from the multiplication next door, C×4 + 3 (the carryover from 78×4), would have to be at least 6. But that’s impossible — the biggest carryover we could possibly get is from 4×9 + 9 = 45. Thus, C = 9. And voilà:

219,978 × 4 = 879,912

## Solution to last week’s Riddler Classic

Congratulations to 👏 Andrew Lauer 👏 of Ludwigshafen, Germany, winner of last week’s Riddler Classic!

Last week, each of seven stranded pirates engaged in a greedy process to hoard the group’s collective coconuts for themselves. After collecting a bunch of coconuts and placing them in a communal pile, they all went to sleep. But, one by one, each of the seven woke up, bribed a nearby monkey with one coconut, and took and hid a seventh of whatever coconuts remained in the communal pile. At the end of all that, they each again took a seventh of whatever remained in the pile in the morning. If there were N coconuts in the pile originally, what was the smallest possible value of N?

The pile couldn’t be divided that way unless it started with at least 823,537 coconuts. This was a quite a nutritional haul for the pirates! According to Wolfram Alpha, this pile of coconuts contains 12,000 kilograms of fat, almost 6,000 kilograms of carbs and over 1,000 kilograms of protein, along with 2 million percent of a person’s daily dose of vitamin C. Scurvy, be gone!

Because individual coconuts are very hard and can’t be readily divided, this puzzle is an example of a Diophantine problem, or one where the solution must be in terms of integers or, in this case, whole coconuts. (These problems are named after the third-century mathematician Diophantus, an early algebraist. Another example is the infamous Fermat’s last theorem.)

Let’s think about what each pirate does to the communal coconut pile as a mathematical function, which we’ll call $$f$$. Each pirate removes one coconut (for the monkey) and (after hiding 1/7 of the total) leaves 6/7 of the rest. Say there are M coconuts in a pile. Our pirate function can then be defined as $$f(M) = (6/7)(M-1)$$. After seven pirate visits, the initial pile, which had N coconuts in it, has become

\begin{equation*} f(f(f(f(f(f(f(N))))))) = 7k \end{equation*}

where k is each pirate’s final share when they all wake up in the morning. As Laurent Lessard explained, this equation expands to:

\begin{equation*} N = \frac{5,764,801k+3,261,642}{279,936} \end{equation*}

So all that remains to do is to find the smallest integer k such that N in the above equation is also an integer — remember that the coconuts cannot be divided. That gives us k = 39,990 and therefore N = 823,537.

Bon appétit!

## Want to submit a riddle?

Email me at oliver.roeder@fivethirtyeight.com.

## Footnotes

1. Important small print: For you to be eligible, I need to receive your correct answer before 11:59 p.m. Eastern time on Sunday. Have a great weekend!

Oliver Roeder was a senior writer for FiveThirtyEight.