1. Pathways
  2. Freedom and Constraints
  3. Climbing the Stairs
  4. 13 Steps

13 Steps

Stairs against an orange background
 
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?

 

 

I wonder if there's a different way to climb 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 a way to make this problem more manageable?

Perhaps you could investigate some smaller staircases first...

Is there a quick way to work out the number of different ways to go up any size staircase, one or two steps at a time?


How do you know your method will always work?

I wonder how big a staircase I would need in order to have more than a million different ways of climbing the stairs...

 

Once you've explored this, you might like to take a look at Giant Steps.

 

 

Comments

Submitted by sergio estan on Wed, 02/10/2016 - 21:19

What I did was to try this problem in a more manageable way, so I tried to do it up to five steps and see what the answers were.
I quickly found out the term to term rule was multiplying by 2. So it must be 2 to the power of n, but I worked out the numbers were double the real answer. So I just converted it into 2 to the power of n-1.
Lovely problem.

Submitted by cfg21 on Fri, 02/19/2016 - 11:50

Sergio, can you show us what answers you got for 1 to 5 steps?
I think I've got different answers to you.

Submitted by Liam on Tue, 05/17/2016 - 13:58

the rule definitely is not multiplying by two:

1 step = 1 way: 1
2 steps = 2 ways: 1 1, 2
3 steps = 3 ways: 1 1 1, 1 2, 2 1
4 steps = 5 ways: 1 1 1 1, 1 1 2, 1 2 1, 2 1 1, 2 2
and so on

This is how to continue the pattern:

To find all of the 'sequences' (for use of a better word) that 5 steps would have, put 1's on the end of the 4 steps list, and a 2 on the end of the 3 steps list (because they are literally 1 and 2 steps away from 5 respectively). It's a decent proof of why it is the previous two answers added together.

Extensions into 'what if we could take three at a time?' works too, because it is the previous three results added together instead of two:
3's added to the end of the 2 steps list, 2's to the 3 steps list and 1's added to the 4 step list will give you all of the 'sequences' for 5 steps

You can really go quite in depth with it if you want to.

Submitted by Valerie on Tue, 03/01/2016 - 20:00

So I saw Sergio's approach and decided to simplify even further. I considered 1 step and got 1 way. ways
2 steps, 2 ways.
3 steps, 3 ways.
4 steps, 5 ways.
5 steps, 8 ways.
I am noticing that the differences in "ways" appears to be Fibonacci. I haven't tried 6 steps but I will. Am I on the correct track?

Submitted by valerie on Tue, 03/01/2016 - 20:04

Just posted a beginning solution. I did predict that 6 steps would have 13 ways (based on pattern in differences) and verified by writing them out. I am not sure if I included this in my previous comment.

ajk44's picture

Submitted by ajk44 on Fri, 03/04/2016 - 14:44

Good stuff Valerie, you've spotted a pattern that seems to work... I wonder if you can find an explanation why you get the Fibonacci sequence?

Submitted by Jan S. Dybicz on Mon, 04/11/2016 - 05:47

Assume that we go up the thirteen steps only by 1 step, and that we do not take steps two at a time.
This is equivalent to asking how many ways are there to order a sequence of 13 ones.
There are only 13_C_0, or 13!/13! ways, or only 1 way to go up the steps.

Now, assume that we go up the thirteen steps, and this time we only have one step that is two at a time.
This is equivalent to asking how many ways are there to order a sequence of 11 ones and 1 two.
There are 12_C_1, 12!/(11!*1!), or 12 ways to get up the steps.

We continue with going up the steps, two of the steps being two at a time.
This is equivalent to asking how many ways are there to order a sequence of 9 ones and 2 twos.
There are 11_C_2, 11!/(9!*2!), or 36 ways to get up the steps.

And so on, until we reach the final case, where six of the steps are two at a time, and only one step is one at a time.
The total ways possible is just the sum of all the ways in each case.

ajk44's picture

Submitted by ajk44 on Thu, 04/14/2016 - 15:22

That's one way to solve it, but there is another very elegant way that's hinted at in some of the comments above!

Submitted by Thomas Vogler on Sun, 05/22/2016 - 05:33

Thinking about how this problem works when we allow 3 or more steps at a time...

We can use a recursion formula: $$f(n) = \sum_{k=0}^{n-1}f(k) \qquad \text{where} \ f(0)=1$$ Solving this recursion, you get $f(n) = 2^{n-1}$.

 

Submitted by cfg21 on Thu, 06/02/2016 - 16:11

That's a very interesting way of looking at the problem. You may find it useful in solving Giant Steps, where we investigate larger steps at a time.

To solve this problem, how could you adjust your recursion formula to exclude steps larger than 2?

Submitted by Joanne on Sun, 05/22/2016 - 12:59

Help - I'm missing one of the 8 steps

11111111
1111112, 1111121, 1111211, 1112111, 1121111, 1211111, 2111111
111122, 111221, 112211, 122111, 221111, 212111, 211211, 211121, 211112, 121211, 121121, 121112, 112121, 112112, 111212
11222, 12221, 22211, 22121, 22112, 12212, 12122, 21122, 21221
2222

Submitted by cfg21 on Fri, 05/27/2016 - 12:50

I think you are missing one of the combinations that has two 1s and three 2s.

Submitted by Annabel on Fri, 05/27/2016 - 09:37

I worked through this problem by first seeing how many ways you could go up 2 steps which = 2 ways, then
3 steps = 3,
4 steps = 5,
5 steps = 8,
6 steps = 18

After I had worked out this I realised ...

it's the Fibonacci sequence and so the 13 number after 1 equals 377 days

Submitted by Alex on Tue, 06/07/2016 - 05:54

This is how I did it:
First step - 1 (way to get there)
Second step - 2 (1+1)
Third step - 3 (2+1)
Fourth - 5 (3+2)

Can you see the pattern?

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

I hope this is helpful.

Submitted by Alex on Tue, 06/07/2016 - 05:55

This is how I did it:
First step - 1 way to get there
Second step - 2
Third step - 3
Fourth - 5
Can you see the pattern?


First step - 1
Second step - 2 (1+1)
Third step - 3 (2+1)
Fourth - 5 (3+2)

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...


I hope this is helpful.

Submitted by Yang Jie & Marc on Wed, 06/08/2016 - 10:19

The overall formula from steps ($S$) to amount of combinations ($C$) is:

$$C = \frac{\phi^{S+1}-(-\phi)^{-(S+1)}}{\sqrt{5}}$$

Where $\phi = \frac{1+\sqrt{5}}{2}$

This is similar to the Fibonacci formula, except for the '$S+1$' part.