Problem solving question

Thanks but I've given up!

(edited 9 years ago)

Here's a problem-

I have 13 steps I need to climb
I can climb one step at a time, two steps at a time or three steps at a time
E.g. I can climb 3 then 3 then 3 then 3 then 1
How many different ways can I climb the steps?

Start with a smaller number of steps, increase the number, look for a pattern

Reply 2

Yeah dude

Original post by Hunkybm

I have done, cannot seem to see a pattern :frown:

Count to ten, breath in and be the stairs

Posted from TSR Mobile

Reply 3

rixeh

Think about how many ways you can make 13 by adding 1's, 2's and 3's and then for each combination find how many different way you can sort the numbers.

Reply 4

Hunkybm

Original post by Yeah dude

Count to ten, breath in and be the stairs

Posted from TSR Mobile

Yeah thanks for that....

Reply 5

TenOfThem

Original post by Hunkybm

I have done, cannot seem to see a pattern :frown:

no, me neither

Reply 6

DFranklin

Hunkybm

TenOfThem

Let a(n) be the number of ways of going up n steps. (So you are looking for a(13)).

Clearly a(1) = 1.
a(2) = 1 (go up two steps) + a(1) (go up one step and then use the answer for going up the remaining 1 step) = 1 + 1 = 2.
a(3) = 1 (go up 3 steps) + a(2) (go up one step and then use the answer for going up the remaining 2 steps) + a(1) (go up two steps and then ...) = 1 + 2 + 1 = 4
a(4) = a(3) (go up one step and then use the 3 steps answer) + a(2) (...) + a(1)

Carry on and the pattern should be obvious.

To actually find a(13), you could solve the 3rd order recurrence relationship and use the initial values for a(1), a(2) and a(3). But in practice it's going to be easier to just use the recurrent relationship directly to find a(4) then a(5), ... up to a(13). (In the same way that to find the 13th fibonnacci number it's easier to just go 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 than to solve the recurrence relationship and use the resulting messy formula).

Reply 7

DFranklin

Original post by Hunkybm

Thanks for the help but I just can't seem to get it, clearly I'm not cut out for a maths degree!!

<Reddit Response>

Well not with that attitude you're not!

</Reddit Response>

And to be honest, the Reddit response is pretty close to the mark here. Spending your time saying "I don't get it" is not going to get you very far.

What is the first line in my previous post that you don't understand?

[You may also want to google Fibonacci and either stairs or steps. This will give you some solutions / explanations for the simpler case where you can only go 1 or 2 steps at a time. [You will see some solutions using binomials - ignore these, as they don't generalise to the problem you have here. Instead, look at the solutions involving recurrence relations]].

Reply 8

DFranklin

Original post by Hunkybm

You're right.
Am I right in saying a(5)=a(1)+a(2)+a(3)+a(4)-1

I think this is "true", but I don't think your reasoning is correct.

And a(6)=a(5)+a(1)+a(2)+a(3)+a(4)-2?

And this definitely isn't true.

Let's look at it the other way.

Suppose you're on step n (with n > 3) and you want to get to the bottom (step 0).

Suppose you first go 1 step, leaving n-1. How many ways are there of getting to the bottom from here?

Spoiler

.
Or you could go 2 steps, leaving n-2. How many ways are there of getting to the bottom from here?
Or you could go 3 steps, leaving n-3. How many ways are there of getting to the bottom from here?

So the total number of ways of getting to the bottom is?