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
It’s the second week in our four weeks of CrossProduct™ puzzles!
This time around, there are six three-digit numbers — each belongs in a row of the table below, with one digit per cell. The products of the three digits of each number are shown in the rightmost column. Meanwhile, the products of the digits in the hundreds, tens and ones places, respectively, are shown in the bottom row.
| 210 | |||
| 144 | |||
| 54 | |||
| 135 | |||
| 4 | |||
| 49 | |||
| 6,615 | 15,552 | 420 | |
Can you find all six three-digit numbers and complete the table?
The solution to this Riddler Express can be found in the following column.
Riddler Classic
From James Bach comes a doozy on doodles:
James likes to draw doodles in the shapes of different polygons. He especially likes to doodle self-intersecting polygons, where the sides cross over each other. (These are distinct from the simple polygons you might have learned about in school, whose sides do not intersect each other.)
The other day, James was able to draw a self-intersecting polygon, each of whose sides intersected with exactly two other sides. Not only that, he drew a polygon with the fewest possible sides that met these criteria.
What was it, you ask? It was a pentagram, which has just five sides.
Lovely. But this got James really thinking — can you draw a polygon where each side intersects exactly three other sides? And if so, what is the minimum number of sides this polygon can have?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Greg ÑÑâÐ of Brooklyn, New York, winner of last week’s Riddler Express.
Last week you had to solve a CrossProduct™ with five three-digit numbers. The products of the three digits of each number were shown in the rightmost column below, while the products of the digits in the hundreds, tens and ones places were shown in the bottom row.
| 135 | |||
| 45 | |||
| 64 | |||
| 280 | |||
| 70 | |||
| 3,000 | 3,969 | 640 |
Once again, a good way to start was to write out the possible ways each row’s product could be the product of three digits:
- 135 was 3×5×9.
- 45 was 1×5×9 or 3×3×5.
- 64 was 1×8×8, 2×4×8 or 4×4×4.
- 280 was 5×7×8.
- 70 was 2×5×7.
Next, many solvers worked out the prime factorization of the three columns’ products, so they could figure out which digit went into which column.
- 3,000 was 23×3×53.
- 3,969 was 34×72.
- 640 was 27×5.
First off, the middle column had an odd product, which meant every middle digit had to be odd. This was only possible if the number in the third row was 818.
Meanwhile, only the middle column had 7s in its prime factorization, which meant the middle digits in the fourth and fifth rows were both 7. As for the first column, since the 8 in the third row accounted for all three factors of 2, that meant the first digits in the fourth and fifth rows had to be odd as well. The number in the fourth row was therefore 578, while the number in the fifth row was 572.
In the middle column of the first and second rows, you still somehow needed to account for four factors of 3. The only way this was possible was if both of these middle digits were 9. To make the remaining products work, that meant the number in the first row had to be 395, while the number in the second row was 591.
There was certainly more than one way to solve this puzzle. For another approach, check out Andrew Heairet’s animated solution:
It looks like this will be the next Twitch sensation!
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Stephen Berg ÑÑâÐ of Troy, New York, winner of last week’s Riddler Classic.
Last week, Cassius the ape was trying to solve Lucas’ Tower puzzle with three disks, all of which start on the same pole. The disks had different diameters, with the biggest disk at the bottom and the smallest disk on top. The goal was to move all three disks from one pole to any other pole, one at a time — but at no point could a larger disk sit atop a smaller disk.
The minimum number of moves to solve the puzzle was not in question — that result is well known: N disks can be solved in exactly 2N−1 moves.
It turned out that Cassius couldn’t care less about actually solving the puzzle, but he was very good at following directions and understood that a larger disk could never sit atop a smaller disk. With each move, he randomly chose from among the set of valid moves.
On average, how many moves would it take for Cassius to solve this puzzle with three disks?
Given the complexity of this problem, several solvers, like Kenneth W and Kei Nishimura-Gasparian, turned to their computers for assistance. After 1 million simulations, Kenneth found that it took Cassius approximately 70.7 moves on average to solve the puzzle.
Many solvers found an exact answer. One way to do this was to map out all 27 possible states of the disks and poles, as Dean Ballard did:
Based on Dean’s diagram, the question then became: If you started at A and randomly walked your way back and forth between adjacent states, what was the average number of steps it took to reach either Z1 or Z2?
“Random walk” problems like these are commonly solved using systems of equations or Markov chains, which was what solver Michael Ringel did:
Either way, you found that the average number of moves to go from A to Z1 or Z2 was 637/9, or about 70.78 — very close to Kenneth’s numerical approximation. If you alternatively interpreted the problem as going from A to Z1 and only Z1 (or to Z2 and only Z2) — an answer I accepted — you had double the result, or 1274/9, due to the bilateral symmetry in the state diagram.
For extra credit, you had to find the average number of moves in the general case of N disks and three poles. The challenge here was that the number of possible states scaled exponentially with N, which made this rather difficult.
Puzzle submitter Toby Berger, along with coauthor Max A. Alekseyev, solved this exact problem in a 2014 paper. It may have been difficult to see from Dean’s or Michael’s drawings, but there was a recursive nature to the diagram of states. Here’s an illustration from Toby’s paper that shows this nature a little more clearly when there were one, two and three disks:
By leveraging the recursive nature of these states, the authors were able to show the general formula for the average number of steps to randomly move the disks from one pole to another: (3N−1)(5N−3N)/(2·3N−1). The average number of steps to randomly move the disks to either of the other poles was then half of that, or (3N−1)(5N−3N)/(4·3N−1).
Finally, Eric Thompson-Martin further studied the shape of the probability distribution for the number of steps it took Cassius to solve the puzzle. According to Eric, this distribution appeared to be a log-normal curve as the number of disks increased.
In any case, I hope no one blew a (SierpiÐâski) gasket solving this!
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.