How Many Ways Can You Build A Staircase?

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,1 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.

## Riddler Express

This is the fourth and final week of CrossProduct™ puzzles — for now. This time, there are four four-digit numbers — each belongs in a row of the table below, with one digit per cell. The products of the four digits of each number are shown in the rightmost column. Meanwhile, the products of the digits in the thousands, hundreds, tens and ones places, respectively, are shown in the bottom row.

1,458
128
2,688
125
960 384 630 270

Can you find all four four-digit numbers and complete the table?

The solution to this Riddler Express can be found in the following column.

## Riddler Classic

From Jesse Nicholas comes a puzzle that is four small steps for a human, one giant leap for humankind:

You have 10 blocks with which to build four steps against a wall. The first step is one block high, the second is two blocks high, the third is three blocks high and the fourth is four blocks high.

However, the ground ever-so-slightly slopes down toward the wall, and both the floor and the blocks are a little bit slippery. As a result, whenever you place a block at ground level, it slides toward the wall until it hits the wall or another block. And when you place a block atop another block, it will similarly slide toward the wall until it hits the wall or another block.

Suppose the four blocks in the bottom row are labeled A, the three blocks in the second row are labeled B, the two blocks in the next row are labeled C and the topmost block is labeled D. One way to build the steps would be to place the blocks in the following order, one row at a time: A-A-A-A-B-B-B-C-C-D. You could alternatively place the blocks one column at a time: A-B-C-D-A-B-C-A-B-A. But you could not place them in the order A-B-B-A-A-A-B-C-C-D because that would mean at one point you have more blocks in the second row, B, than in the bottom row, A — a physical impossibility!

How many distinct ways are there to build these four steps using the 10 blocks?

Extra credit: Suppose you have precisely enough blocks to build a staircase with N stairs. How many distinct ways are there to build this staircase?

The solution to this Riddler Classic can be found in the following column.

## Solution to last week’s Riddler Express

Congratulations to 👏Rick McGeer 👏 of Orinda, California, winner of last week’s Riddler Express.

In last week’s CrossProduct™ puzzle, there were seven three-digit numbers, with products shown in the following table:

280
168
162
360
60
256
126
183,708 245,760 117,600

As always, a good place to start was to write out the possible ways each row’s product could be the product of three digits:

• 280 was 5×7×8.
• 168 was 3×7×8 or 4×6×7.
• 162 was 2×9×9 or 3×6×9.
• 360 was 5×8×9.
• 60 was 2×5×6 or 3×4×5.
• 256 was 4×8×8.
• 126 was 2×7×9 or 3×6×7.

Next, many solvers, like Lisa M. Campana, worked out the prime factorization of the three columns’ products, so they could figure out which digit went into which column.

• 183,708 was 22×38×7.
• 245,760 was 214×3×5. (Yes, that exponent was 14.)
• 117,600 was 25×3×52×72.

Since the first column’s product had neither three factors of 2 nor a factor of 5, that meant the first digit of the first row’s number had to be a 7. Had its second digit been a 5, there would have been no way to get 14 factors of 2 out of that middle column. That meant the number in the first row was 785. And because the first column’s product had only two factors of 2, that meant the number in the sixth row was 488.

At this point, all that was left unaccounted for in the first column’s product was eight factors of 3, which meant all the remaining digits in the first column had to be either 3 or 9. Because the third digit in the second row had to be a 7, that meant the number in the second row was 387. Similarly, the number in the seventh row was 927.

Finally, for the middle column to get its remaining four factors of 2 and for the third column to get its remaining two factors of 2, the number in the third row had to be 963, the number in the fourth row had to be 985 and the number in the fifth row had to be 354.

Despite all this pleasant deduction, it has come to my attention that several solvers have written code that will solve any CrossProduct™. But where’s the fun in that? Delete that code and get back to solving by hand, please.

## Solution to last week’s Riddler Classic

Congratulations to 👏 Guy D. Moore 👏 of Darmstadt, Germany, winner of last week’s Riddler Classic (and a previous puzzle submitter).

In the game of Riddler Jenga, you started with one block and then placed more blocks on top of it, one at a time. Every block had the same alignment (e.g., east-west).

Importantly, whenever you placed a block, its center was picked randomly along the block directly beneath it. For example, the following animation showed Riddler Jenga towers that were randomly constructed before ultimately collapsing when the fifth, 10th and 15th blocks were placed. The block highlighted in red was the one above which the blocks were no longer balanced.

On average, how many blocks did you have to place so that your tower collapsed — that is, until at least one block fell off?

At first this looked like a physics problem — and it was. But instead of thinking about tilts and torques, there was a mathematical way to restate the problem, as noted by solver Miha Gazvoda. The tower collapsed whenever the center of mass of the topmost k blocks did not lie above the block directly beneath them. If this was not true for any value of k, then the tower was stable.

Let’s see how this works as we increase the number of blocks. Like solver Emma Knight did, let’s suppose each block had a length of 2, and that the first block was placed along the interval [-1,1]. That meant the second block’s center was randomly chosen between -1 and 1. No matter where the second block was placed, its center was always over the first block (by definition), and so a tower of two blocks never collapsed.

But collapse was possible once the third block was thrown into the mix. If the center of the second block was at position x and the center of the third block was at position y relative to the second block — meaning its center was at the absolute position x+y — then their center of mass was at the average of their positions, or (2x+y)/2. When this was greater than 1 or less than -1 — that is, beyond the extent of the bottommost block — the tower would collapse. And because x and y both varied uniformly between -1 and 1, this probability corresponded to the fraction of the 2×2 square below that was shaded blue, which was 1/8.

That was three blocks. But to find the expected number of blocks for collapse, you had to find the probabilities that the tower would first collapse at any given number of blocks, and then use them to find a weighted average. This turned out to be quite hard.

For example, consider the case of four blocks, where the relative coordinates of the second, third and fourth blocks were x, y and z, respectively. For the topmost two blocks to initiate the collapse, you needed (2y+z)/2 to be greater than 1 or less than -1. Alternatively, the topmost three blocks could initiate the collapse, which happened when (3x+2y+z)/3 was greater than 1 or less than -1. However, for the tower to have collapsed with the fourth block, it couldn’t have collapsed with the third block, which meant (2x+y)/2 was between -1 and 1, corresponding to the unshaded hexagon in the above diagram. With the three variables x, y and z, that meant you were working in three dimensions, and that you wanted to find the fraction of the following hexagonal prism that was shaded blue:

With some careful volumetric analysis, this probability turned out to be 43/252.

Next, with five blocks, you had to calculate the four-dimensional shaded region of a 4-polytope and … just kidding. This was an excellent time to abandon geometry and instead just simulate the dang thing via computer. No one solved this problem analytically.

(Maybe I did it myself, but I’m not sharing.)

(Okay, I didn’t.)

Simulating millions of towers, James Kilfiger found the average number of blocks at which the tower collapsed was approximately 7.11. Here’s a smoothed histogram showing when the tower collapsed, courtesy of George Dontas of Athens, Greece:

I love starting with a problem that is essentially dimensionless, and then having a constant that just seems to pop out of nowhere. This week’s answer of 7.11 might very well be the sum of some wackadoodle infinite series, with hidden connections to 𝜋 or e. Who knows?

## Want more riddles?

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.

## Footnotes

1. Important small print: In order to 👏 win 👏, I need to receive your correct answer before 11:59 p.m. Eastern time on Monday. Have a great weekend!

Zach Wissner-Gross leads development of math curriculum at Amplify Education and is FiveThirtyEight’s Riddler editor.