Introduction and Problem Statement

Riddle 230 from Five Thirty Eight’s column “The Riddler” was suggested by Austin Shapiro. It is as follows:

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?

Solution

With only one ring, there is only one way of creating a stack.

With two rings, we have two cases, each case being the number of rings we’re going to stack. In case 1, we can put either ring on the column for 2 possible stacks. In case 2, we can put both on in the particular order 1,2 from top to bottom for only 1 possible stack. This means there are 3 possible stacks.

With three rings, we have three cases. Analagous to two rings, for case 1 we have 3 possible stacks. For case 2 we can either stack the rings (1,2), (1,3) or (2,3). The first two choices can only be stacked in that particular order. However, the rings (2,3) can be stacked in either order for 4 possible stacks. Case 3 has only 1 possible stack for a total of 3 + 4 + 1 = 8 possible stacks.

Now for four rings. Case 1 gives us 4 possible stacks. Let’s breakdown the 6 possible choices of two rings for case 4. If we choose (1,2), (1,3), or (1,4), there is only the one possible stack for each. If we choose (2,3), (2,4), or (3,4) we have two possible stacks for each giving us a total of 9 possible ways to stack two rings. For case 3, we could stack either (1,2,3), (1,2,4), (1,3,4), or (2,3,4). The first two have only one possible stack each, as ring 1 must be at top and ring 2 must be second. The third has the two possible stacks (1,3,4) and (1,4,3). The fourth has the four possible stacks (2,3,4), (2,4,3), (3,2,4), and (4,2,3). Note that the second one here would force ring 2 to the very top of the column (which is OK). This gives 8 possible stacks for case 3. Finally, case 4 has 1 arrangement for a total of 4+9+8+1=22.

Althogh a pattern may be detected at this point, after doing analyzing five rings, it becomes apparent.

Plugging these four values into OEIS.org will produce 79 results.

Five Rings

Case 1: There are 5 possible stacks with only 1 ring.

Case 2: There are \(\binom{5}{2} = 10\) ways of choosing the two rings. Of the four that include the 1, which are (1,2), (1,3), (1,4), and (1,5), there is only one arrangement allowed. Of the other 6 that do not include the 1, we can arrange each of these in two ways for a total of 4 + 2*(6) = 16 possible stacks.

Case 3: There are \(\binom{5}{3} = 10\) ways of choosing the three rings. Three of these ways result in stacking rings 1 and 2: (1,2,3), (1,2,4), and (1,2,5). Each of these three have only one way to stack. Three more include a 1 but not a 2: (1,3,4), (1,3,5), and (1,4,5). Each of these you are allowed to switch the last two for two each. Three more include a 2 but no 1: (2,3,4), (2,3,5), and (2,4,5). Ring 2 cannot be on bottom for each of these. It can be on top for two different stacks or in the middle for two different stacks, for a total of 4 stacks for each of these three. Finally, the remaining choice of the three rings (3,4,5) can be permuted in all 6 ways. This gives a total of \(3+2*3+4*3+6= 27\) stacks.

Case 4: There are \(\binom{5}{4}=5\) ways of choosing four rings. Two of these include rings 1, 2, and 3: (1,2,3,4), (1,2,3,5) each with 1 possible stack each. One has rings 1 and 2 but no 3: (1,2,4,5) which allows the 4 and 5 to be permuted for 2 possible stacks. One has ring 1 but not ring 2 or 3: (1,3,4,5) which, not allowing ring 3 to be on bottom, allows 4 possible stacks. Finally, the choice of rings (2,3,4,5) will allow the following arrangements top-to-bottom: (2,3,4,5), (2,3,5,4), (2,4,3,5), (2,5,3,4), (3,2,4,5), (3,2,5,4), (4,2,3,5), and (5,2,3,4). This gives a total of \(2+1*2+1*4+1*8 = 16\).

One just needs to be careful that the ring number is never less than the position value of the ring (e.g. ring 2 cannot be in position 3).

Case 5 has 1 possible stack.

This gives a total of 5+16+27+16+1 = 65 different stacks.

Extra Credit

The pattern begins to emerge. The numbers we’re summing on each of these are familiar. They are powers of integers. Notice that for 1 ring, the number of stacks is \(1^1 = 1\), for 2 rings it is \(2^1+1^2 = 3\), for 3 rings it is \(3^1+2^2+1^3=8\), for 4 rings it is \(4^1+3^2+2^3+1^4=22\), and for 5 rings it is \(5^1+4^2+3^3+2^4+1^5 = 65\) with a general value of \(a(n)\) where \[ a(n) = \sum_{k=1}^n (n+k-1)^k . \]

This is not a proof by any means, but simply a conjecture. I look forward to how to think about the number of ways stacking r rings of n as \((n-r+1)^r\). In the meantime, here are a few more values beyond 5.

Riddle230 <- function(n){
   return(sum((n:1)^(1:n)))
}

sapply(1:15, Riddle230)
##  [1]         1         3         8        22        65       209       732
##  [8]      2780     11377     49863    232768   1151914   6018785  33087205
## [15] 190780212

Plugging the first five values into OEIS will result in 3 possible sequences. To be absolutely sure that this was the correct sequence, I wrote a program that checks whether a specific stack is allowable, and another that counts up the number of possible stacks for each integer n. 

## A program that inputs a vector "stack" intended to be a selection of r
## integers chosen from 1:n, and outputs TRUE or FALSE depending on whether
## that stack in that order is allowed or not. 
stackAllowed <- function(stack){
   ## if the stack is in order, then return TRUE
   if(all(sort(stack)==stack)){
      return(TRUE)
      break
   }
   else{
      for(i in stack){
         ## if the position of the ring is greater than the ring, return FALSE
         if(which(stack==i)>i){
            return(FALSE)
            break
         }
         else{
            next
         }
      }
      ## return TRUE if the above never happens.
      return(TRUE)
   }
}


library(combinat)
## 
## Attaching package: 'combinat'
## The following object is masked from 'package:utils':
## 
##     combn
## A function to count the number of stacks of rings for Riddle 230

countStack <- function(n){
   ## let's skip the crazy stuff if n is 1 or 2
   if(n %in% c(1,2)){
      return(ifelse(n==1,1,3))
   }
   ## create the set of rings
   rings <- 1:n
   ## set the count of stacks to 0
   cnt <- 0
   ## cycle through each number of rings that can be chosen
   for(r in rings){
      # create all the combinations of r rings taken from n
      tempstacks <- combn(n,r)
      N <- ifelse(n==r,1,ncol(tempstacks))
      ## cycle through all these combinations
      for(c in 1:N){
         if(N==1){
            cnt <- cnt + 1
            break
         }
         else{
            # create all permutations of each combination
            stackPerms <- permn(tempstacks[,c])
            for(l in 1:length(stackPerms)){
               # if the permutation (stack) is allowed, count it!
               cnt <- cnt + stackAllowed(stackPerms[[l]])
            }
         }
      }
   }
   return(cnt)
}

## Does it work?
sapply(1:7, countStack)
## [1]   1   3   8  22  65 209 732

Seeing that this agrees with the function above, and adding 209 to the sequence narrows it down to sequence A003101, I think we have a winner!