1
$\begingroup$

In how many ways you can make a stack of N disks, such that:

  1. Bottom disk always has radius 1

  2. A disk can be placed on the stack if it radius is <= (maximum of all disk radii below it + 1)

You are given an infinite supply of disks with all radius.

I thought of couple of counting approach but that has lots of overlapping in the already counted solution and I am not able to get rid of it. :(

  • 2
    This isn’t quite clear. (1) Do all the disks have integer radii? (2) Do you have an infinite supply of disks of **each** radius, or do you have only one disk for each of the infinitely many possible radii?2012-04-05
  • 0
    @Brian : I think it is the Towers of Hanoi2012-04-05
  • 0
    @Arjang: No, it very clearly is not the Towers of Hanoi.2012-04-05
  • 0
    @Arjang: Definitely not Hanoi. There the largest disk go below, here disks may be bigger than the one below. Login: A lot is not clear though. Is there exactly one disk below each non-bottom disk or can one stack like a pyramid? Maybe just give the solutions for $N=3$ to clarify the rules.2012-04-05
  • 0
    @BrianM.Scott Disk radii are all positive integers (i.e. 1,2,3,...) and each disk is available in abundance (i.e. infinite supply of disks with radius 1,2,3,...) Hope now I make sense.2012-04-05
  • 0
    @MarcvanLeeuwen You have to make a single tower with a N disks and count in how many possible ways you can do it. Answer for N = 3 is 5. Possible ways are: [1,1,1], [1,1,2], [1,2,1], [1,2,2], [1,2,3] Here, first disk is the bottom disk, second is just above that and 3rd one is top disk. See the constraints are followed. We can't have an arrangement like: [1,3,2] or [1,3,1] Since, maximum radius below second disk is 1. So second disk can have a maximum radius of 1+1 i.e. 2. Hope I'm clear now.2012-04-05

2 Answers 2