[Guest]

A person who can climb one, two or three steps in a single leap is trying to climb a stairway. The stairway consists of 25 steps. In how many different ways can he climb this stairway?

If the question was asked for a stairway consisting of 4 steps, the answer would be 7 (1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2, 1-3, 3-1).

[Guest]

Total 65 ways.

Edited December 22, 2009 by Sarfaraz

[Guest]

A person who can climb one, two or three steps in a single leap is trying to climb a stairway. The stairway consists of 25 steps. In how many different ways can he climb this stairway?

If the question was asked for a stairway consisting of 4 steps, the answer would be 7 (1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2, 1-3, 3-1).

there are 25 steps.

* * * * * * * * * * * * * * * * * * * * * * * * *

there are 24 gaps between each step. each gap represents where each leap may end. the 25th gap will surely be the last leap.

the maximum number of leaps the person may take is 25. this corresponds to using all the 24 gaps (the 25th gap is at the very end).

the minimum number of leaps is 9, corresponding to 8 gaps (the 9th gap is at the very end).

therefore, the number of ways the person may leap through the stairs can be calculated by:

=sum(24CX), x is from 8 to 24.

=16,241,061

it seems very large so i'm not quite sure if i did it right.

if i use the same method for a 4-step stairs... there are 3 gaps. max leaps=4=3 gaps. min leaps=2=1 gap.

=sum(3CX), x is from 1 to 3 = 7

it shows the right answer. so maybe it's right

[Guest]

Initial thought is that the first answer is too small, and the second is too big.

So let's say that S(n) is the number of such ways for a staircase of n steps. We have, just by counting:

S(1) = 1

S(2) = 2 (1-1, or 2)

S(3) = 4 (1-1-1, 1-2, 2-1, or 3)

S(4) = 7 (from the example)

So let's consider the last step taken on the general case of n steps. It's either a 1, 2, or 3-step leap.

If it's a 1-step leap, there are S(n-1) ways to get to step n-1 before taking that last step. For a 2-step leap, there are S(n-2) ways to get to step n-2 before taking the last two steps in a single leap. For a 3-step leap, similarly, there are S(n-3) ways to get to n-3 before taking the last leap to the top. These are three disjoint cases (i.e. only one of them can occur), so we can just add the ways up and get the answer.

I claim that S(1) = 1, S(2) = 2, S(3) = 4, and in general, S(n) = S(n-1) + S(n-2) + S(n-3) for n>3, sort of like a super-Fibonacci series. I think the closed formula is a bit more complex than I'd like to calculate, so I'll just brute force S(25) and see what happens...

Microsoft Excel tells me that the answer is 2555757.

[Guest]

Similarly, there are 12 ways to climb 5 steps, 1,2, or 3 at a time. There are 5 of these 5 step possibilities in 25 steps. Therefore there should be a total of 12^5 or 248,832 total possibilities (maybe adding a handful more for additional inter-5 step block possibilities)

[Guest]

There are 13 ways to climb 5 steps, 1, 2, or 3 at a time so 13^5 = 371,293 ways to climb 25 steps (although I also agree with Chuck's assumption--so not sure which is right)

Similarly, there are 12 ways to climb 5 steps, 1,2, or 3 at a time. There are 5 of these 5 step possibilities in 25 steps. Therefore there should be a total of 12^5 or 248,832 total possibilities (maybe adding a handful more for additional inter-5 step block possibilities)

[superprismatic]

Initial thought is that the first answer is too small, and the second is too big.

So let's say that S(n) is the number of such ways for a staircase of n steps. We have, just by counting:

S(1) = 1

S(2) = 2 (1-1, or 2)

S(3) = 4 (1-1-1, 1-2, 2-1, or 3)

S(4) = 7 (from the example)

So let's consider the last step taken on the general case of n steps. It's either a 1, 2, or 3-step leap.

If it's a 1-step leap, there are S(n-1) ways to get to step n-1 before taking that last step. For a 2-step leap, there are S(n-2) ways to get to step n-2 before taking the last two steps in a single leap. For a 3-step leap, similarly, there are S(n-3) ways to get to n-3 before taking the last leap to the top. These are three disjoint cases (i.e. only one of them can occur), so we can just add the ways up and get the answer.

I claim that S(1) = 1, S(2) = 2, S(3) = 4, and in general, S(n) = S(n-1) + S(n-2) + S(n-3) for n>3, sort of like a super-Fibonacci series. I think the closed formula is a bit more complex than I'd like to calculate, so I'll just brute force S(25) and see what happens...

Microsoft Excel tells me that the answer is 2555757.

Very nice, concise explanation!

[Guest]

Preliminary: There is only 1 way to stride up 1 step: (1)

There are 2 ways to cover 2 steps: (1-1, 2)

There are 4 ways to move up 3 steps: (1-1-1, 1-2, 2-1, 3 )

--------------------------------------------------------

Now, consider a staircase with 4 steps.

I'm going to approach this by looking at what happens after you take one of the three choices you will always have for your first move:

You can move one step, two steps or three steps.

If your first move is one step, you will be (4-1) = 3 steps from the top and we know from the preliminary that there are 4 ways to cover 3 steps.

If your first move is two steps, you will be (4-2) = 2 steps from the top and we know from the preliminary that there are 2 ways to cover 2 steps.

If your first move is 3 steps, you will be (4-3) =1 step from the top and there is 1 way to cover that.

So, by adding the 4 ways, 2 ways and 1 way above, I can see there are 7 ways to cover 4 steps.

# of steps -----# of ways

1 -----------------1

2 -----------------2

3 -----------------4

4 -----------------7

If the staircase has 5 steps, I consider a first move of 1,2 or 3 steps, leaving 4,3 or 2 steps remaining.

I can see from the above table that I will add the # of ways in the last 3 rows (2 + 4 + 7) to get 13 ways .

In general, (for staircase of 4 steps or more), I can always add the last 3 entries in the second column of the table to get the next entry.

# of steps -----# of ways

1 -----------------1

2 -----------------2

3 -----------------4

4 -----------------7

5 ----------------13

6 ----------------24

. . .

25 ------------2,555,757

Looks like a vote for Chuck's

[Guest]

...So let's say that S(n) is the number of such ways for a staircase of n steps. We have, just by counting:

S(1) = 1

S(2) = 2 (1-1, or 2)

S(3) = 4 (1-1-1, 1-2, 2-1, or 3)

S(4) = 7 (from the example)

I claim that S(1) = 1, S(2) = 2, S(3) = 4, and in general, S(n) = S(n-1) + S(n-2) + S(n-3) for n>3, sort of like a super-Fibonacci series...

Nice! And as a nice bonus you have found an alternative definition of the Fibonacci numbers:

Let S(i,n) be the number of ways to climb n stairs with foot-steps that cover an interval of at most i steps.

Set S(i,0) = 1 and S(i,n) = 0 for negative integers n, and

S(i,n)=S(i,n-1)+S(i,n-2)+...+S(i,n-i) for n=1,2,3,...

then, we get the Fibonacci sequence for i=2, and Chuck's recursive formula for S(3,n) can now apply for all n>0.

We could even generalize further and say that for each step s in the staircase, there is a set A(s) of allowed "next-steps" which are where we are allowed to step next after having stepped on s. We could visualize such a set up as a bunch of arrows that point from s to other steps. Then, the question becomes how many paths can I take, following the arrows, to get from the bottom of the stairs to the top?

With this definition, the nth Fibonacci number becomes the answer the following question: on a sequence of integers {1,2,...,n+1} (called steps), draw arrows from each step s to each of the following two steps s+1 and s+2, and then ask

"how many paths can I take, following these arrows, to get from the bottom of the stairs (s=1) to the top (s=n+1)?"

Very cool!

[Guest]

Nice! And as a nice bonus you have found an alternative definition of the Fibonacci numbers:

Let S(i,n) be the number of ways to climb n stairs with foot-steps that cover an interval of at most i steps.

Set S(i,0) = 1 and S(i,n) = 0 for negative integers n, and

S(i,n)=S(i,n-1)+S(i,n-2)+...+S(i,n-i) for n=1,2,3,...

then, we get the Fibonacci sequence for i=2, and Chuck's recursive formula for S(3,n) can now apply for all n>0.

We could even generalize further and say that for each step s in the staircase, there is a set A(s) of allowed "next-steps" which are where we are allowed to step next after having stepped on s. We could visualize such a set up as a bunch of arrows that point from s to other steps. Then, the question becomes how many paths can I take, following the arrows, to get from the bottom of the stairs to the top?

With this definition, the nth Fibonacci number becomes the answer the following question: on a sequence of integers {1,2,...,n+1} (called steps), draw arrows from each step s to each of the following two steps s+1 and s+2, and then ask

"how many paths can I take, following these arrows, to get from the bottom of the stairs (s=1) to the top (s=n+1)?"

Very cool!

[Guest]

1,1,1,................1=1

2,1,1,1,1,=24

2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1...=22+21*22=>22*22=484

2,2,2,1,1,1,1,1,1,1=20+20+=>20*20=400

2,2,2,2,1,1,1,=18*18=324

2,2,2,2,2,1,1,1,1,=16*16=256

2,2,2,2,,2(6)....1,1,1,1=14*14196

2,2,2,.......(7),1,1,1,1,=12*12144

2,2,2,2,2,2(8)..,1,1,1,=10*10==100

2,2,2,2,,2(9),1,1,1,1=8*8=64

2,2,2,2,2,(10),1,1,1=6*6=36

2,2,2,2,2,(11),1,1,1=4*4=16

2,2,2,2,22,(12),1=2*2=4

3,1,1=23

3,3,1,1,1,1,=20*20=400

3,3,3,1,1,1,=17*17=289

3,3,3,3,1,1,1=14*14=196

3,3,3,3,3(5),1,1,1,1=11*11=121

3,3,3,3,3(6),1,1,1=8*8=64

3,3,3,3,(7),1,1,1,1=5*5=25

3,3,3,3,3(8),1=2*2=4

total number of ways are 2771

[Guest]

Total 65 ways.

It looks like you were counting the number of integer partitions of 25 where each part is at most 3. In the problem posed, the order of the parts matters,

e.g. 1,1,2 is not the same as 1,2,1

and you did not take this into account. However, the problem you solved is an interesting problem itself. I was wondering what you were counting to get a such a low number!

To follow this up, can anyone find a formula for the number of ways to write n as a sum of 1's 2's and 3's, where the order of the terms doesn't matter?

e.g.

1 has 1 way: 1

2 has 2 ways: 2=1+1

3 has 3 ways: 3=2+1=1+1+1

4 has 4 ways: 3+1=2+2=2+1+1=1+1+1+1

5 has 5 ways: 3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1

6 has 7 ways: 3+3=3+2+1=2+2+2=3+1+1+1=2+2+1+1=2+1+1+1+1=1+1+1+1+1+1

...

25 has 65 ways...

40 has 154 ways...

I computed this out a little further and it seems that the sequence grows only slightly faster than linearly.

(also, the problem for writing n as a sum of 1's and 2's is very easy...but this does not mean that the problem I have posed is-- it might be very difficult)

[Guest]

...the problem for writing n as a sum of 1's and 2's is very easy...but this does not mean that the problem I have posed is-- it might be very difficult

I thought about this some more, and I've pretty pretty much found the solution, just can't prove it yet. The sequence definitely grows at a quadratic rate. If you try to solve it, it might be advantageous to consider first the case where n=6k.

The number of ways to write 6k as a sum of 1's, 2's and 3's where order doesn't matter is

3k²+3k+1

which happens to be equal to

(k+2)choose2 + 4*((k+1)choose2) + (k)choose2

[Guest]

Approximately

f(n) = (0.19079003884 + 0.01870058311*I)*(-0.41964337761 - 0.60629072921*I)^n + (0.19079003884 - 0.018700583112*I)*(-0.41964337761 + 0.60629072921*I)^n + 0.61841992232*1.83928675521^n

where I is the imaginary unit.

Where f(25) is the final answer to the problem.

The exact form is very, very ugly:

I told you so:

f(n) = (Sqrt[3]*(1/3 - ((1 + I*Sqrt[3])*(19 - 3*Sqrt[33])^(1/3))/6 - ((1 - I*Sqrt[3])*(19 + 3*Sqrt[33])^(1/3))/6)^n*

(42 + (-5 - (5*I)*Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) + I*(I + Sqrt[3])*(19 - 3*Sqrt[33])^(2/3) + (5*I)*(I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3) +

(-1 - I*Sqrt[3])*(19 + 3*Sqrt[33])^(2/3)))/(((19 - 3*Sqrt[33])^(1/3) - (19 + 3*Sqrt[33])^(1/3))*

(-24*I - (-3*I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) + 2*Sqrt[3]*(19 - 3*Sqrt[33])^(2/3) + (3*I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3) -

2*Sqrt[3]*(19 + 3*Sqrt[33])^(2/3))) + (21 + 5*(19 - 3*Sqrt[33])^(1/3) + (19 - 3*Sqrt[33])^(2/3) + 5*(19 + 3*Sqrt[33])^(1/3) +

(19 + 3*Sqrt[33])^(2/3))/((3/(1 + (19 - 3*Sqrt[33])^(1/3) + (19 + 3*Sqrt[33])^(1/3)))^n*

(42 + (19 + 3*Sqrt[33])^(2/3) + 2*(19 - 3*Sqrt[33])^(1/3)*(19 + 3*Sqrt[33])^(2/3) +

(19 - 3*Sqrt[33])^(2/3)*(1 + 2*(19 + 3*Sqrt[33])^(1/3)))) +

(((2 + I*(I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) + (-1 - I*Sqrt[3])*(19 + 3*Sqrt[33])^(1/3))/6)^n*

(-42*I + 5*(I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) - (-I + Sqrt[3])*(19 - 3*Sqrt[33])^(2/3) - 5*(-I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3) +

(I + Sqrt[3])*(19 + 3*Sqrt[33])^(2/3)))/(-84*I + (I + Sqrt[3])*(19 + 3*Sqrt[33])^(2/3) -

2*(-I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3)*(19 + 3*Sqrt[33])^(2/3) + (19 - 3*Sqrt[33])^(2/3)*

(I - Sqrt[3] + 2*(I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3)))

Edited December 23, 2009 by mmiguel1

[Guest]

Good puzzle flrd. Good presentation, it looks easy, but is actually a bit tricky and interesting.

[Guest]

Approximately

f(n) = (0.19079003884 + 0.01870058311*I)*(-0.41964337761 - 0.60629072921*I)^n + (0.19079003884 - 0.018700583112*I)*(-0.41964337761 + 0.60629072921*I)^n + 0.61841992232*1.83928675521^n

where I is the imaginary unit.

Where f(25) is the final answer to the problem.

The exact form is very, very ugly:

I told you so:

f(n) = (Sqrt[3]*(1/3 - ((1 + I*Sqrt[3])*(19 - 3*Sqrt[33])^(1/3))/6 - ((1 - I*Sqrt[3])*(19 + 3*Sqrt[33])^(1/3))/6)^n*

(42 + (-5 - (5*I)*Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) + I*(I + Sqrt[3])*(19 - 3*Sqrt[33])^(2/3) + (5*I)*(I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3) +

(-1 - I*Sqrt[3])*(19 + 3*Sqrt[33])^(2/3)))/(((19 - 3*Sqrt[33])^(1/3) - (19 + 3*Sqrt[33])^(1/3))*

(-24*I - (-3*I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) + 2*Sqrt[3]*(19 - 3*Sqrt[33])^(2/3) + (3*I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3) -

2*Sqrt[3]*(19 + 3*Sqrt[33])^(2/3))) + (21 + 5*(19 - 3*Sqrt[33])^(1/3) + (19 - 3*Sqrt[33])^(2/3) + 5*(19 + 3*Sqrt[33])^(1/3) +

(19 + 3*Sqrt[33])^(2/3))/((3/(1 + (19 - 3*Sqrt[33])^(1/3) + (19 + 3*Sqrt[33])^(1/3)))^n*

(42 + (19 + 3*Sqrt[33])^(2/3) + 2*(19 - 3*Sqrt[33])^(1/3)*(19 + 3*Sqrt[33])^(2/3) +

(19 - 3*Sqrt[33])^(2/3)*(1 + 2*(19 + 3*Sqrt[33])^(1/3)))) +

(((2 + I*(I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) + (-1 - I*Sqrt[3])*(19 + 3*Sqrt[33])^(1/3))/6)^n*

(-42*I + 5*(I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3) - (-I + Sqrt[3])*(19 - 3*Sqrt[33])^(2/3) - 5*(-I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3) +

(I + Sqrt[3])*(19 + 3*Sqrt[33])^(2/3)))/(-84*I + (I + Sqrt[3])*(19 + 3*Sqrt[33])^(2/3) -

2*(-I + Sqrt[3])*(19 - 3*Sqrt[33])^(1/3)*(19 + 3*Sqrt[33])^(2/3) + (19 - 3*Sqrt[33])^(2/3)*

(I - Sqrt[3] + 2*(I + Sqrt[3])*(19 + 3*Sqrt[33])^(1/3)))

mmiguel1, How did you get to the exact form?

I got what will probably be the same answer...probably...

I got 2555757 using an expanded Fibonacci sequence in which each term is the sum of the three previous terms. I recently spent some time studying the fibonacci numbers and discovered that when each term is the sum of the previous x terms, (nth term)/(n-1th term) always approaches a constant. let a=number of terms added to get next term. that constant will always be the solution to x^a-x^(a-1)-x^(a-2)...-x-1=0

The exact value that you posted, mmiguel1, appears to have numerous iterations of the ratio of successive terms when each term is equal to the sum of the previous 3 terms... aka, the tribonacci constant.

If you could take four steps at once, one could use the fibonacci sequence in which each term is the sum of the previous 4 terms...