Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,¹ and you may get a shoutout in the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter or send me an email.

Riddler Express

From Vince Vatter comes a puzzle about a “party” game that’s all the rage these days:

In the game Digit Party (of which Vince was one of the creators!), you place 25 digits one at a time on a five-by-five board. Whenever two of the same digits are placed in adjacent squares (whether horizontally, vertically or diagonally adjacent), you get a number of points equal to the value of those two digits.

For example, if you place four 1s in a row, you get 3 points — there are three adjacencies. If you instead place those 1s in a two-by-two square, you get 6 points — there are now six adjacencies (including the two diagonals).

The game is a lot of fun, and this week’s Express is inspired by it.

Suppose you have to place 16 1s on an infinite grid that is initially empty. What is the maximum number of points you can earn?

Extra credit: Suppose you have to place 100 1s on an infinite grid that is initially empty. What is the maximum number of points you can earn? What about 1,000 1s?

Submit your answer

Riddler Classic

From Paul Pudaite comes an opportunity for you to save the world:

Later this year, aliens will visit Earth and announce that they intend to blow up the planet. (Lovely.)

However, they present you with a challenge. If you successfully complete the challenge, they’ll blow up another planet instead (probably Neptune, because why not).

The aliens have telepathically assigned each of the 8 billion human beings on Earth a unique random number, uniformly distributed between 0 and 1. Each human being knows their own number, but no one else’s. Your challenge is to identify the person with the highest number.

The aliens will allow you to ask a single yes-or-no question² to all 8 billion people. This question must be the same for everyone and will be answered simultaneously by everyone. The aliens have courteously agreed to aggregate the data for you as to who answers your question yes or no.

What question would you ask, and what are your chances of saving the world?

Submit your answer

Solution to the last Riddler Express

Congratulations to 👏 Shantanu Gangal 👏 of Mumbai, India, winner of last week’s Riddler Express.

Last week, a grasshopper was jumping on a number line and started at its home at zero (i.e., the “origin”). Its Nth jump had length 1/2^N, so its first jump had length 1/2, its second jump had length 1/4, its third jump had length 1/8 and so on.

However, before the jumping began, it drank a little too much grasshopper juice and lost all sense of direction. For each jump, it hopped left or right along the number line with equal probability.

After infinitely many jumps, the grasshopper’s head was once again clear and it wanted to return home to the origin. On average, what was the expected distance it traveled to return home? (Note that no matter which side of the origin the grasshopper was on, “distance” was defined as being zero or positive, but couldn’t be negative.)

Since the grasshopper was equally likely to jump left or right at any given point, by symmetry its average position always remained zero. That is, averaging the various positive landing positions to the right of the origin and the negative positions to the left of the origin always gave you exactly zero. And so some readers thought zero was the answer.

However, this puzzle asked for the average distance to the origin, which was defined as positive whether the grasshopper was to the left or to the right. So while the average position was always zero, the average distance to the origin was positive as soon as the grasshopper took its first jump.

Suppose the grasshopper’s first jump was to the right, meaning it was now at 1/2. Since subsequent jumps were equally likely to be left or right, its average position from this point forward remained at 1/2. What’s more, there was no way for the grasshopper to ever cross over to the left side of the origin again. Even if all the remaining jumps were to the left, the grasshopper would have been at 1/4, then 1/8, then 1/16 and so on, returning to the origin after infinitely many jumps. Because you never had to worry about crossing the origin again, the average distance the grasshopper had to travel was simply 1/2.

Now suppose the grasshopper’s first jump was to the left, meaning it was now at -1/2. This time around, it could never return to positive territory, even if all the remaining jumps were to the right. And so, once again, the average distance the grasshopper had to travel was simply 1/2.

That first jump was equally likely to be left or right, so the overall average distance was the average of 1/2 and 1/2, which was, of course, 1/2.

For extra credit, the grasshopper’s Nth jump was no longer 1/2^N, but rather the slightly larger 2^N/3^N. After infinitely many jumps, what was the average distance the grasshopper now traveled to return to the origin?

With this greater jumping distance, it was now possible for the grasshopper to cross the origin. For example, suppose the first jump was to the right, so that the grasshopper was at 2/3. If all remaining jumps were to the left, they totaled 4/9 + 8/27 + 16/81 + …, a geometric series that summed to 4/5. After infinitely many jumps, the grasshopper’s final position was 2/3 − 4/5, or -2/15 — i.e., in negative territory. Because the grasshopper could cross the origin (and even do it multiple times), calculating the average distance was much trickier.

Solver Josh Silverman even composed a two-verse limerick — in what I believe is a first for The Riddler — about the complexity of the extra credit:

A grasshopper’s steps scaled by s,
It hopped and it leapt with finesse.
With s under one-half,
Each point had one path,
A solvable riddle, no mess.

But when s expands,
Points have multiple strands.
Too long to fade,
Neat solving forbade,
A labyrinthine mess on our hands.

A few solvers, including Michael Coffey and Charlie Drinnan, created vast probability trees to compute the average, which turned out to be approximately 0.7421844.

By the way, if you enjoyed this riddle, you might enjoy the 2003 paper, “Random walk with shrinking steps,” which analyzes the probability distribution of the grasshopper’s final position. Things really get crazy when the ratio of successive jumps is the golden ratio, as shown below:

Solution to the last Riddler Classic

Congratulations to 👏 Ivor Traber 👏 of Waterloo, Ontario, winner of last week’s Riddler Classic.

Last week, you were playing a board game, but unfortunately you were fresh out of dice. However, you did have a coin that you could use to simulate a die. For example, if you flipped the coin three times, then HHH could represent a 1, HHT a 2, HTH a 3, HTT a 4, THH a 5 and THT a 6. However, in this schema, the flips TTH and TTT were not assigned to a die roll, so if they came up then you’d have to start over and flip the coin another three times.

Facing the possibility of an unbounded number of coin flips, you instead turned to the one magic coin in your possession. You could choose any value of p between 0 and 1 and this coin would land on heads with probability p. But once you chose that value for p, it couldn’t be changed.

Using this magic coin, you wanted to simulate a die with at most k flips, so that all sequences of k flips could be split into six groups of equal probability.

What was the smallest value of k (i.e., the number of flips) you could use? And what was the corresponding value of p?

You immediately knew that k couldn’t be 1 or 2, since that didn’t even generate enough distinct cases to represent six die rolls. So the first value to check for k was 3. Once again, there were eight possible sequences of flips, which could be split into four categories of equal probability regardless of the value of p:

• HHH
• HHT, HTH and THH
• HTT, THT and TTH
• TTT

However, trying various combinations, you found that there was no way to reorganize these eight sequences into six groups of equal probability, no matter what value of p you used. The same was true when k was 4. (Solver Dan Swenson recognized this immediately, having solved a similar Riddler Classic several years ago.)

But when k was 5, the impossible suddenly became possible. There were 32 possible sequences of flips, which could be split into six categories:

• HHHHH
• Four heads and one tails (five permutations)
• Three heads and two tails (10 permutations)
• Two heads and three tails (10 permutations)
• One heads and four tails (five permutations)
• TTTTT

You could form five distinct groups, each composed of one permutation from the second category (e.g., HHHHT), two permutations from the third category, two permutations from the third category and one permutation from the fourth category. All five of these groups had equal total probabilities, and in terms of p these were p⁴(1−p) + 2p³(1−p)² + 2p²(1−p)³ + p(1−p)⁴. To form the sixth group, you had to combine HHHHH and TTTTT, which had a combined probability of p⁵ + (1−p)⁵.

To calculate the value of p, you had to set the two previous expressions equal to each other and solve a quintic equation. Thanks to the symmetry of how these six groups of flip sequences were organized, there were two possible solutions: p could either be approximately 0.30334 or approximately 0.69666.

Want more puzzles?

Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!

Want to submit a riddle?

Email Zach Wissner-Gross at riddlercolumn@gmail.com.