## The Staircase problem - Global Math Olympiad.

Asked Where ? :

A typical question from Primary level South East Asian Olympiads.

The Problem :**We have a 10 step staircase. One can climb up 1,2, or 3 stairs at a time. How many ways are there to climb up the stairs ?**

The Solution :

If there is only one stair , number of ways = 1

If there are two stairs, number of ways = (1 stair at a time i.e 1 stair 1 stair) + 2 stairs at a time = 2

If there are three stairs, number of ways = (1 stair,1 stair, 1 stair) + (1 stair, 2 stairs) + (2 stairs, 1 stair) + (3 stairs) = 4

If there are four stairs, number of ways = ( First 1 stair + number of ways to climb the next three stairs) + (First 2 stairs + number of ways to climb the next two stairs) +(First 3 stairs + number of ways to climb the next one stair) = 4+2+1 = 7

Take a look at the sketch below to get an idea

If there are five stairs, number of ways = ( First 1 stair + number of ways to climb the next four stairs) + (First 2 stairs + number of ways to climb the next three stairs) +(First 3 stairs + number of ways to climb the next two stairs) = 7+4+2 = 13

So , we may notice that if N_{k} denotes the number of ways to climb “k” stairs , then for k ≥ 4 ,there are 3 “moves” one can do for your ﬁrst step: you can climb 1,2, or 3 stairs. If you climb 1 stair then there are N_{k−1}ways to ﬁnish; if you climb 2 stairs there are N_{k-2} ways to ﬁnish; and if you climb 3 stairs there are N_{k−3}ways to ﬁnish.

So , we may generalize that:

N_{k} = N_{k-1} + N_{k-2} +N_{k-3}

So, it’s easy to understand that for k<4, we have N_{1}= 1, N_{2}=2 and N_{3}=4

Calculating for N≥4,

N4 = N3+N2+N1 = 4+2+1 = 7

N5 = N4+N3+N2 = 7+4+2 = 13

N6 = N5+N4+N3 = 13+7+4 = 24

N7 = N6+N5+N4 = 24+13+7 = 44

N8 = N7+N6+N5 = 44+24+13 = 81

N9 = N8+N7+N6 = 81+44+24 = 149

N10 = N9+N8+N7 = 149+81+44 = 274

**The Answer:****There are 274 ways to climb 10 stairs, given the conditions of the problem.**

The Reader’s challenge :**We have a 10 step staircase. One can climb up 1 or 2 stairs at a time. How many ways are there to climb up the stairs ?**

You will find a very popular series over here . Can you name the series ? Please respond with your solution in the comment section.

TokaiThe way you explained is great.

Reader’s challenge answer:Number of ways to climb 10 stairs is 89.

The series we get here is 1,2,3,5,8,13,21,34,55,89…i.e. fibonacci series.

DecodeMonkRight answer..Can anybody explain the answer elaborately?