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

Inspired by a conversation with Matan Protter, this week’s Express involves a happily hopping grasshopper:

A grasshopper is jumping on a number line and starts at its home at zero (i.e., the “origin”). Its first jump will be length 1/2, its second jump will be length 1/4, its third jump will be length 1/8 and so on. (To make this explicit, its Nth jump will be length 1/2^N.)

However, before the jumping begins, it drinks a little too much grasshopper juice and loses all sense of direction. For each jump, it will hop left or right along the number line with equal probability.

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

Extra credit: The next day, the grasshopper again jumps randomly from the origin, but this time with a little more enthusiasm, such that the Nth jump has length 2^N/3^N. After infinitely many jumps, what is the average distance the grasshopper must now travel to return to the origin?

Submit your answer

Riddler Classic

From Daniel Sleator comes a puzzle for those who like to play board games but can’t stand to roll dice:

Daniel is playing a board game with his friends, but unfortunately he is fresh out of dice. He does have a coin, and his friends encourage him to use the coin to simulate a die. For example, if he flips 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 are not assigned to a die roll, so if they come up then Daniel would have to start over and flip the coin another three times.

Facing the possibility of an unbounded number of coin flips, Daniel instead turns to the one magic coin in his possession. He can choose any value of p between 0 and 1 and the coin will land on heads with probability p. But once he has chosen a value for p, it cannot be changed.

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

What is the smallest value of k (i.e., the number of flips) Daniel can use? And what is the corresponding value of p?

Submit your answer

Solution to the last Riddler Express

Congratulations to 👏 Sam Hamilton 👏 of Portland, Maine, winner of the last Riddler Express.

Last week, you had a toast rack with five slots, arranged in an array. Each slot had a slice of toasted bread, which you removed one at a time. However, you were quite superstitious, and you knew it was bad luck to remove adjacent pieces of toast one after the other. (What? You’ve never heard that before? It’s totally a thing!)

How many different ways could you have removed the slices of toast?

Before working with five slices of toast, several solvers got their feet wet by seeing what would have happened with fewer slices. These calculations were relatively straightforward:

• With one slice of toast, there was one way to remove it. Easy!
• With two slices of toast, there were no ways to remove them. Once you picked the first slice, the second one was guaranteed to be adjacent. Too bad!
• With three slices of toast, there were again no ways to remove them. If you started with the middle slice, the second was guaranteed to be adjacent. If you instead started at one of the ends, you next had to select the other end, followed by the middle (which was adjacent). Too bad!
• With four slices of toast, you finally had some options. You couldn’t remove the first slice, because next you’d either have to remove the third slice (which was adjacent to the second and fourth) or the fourth (which meant the last two you removed were the adjacent slices in the middle). One solution was to remove the second, then fourth, then first, then third, which could be represented with the sequence 2, 4, 1, 3. Reflecting this sequence across the middle of the toast rack gave you a second solution: 3, 1, 4, 2. These were the only two solutions for four pieces of toast.

While having four or fewer slices had a total of three solutions, once you hit five pieces of toast the number of solutions grew significantly. While some solvers worked things out by hand, others wrote some computer code to work out all the cases. In the end, there were 14 valid sequences for five slices of toast, which included seven sequences and their reflections:

• 1, 3, 5, 2, 4 and 5, 3, 1, 4, 2
• 1, 4, 2, 5, 3 and 5, 2, 4, 1, 3
• 2, 4, 1, 3, 5 and 4, 2, 5, 3, 1
• 2, 4, 1, 5, 3 and 4, 2, 5, 1, 3
• 2, 5, 3, 1, 4 and 4, 1, 3, 5, 2
• 3, 1, 4, 2, 5 and 3, 5, 2, 4, 1
• 3, 1, 5, 2, 4 and 3, 5, 1, 4, 2

Solver Marcus Dunn made the connection between this puzzle and what has been referred to as Hertzsprung’s problem, which asks: How many ways can you place N kings on an N-by-N chessboard, with one king in each row and one king in each column, such that no two kings are attacking each other? If you imagine placing the kings in the columns one column at a time, you can’t place consecutive kings in neighboring rows — otherwise they’d be able to attack each other. And this was perfectly analogous to not consecutively removing neighboring pieces of toast! For example, here’s how the sequence 1, 3, 5, 2, 4 could be represented with kings on a chessboard:

For extra credit, you had six slices of toast instead of five. Now how many different ways could you have removed the slices without ever removing adjacent pieces one after the other? While many solvers again solved with computer assistance, a few realized that Hertzsprung’s problem corresponded to sequence A002464 on OEIS. There were 90 distinct ways to remove six pieces of toast.

There is a formula for the number of ways to remove N pieces of toast as a function of N — but finding that formula is left as an exercise to the reader. 😁

Solution to the last Riddler Classic

Congratulations to 👏 Jenny Mitchell 👏 of Nashville, Tennessee, winner of the last Riddler Classic.

Last week’s puzzle concerned The New York Times’s new math game, Digits. In each level of the game, you are presented with six numbers and the four basic operations (addition, subtraction, multiplication and division). For example, the six numbers in the game below are 2, 3, 5, 14, 25 and 15.

With each step of the game, you first pick a number, then an operation and then another number. So if you picked 15, then ×, then 5, the 15 and 5 would disappear and be replaced by 75, as shown below:

At this point, you could use the 75 similarly to how you use the other four numbers. The objective of the game is to use the numbers and operations to reach a specific target number. But let’s put that aside for now.

With this gameplay in mind, your challenge was to determine the greatest number of distinct values you could make using anywhere from one number by itself to all six numbers, or anywhere in between. For the purposes of this puzzle, you could take your pick of starting numbers. Also, negative numbers and fractions were allowed — they could be starting numbers or values generated along the way.

For puzzles like these — with presumably very large answers — I find it helpful to compute an upper bound. If the upper bound isn’t too large (i.e., if it’s somewhere in the millions), then a computational approach that tests every possible sequence of number and operation is a plausible strategy.

If you were using all six numbers, then you performed five operations. For the first, you chose among six numbers, then one of the four operations, and finally among the remaining five numbers. Then you repeated this process until you had only one number left. The total number of ways to do this was (6·4·5)·(5·4·4)·(4·4·3)·(3·4·2)·(2·4·1), a product that came to 88,473,600. If you didn’t use all six numbers, there weren’t as many cases to consider: 11,059,200 for five numbers, 460,800 for four numbers, 9,600 for three numbers, 120 for two numbers and six for one number. All told, there were 100,003,326 ways to combine the numbers, a figure within reach for today’s personal computers.

But many of these hundred million or so ways to combine the numbers were mathematically equivalent, and that was the Gordian knot to untangle with this puzzle. To see this, suppose you had three numbers: a, b and c. If you added them, the order by which you added them didn’t matter, since addition is commutative. But if you subtracted them, the order mattered and there were six potentially distinct results: (a−b)−c, (b−a)−c, (c−a)−b, a−(b−c), b−(c−a) and c−(a−b). (There were other ways to order the operations, but they’d always be equivalent to one of these six expressions.)

Solver Jenny Mitchell wrote Python code to navigate these cases and used various combinations of prime numbers for the six starting values. (With smaller or duplicative values, you could wind up with equivalent expressions that weren’t always equivalent. For example, while a·b isn’t equivalent to a+b, they happen to be equal when a and b are both 2.) In the end, Jenny correctly computed that the maximum number of distinct values you could generate in a game of Digits was 974,860.

And wouldn’t you know it, Jenny also identified a closely related OEIS sequence for the “number of inequivalent expressions involving N operands.” Taking the elements of this sequence and multiplying by the corresponding number of ways to choose from among the six starting numbers gave an answer of 6·1 + 15·6 + 20·68 + 15·1,170 + 6·27,142 + 1·793,002, which again came to a grand total of 974,860.

If you want to hack your way through Digits, it’s worth knowing that you can generate almost a million distinct values. So maybe leveraging your number sense is a better way to go.

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.