Another week, another riddler. This one is from Austin Shapiro:
From Austin Shapiro comes a story of stacking that may stump you:
Mira has a toy with five rings of different diameters and a tapered column. Each ring has a “correct” position on the column, from the largest ring that fits snugly at the bottom to the smallest ring that fits snugly at the top.
Each ring she places will slide down to its correct position, if possible. Otherwise, it will rest on what was previously the topmost ring.
For example, if Mira stacks the smallest ring first, then she cannot stack any more rings on top. But if she stacks the second-smallest ring first, then she can stack any one of the remaining four rings above it, after which she cannot stack any more rings.
Here are a four different stacks Mira could make:
This got Mira thinking. How many unique stacks can she create using at least one ring?
Extra credit: Instead of five rings, suppose the toy has N rings. Now how many unique stacks can Mira create?
To find this we brute forced solutions for rings of 3 through 7. Here are visualizations for the five and six ring solutions:
Figure 1: All 45 solutions with five rings
Figure 2: All 104 solutions with six rings
