Answer: Flight Of Stairs

I got this problem from Shelley Chang, who says it’s one of her favorites.

Simple trial and error will allow you to get the number of ways to climb one, two, three, four, and five steps. This turns out to be one, two, three, five, and eight.

That probably looks familiar as the Fibonacci sequence. Fibonacci comes into play here because there are two ways to reach the 20^{th} stair. You can go up a single step from the 19^{th} or go up two steps at once from the 18^{th}. So the number of ways you can reach step 20 is the sum of the number of ways you can reach steps 18 and 19. Since the first and second steps correspond to the second and third Fibonacci numbers (depending on where you think the Fibonacci numbers start), the number of ways you can reach the n^{th} stair is the (n-1)^{th} Fibonacci number.

I wrote up a derivation of the formula for this number here.

If you followed the post linked above, it becomes trivial to generalize this question. The maximum number of steps you can take at a time becomes the dimension of the matrix. The matrix has mostly zeroes along the diagonal with ones next to the diagonal, and nothing else until the last row. The last row then has ones in all the columns that correspond to steps you could use to get to the final step. Then by diagonalizing this matrix and exponentiating the eigenvalues, we could find, for example, how many ways there are to get up 932 steps going 4,7, or 9 at a time. (This would require a 9X9 matrix).


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: