mathschallenge.net logo

Climbing Stairs

Problem

It is possible to climb three steps in exactly four different ways.


How many ways can you climb ten steps?


Solution

If there are ten steps, it is necessary to arrive at the 10th step, but all the other steps in between are optional.

Step Number 1  2  3  4  5  6  7  8  9 10
  0 0 0 1 0 1 0 0 0 1

So the binary sequence, 0001010001, represents a journey using steps 4, 6 and 10. To find the total number of ways of climbing 10 steps we need to consider how many binary sequences can be made using 9 binary digits (as step 10 must always be a 1).

Hence there are 29 = 512 ways of climbing ten steps.

What if the maximum number of steps you can climb at a time is two?

Problem ID: 74 (Apr 2002)     Difficulty: 2 Star

Only Show Problem