Climbing the stairs
In how many ways can I get upstairs?
Problem
This resource is part of "Freedom and Constraints"
Image
When I go up my stairs in a hurry, I take some steps two-at-a-time.
This morning, I climbed my thirteen steps in this pattern: 1, 2, 1, 2, 1, 1, 2, 1, 2.
Yesterday the pattern was 1, 1, 1, 1, 1, 1, 2, 2, 1, 2.
How many days do you think I can go before I have to repeat a pattern?
Charlie estimated a lower bound:
I wonder if there's a different pattern of climbing the stairs for each day of the year.
There are lots of possibilities. It's going to be really hard to count them all without missing any, and without accidentally counting any twice.
Sometimes mathematicians like to tackle a big task by starting with a more manageable one, to get some insight into the bigger problem...
Can you think of some more manageable problems you could work on, to help you to get started?
Take a look at the hidden image if you would like a hint:
What other interesting mathematical questions can you think of to explore next?
We have thought of some possibilities:
Yesterday the pattern was 1, 1, 1, 1, 1, 1, 2, 2, 1, 2.
How many days do you think I can go before I have to repeat a pattern?
Charlie estimated a lower bound:
"Even if I only do a 2-step once, I can choose to take that step from any one of 12 places on the staircase. And I could have two, or three, or four 2-steps... so there will be lots more possibilities. It's going to be at least 50."
I wonder if there's a different pattern of climbing the stairs for each day of the year.
There are lots of possibilities. It's going to be really hard to count them all without missing any, and without accidentally counting any twice.
Sometimes mathematicians like to tackle a big task by starting with a more manageable one, to get some insight into the bigger problem...
Can you think of some more manageable problems you could work on, to help you to get started?
Take a look at the hidden image if you would like a hint:
Image
What other interesting mathematical questions can you think of to explore next?
We have thought of some possibilities:
How can you be sure you've included every possibility?
Is there a quick way to work out the number of different ways to go up staircases with many steps?
How can you be sure that your method will work for all staircases, not just the ones you've tried?
How many steps would I need on my staircase if I wanted to have more than a thousand ways of going upstairs?
What if I could also go down 3 steps at a time? Or 4 steps?
What if I could only go down 2 or 3 steps at a time?
Is there a quick way to work out the number of different ways to go up staircases with many steps?
How can you be sure that your method will work for all staircases, not just the ones you've tried?
How many steps would I need on my staircase if I wanted to have more than a thousand ways of going upstairs?
What if I could also go down 3 steps at a time? Or 4 steps?
What if I could only go down 2 or 3 steps at a time?
We'd love you to share the questions you've come up with. Tell us also how you got started and any conclusions you have arrived at.
Send us your thoughts; we'll be publishing a selection.
Send us your thoughts; we'll be publishing a selection.
Student Solutions
The number of days one can go without repeating the pattern is $377$, and, therefore, it is possible to have a different pattern each day of the year.
Before solving the problem, most students who submitted a solution found it useful to look at smaller cases.
Oliver from Beechwood Park School, England, Elz from Banstead Juniors and Jason from Commit Learning found it useful to write all the solutions for some cases:
There are $8$ ways to climb $5$ steps by taking at most two at the time, namely $11111$, $1112$, $1121$, $1211$, $2111$, $122$, $212$ and $221$, where $1$ represents the action of taking one step and $2$ the one of taking two steps.
Oliver found it interesting to look at the case where one can take at most three steps at a time, and he find almost all the solutions:
$11111$, $1112$, $1121$, $1211$, $2111$, $113$, $131$, $311$, $122$, $121$, $211$
Since $32$ and $23$ are also valid solutions, there are $13$ ways in total of climbing the $5$ stairs.
Hoi and Glory from Harrow International School Hong Kong, asked themselves an additional question: what if we can take up to five steps at a time.
In this case there are $16$ ways, namely $11111$, $1112$, $1121$, $1211$, $2111$, $113$, $131$, $311$, $14$, $41$,$122$, $121$, $211$, $31$, $23$, $5$. The fastest way for me to find all the possibilities was to draw a diagram and to write all the numbers in order. It was also very important to double check it.
Thomas from Hardwick Middle School,England, Michelle, Chihiro, Laura and Ken from Shatin College,Hong Kong, Troll from British School Manila and Liam from Thomas Deacon Academy, UK, all managed to find, by inspecting smaller cases, a correlation between the answer and the Fibonacci's sequence.
To solve this problem I decided to start with a low number of stairs, like $2$. So I took $2$ and worked out how many solutions there were. I continue doing that and I noticed that the numbers of ways for a particular number of stairs was the sum of the numbers of ways to climb the stair for the previous two numbers of stairs. After repeating this process I ended up with these results:
$1$ step $=1$ way,
$2$ steps $=2$ ways,
$3$ steps $= 3$ ways,
$4$ steps $= 5$ ways,
$5$ steps $= 8$ ways,
$6$ steps $=13$ ways
$7$ steps $= 21$ ways
$8$ steps $= 34$ ways
$9$ steps $= 55$ ways
$10$ steps $= 89$ ways
$11$ steps $= 144$ ways
$12$ steps $= 233$ ways
$13$ steps $=377$ ways
which form the Fibonacci's sequence. Therefore the answer is $337$ and we can choose one different way of climbing the $13$ steps for each day of the year.
Harry from Alleyn's School, UK, continued with a generalisation of this problem.
When $1$ or $2$ steps can be taken at a time, a staircase of $5$ stairs can be descended in $8$ different ways. I explored this and found that when I had a staircase with $n$ stairs, I could simply add the possibilities of the staircases with $n-1$ and $n-2$ numbers of stairs; a Fibonacci sequence. I knew I had found all of the combinations as I did it systematically. I worked
out that this happens because the possibilities of the previous two numbers of stairs can be written out, with a $1$ put on the end of all the possibilities of $n-1$ and a $2$ on the end of those of $n-2$.
When I added the possibility of taking $3$ steps in one go, I saw a pattern similar to a Fibonacci sequence, only with adding the previous $3$ numbers rather than two:
$$x_n = x_{n-1} + x_{n-2} + x_{n-3}$$
(where $x_n=$ the number of ways of climbing $n$ stairs). This happens due to the same reason;
a $1$ is put on the end of all $n-1$ possibilities, a $2$ on the end of $n-2$ and a $3$ on the end of $n-3$. I assume that with a $4$-step move, $$x_n=x_{n-1} + x_{n-2}
+ x_{n-3} + x_{n-4}$$, although I have not checked this.
With only $2$ and $3$ step moves allowed, I discovered a sequence I had to dwell on for quite a while: $1,1,1,2,2,3,4,5,7,9,12,16...$ After I had looked at this in many ways, I eventually discovered that when $n$ is the number of stairs in the staircase, the number of possibilities is equal to the sum of the number of possibilities in $n-2$ and $n-3$: one must skip the number
preceding n and then add the previous $2$ numbers. A $2$ is put on the end of the $n-2$ sequences and a $3$ on the end of $n-3$ sequences. $n-1$ is not included as a $1$ cannot be put on the end of anything; only moves of $2$ and $3$ steps are allowed.
Ali from Deira International School, UAE and Hadi from Haileybury Almaty, Kazakhstan, had a totally different approach:
You can take either $0,1,2,3,4,5$ or $6$ double steps each day. Let $s$ be the number of double steps you take. We will find the total ways you can take each number of double steps.
For $0$ double steps there is only $1$ way. This is all single steps. so for $s = 0$ there is $1$ way.
For $1$ double step we consider the double step to be a single object. Now there are $11$ $1$ step objects and $1$ $2$ step object $11\times 1 + 1\times 2 = 13$. This object can be placed in
$$ {12 \choose 1} = 12$$
ways so for $s = 1$ there are 12 ways (since ${n \choose r} = \frac{n!}{(n-r)!r!}$).
For $2$ double steps we again consider the double steps to be a single object and so this time there are $9$ $1$ step object so there are a total of $11$ objects. These two 2 step objects can be placed in $ {11 \choose 2} = 55$ ways.
Following on using the same argument we find there are $ {10 \choose 3} = 120$ ways for 3 double steps.
For 4 double steps: ${9 \choose 4} = 126$ ways.
For 5 double steps: ${8 \choose 5} = 56$ ways.
For 6 double steps: ${7 \choose 6} = 7$ ways.
We add them all up:
$$1+12+55+120+126+56+7 = 377$$
ways so it is possible to have a unique way for each day of the year as an year has atmost 366 days
Well done to you all for sending such a variety of solutions.
Before solving the problem, most students who submitted a solution found it useful to look at smaller cases.
Oliver from Beechwood Park School, England, Elz from Banstead Juniors and Jason from Commit Learning found it useful to write all the solutions for some cases:
There are $8$ ways to climb $5$ steps by taking at most two at the time, namely $11111$, $1112$, $1121$, $1211$, $2111$, $122$, $212$ and $221$, where $1$ represents the action of taking one step and $2$ the one of taking two steps.
Oliver found it interesting to look at the case where one can take at most three steps at a time, and he find almost all the solutions:
$11111$, $1112$, $1121$, $1211$, $2111$, $113$, $131$, $311$, $122$, $121$, $211$
Since $32$ and $23$ are also valid solutions, there are $13$ ways in total of climbing the $5$ stairs.
Hoi and Glory from Harrow International School Hong Kong, asked themselves an additional question: what if we can take up to five steps at a time.
In this case there are $16$ ways, namely $11111$, $1112$, $1121$, $1211$, $2111$, $113$, $131$, $311$, $14$, $41$,$122$, $121$, $211$, $31$, $23$, $5$. The fastest way for me to find all the possibilities was to draw a diagram and to write all the numbers in order. It was also very important to double check it.
Thomas from Hardwick Middle School,England, Michelle, Chihiro, Laura and Ken from Shatin College,Hong Kong, Troll from British School Manila and Liam from Thomas Deacon Academy, UK, all managed to find, by inspecting smaller cases, a correlation between the answer and the Fibonacci's sequence.
To solve this problem I decided to start with a low number of stairs, like $2$. So I took $2$ and worked out how many solutions there were. I continue doing that and I noticed that the numbers of ways for a particular number of stairs was the sum of the numbers of ways to climb the stair for the previous two numbers of stairs. After repeating this process I ended up with these results:
$1$ step $=1$ way,
$2$ steps $=2$ ways,
$3$ steps $= 3$ ways,
$4$ steps $= 5$ ways,
$5$ steps $= 8$ ways,
$6$ steps $=13$ ways
$7$ steps $= 21$ ways
$8$ steps $= 34$ ways
$9$ steps $= 55$ ways
$10$ steps $= 89$ ways
$11$ steps $= 144$ ways
$12$ steps $= 233$ ways
$13$ steps $=377$ ways
which form the Fibonacci's sequence. Therefore the answer is $337$ and we can choose one different way of climbing the $13$ steps for each day of the year.
Harry from Alleyn's School, UK, continued with a generalisation of this problem.
When $1$ or $2$ steps can be taken at a time, a staircase of $5$ stairs can be descended in $8$ different ways. I explored this and found that when I had a staircase with $n$ stairs, I could simply add the possibilities of the staircases with $n-1$ and $n-2$ numbers of stairs; a Fibonacci sequence. I knew I had found all of the combinations as I did it systematically. I worked
out that this happens because the possibilities of the previous two numbers of stairs can be written out, with a $1$ put on the end of all the possibilities of $n-1$ and a $2$ on the end of those of $n-2$.
When I added the possibility of taking $3$ steps in one go, I saw a pattern similar to a Fibonacci sequence, only with adding the previous $3$ numbers rather than two:
$$x_n = x_{n-1} + x_{n-2} + x_{n-3}$$
(where $x_n=$ the number of ways of climbing $n$ stairs). This happens due to the same reason;
a $1$ is put on the end of all $n-1$ possibilities, a $2$ on the end of $n-2$ and a $3$ on the end of $n-3$. I assume that with a $4$-step move, $$x_n=x_{n-1} + x_{n-2}
+ x_{n-3} + x_{n-4}$$, although I have not checked this.
With only $2$ and $3$ step moves allowed, I discovered a sequence I had to dwell on for quite a while: $1,1,1,2,2,3,4,5,7,9,12,16...$ After I had looked at this in many ways, I eventually discovered that when $n$ is the number of stairs in the staircase, the number of possibilities is equal to the sum of the number of possibilities in $n-2$ and $n-3$: one must skip the number
preceding n and then add the previous $2$ numbers. A $2$ is put on the end of the $n-2$ sequences and a $3$ on the end of $n-3$ sequences. $n-1$ is not included as a $1$ cannot be put on the end of anything; only moves of $2$ and $3$ steps are allowed.
Ali from Deira International School, UAE and Hadi from Haileybury Almaty, Kazakhstan, had a totally different approach:
You can take either $0,1,2,3,4,5$ or $6$ double steps each day. Let $s$ be the number of double steps you take. We will find the total ways you can take each number of double steps.
For $0$ double steps there is only $1$ way. This is all single steps. so for $s = 0$ there is $1$ way.
For $1$ double step we consider the double step to be a single object. Now there are $11$ $1$ step objects and $1$ $2$ step object $11\times 1 + 1\times 2 = 13$. This object can be placed in
$$ {12 \choose 1} = 12$$
ways so for $s = 1$ there are 12 ways (since ${n \choose r} = \frac{n!}{(n-r)!r!}$).
For $2$ double steps we again consider the double steps to be a single object and so this time there are $9$ $1$ step object so there are a total of $11$ objects. These two 2 step objects can be placed in $ {11 \choose 2} = 55$ ways.
Following on using the same argument we find there are $ {10 \choose 3} = 120$ ways for 3 double steps.
For 4 double steps: ${9 \choose 4} = 126$ ways.
For 5 double steps: ${8 \choose 5} = 56$ ways.
For 6 double steps: ${7 \choose 6} = 7$ ways.
We add them all up:
$$1+12+55+120+126+56+7 = 377$$
ways so it is possible to have a unique way for each day of the year as an year has atmost 366 days
Well done to you all for sending such a variety of solutions.
Teachers' Resources
An alternative version of this problem, 1 Step 2 Step, is available with full teachers' notes and suggestions for classroom use.