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
You have three coins in your pocket, each of which can be a penny, nickel, dime or quarter with equal probability. You might have three different coins, three of the same coin or two coins that are the same and one that is different.
Each of these coins can buy you a string whose length in centimeters equals the value of the coin in cents, i.e., the penny buys 1 cm of string, the nickel buys 5 cm of string, etc. After purchasing your three lengths of string, what is the probability that they can be the side lengths of a triangle?
The solution to this Riddler Express can be found in the following column.
Riddler Classic
On Feb. 23, baseball statistician Jim Passon tweeted out some recent stats for baseball’s God of WAR, Mike Trout:
Yes, Trout’s numbers are gaudy. But what caught social media’s attention was that each stat (batting average, on-base percentage, slugging percentage and OPS) somehow had a corresponding number of games over which Trout averaged those stats. For example, Trout batted .299 over his last 299 games. Could this possibly be a coincidence?
If you think about it for a minute, you’ll realize that there’s nothing magical at all about having a batting average that matches a corresponding number of games.
Suppose a baseball player has four at-bats per game (not including walks), so their batting average is the number of hits they got divided by four times the number of games they played. For many games, it’s possible to have a corresponding batting average that, when rounded to three digits, equals the number of games divided by 1,000. For example, if a player typically gets one hit per game in their at-bats, then they could very well have a .250 average over 250 games.
What is the greatest number of games for which it is not possible to have a matching rounded batting average? Again, assume four at-bats per game.
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to 👏Brian 👏 of Carlton, Washington, winner of last week’s Riddler Express.
In last week’s final CrossProduct™ puzzle (for now), there were four four-digit numbers, with products shown in the following table:
| 1,458 | ||||
| 128 | ||||
| 2,688 | ||||
| 125 | ||||
| 960 | 384 | 630 | 270 | |
As always, a good place to start was to write out the possible ways each row’s product could be written as the product of four digits:
- 1,458 was 2Ă—36. There were two ways to multiply four digits: 2Ă—9Ă—9Ă—9 and 3Ă—6Ă—9Ă—9.
- 128 was 27. There were four ways to multiply four digits: 1Ă—2Ă—8Ă—8, 1Ă—4Ă—4Ă—8, 2Ă—2Ă—4Ă—8 and 2Ă—4Ă—4Ă—4.
- 2,688 was 27Ă—3Ă—7. There was only one way to multiply four digits: 6Ă—7Ă—8Ă—8.
- 125 was 53. There was only one way to multiply four digits: 1Ă—5Ă—5Ă—5.
Next, it was useful to write out the prime factorization of the columns:
- 960 was 26Ă—3Ă—5.
- 384 was 27Ă—3.
- 630 was 2Ă—32Ă—5Ă—7.
- 270 was 2Ă—33Ă—5.
At this point, solver Alice C. noted that the second column was the only column without a factor of 5, which meant the number in the fourth row had to be 5,155. Next, the third column was the only one with a factor of 7. Meanwhile, the first and second columns both had at least three factors of 2, while the fourth column had just one factor of 2. That meant the number in the third row had to be 8,876.
At this point, every column had at least one factor of 3 unaccounted for, all of which had to come in the first row. That meant the last two digits in the first row both had to be 9, while the first two digits were 3 and 6 in some order. To make all the numbers work out, the number in the first row had to be 3,699, and the number in the second row was 8,821.
I hope you enjoyed these last four weeks of CrossProduct™ puzzles. I’m sure a few more will appear later this year.
Solution to last week’s Riddler Classic
Congratulations to 👏 Michael Ringel 👏 of Jacksonville, Florida, winner of last week’s Riddler Classic.
Last week, you had 10 blocks with which to build four steps against a wall. The first step was one block high, the second was two blocks high, the third was three blocks high, and the fourth was four blocks high.
However, whenever you placed a block at ground level, it slid toward the wall until it hit the wall or another block. And when you placed a block atop another block, it similarly slid toward the wall until it hit the wall or another block.
Suppose the four blocks in the bottom row were labeled A, the three blocks in the second row were labeled B, the two blocks in the next row were labeled C, and the topmost block was labeled D. One way to build the steps was to place the blocks one row at a time: A-A-A-A-B-B-B-C-C-D. You could alternatively have placed the blocks one column at a time: A-B-C-D-A-B-C-A-B-A. But you could not have placed them in the order A-B-B-A-A-A-B-C-C-D because that would mean at one point you had more blocks in the second row, B, than in the bottom row, A — a physical impossibility!
How many distinct ways were there to build these four steps using the 10 blocks?
Many solvers worked their way up from smaller numbers of steps, looking for a pattern. With one step (i.e., one block), there was one way: A. With two steps (i.e., three blocks), there were two ways: A-A-B and A-B-A. It started to look like there wasn’t much to this puzzle at all!
But with three steps (i.e., six blocks), there were suddenly 16 ways. Listed alphabetically, they were:
- A-A-A-B-B-C
- A-A-A-B-C-B
- A-A-B-A-B-C
- A-A-B-A-C-B
- A-A-B-B-A-C
- A-A-B-B-C-A
- A-A-B-C-A-B
- A-A-B-C-B-A
- A-B-A-A-B-C
- A-B-A-A-C-B
- A-B-A-B-A-C
- A-B-A-B-C-A
- A-B-A-C-A-B
- A-B-A-C-B-A
- A-B-C-A-A-B
- A-B-C-A-B-A
With four steps (i.e., 10 blocks), the number of ways to build the staircase seemed primed to explode. Listing them out, alphabetically or otherwise, was not reasonable. Solvers like Dean Ballard instead organized the problem using a tree diagram:
The number of ways to reach each state of partial staircase construction can be computed by adding the numbers for the connected states above it. In the end, there were a whopping 768 distinct ways to build the four-step staircase. If you have the patience, you can even watch solver Allen Gu’s four-minute animation of all 768 solutions:
For extra credit, you had precisely enough blocks to build a staircase with N steps — that is, you had N(N+1)/2 blocks. How many distinct ways were there to build such a staircase?
If you tried working through each case (ideally through recursion, or better yet, dynamic programming), the numbers got really big, really fast. Solver James Anderson found that there were 292,864 ways to build a five-step staircase, more than 1 billion ways to build a six-step staircase and almost 50 trillion ways to build a seven-step staircase. (As usual, you can find more of this sequence on OEIS.)
Fortunately, there was indeed a general solution in the case of N steps. Counting the ways a staircase could be assembled was the same as counting what are called Young tableaux (the plural of tableau), or numbered block diagrams, for the specific staircase shape. With N total steps, the number of ways to build the staircase was (N(N+1)/2)! divided by the product of the hook length for each block in the diagram. To learn more about why that was, check out this 1979 paper, dug up by solver Josh Silverman.
I wonder how this problem might be even further generalized. It seems one could have three-dimensional Young tableaux, right? And with those diagrams in hand, one might ask how many sequences there were for building, say, the Great Pyramid of Giza. But I won’t ask that. That number would make my head explode.
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.