Author |
Topic: Walking up stairs (Read 2190 times) |
|
Earendil
Newbie
 
Gender: 
Posts: 46
|
 |
Walking up stairs
« on: Aug 18th, 2007, 11:22pm » |
 Quote  Modify
|
What is the number of ways you can walk up a stair with n steps only going up 1, 2 or 3 steps at a time?
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Walking up stairs
« Reply #1 on: Aug 19th, 2007, 12:11am » |
Quote Modify
|
::Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4::
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Walking up stairs
« Reply #2 on: Aug 19th, 2007, 4:40am » |
Quote Modify
|
on Aug 19th, 2007, 12:11am, TenaliRaman wrote:::Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4::
-- AI |
|
... which is called Tribonacci Number.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Walking up stairs
« Reply #4 on: Sep 6th, 2007, 4:48pm » |
Quote Modify
|
No, it has absolutely nothing to do with the subfactorial.
|
|
IP Logged |
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: Walking up stairs
« Reply #5 on: Sep 6th, 2007, 8:04pm » |
Quote Modify
|
I'm 99.9999999999...% sure it does.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Walking up stairs
« Reply #6 on: Sep 6th, 2007, 11:26pm » |
Quote Modify
|
on Sep 6th, 2007, 8:04pm, srn347 wrote:| I'm 99.9999999999...% sure it does. |
|
Then back up your blinkeredness with some hard facts! Exactly how are they similar?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JiNbOtAk
Uberpuzzler
Hana Hana No Mi
Gender:
Posts: 1187
|
|
Re: Walking up stairs
« Reply #7 on: Sep 7th, 2007, 1:54am » |
Quote Modify
|
on Sep 6th, 2007, 11:26pm, ThudanBlunder wrote:| Then back up your blinkeredness with some hard facts! Exactly how are they similar? |
|
This would prove to be interesting. ( And not only because T&B is getting riled up ) 
on Sep 6th, 2007, 4:48pm, Obob wrote:| No, it has absolutely nothing to do with the subfactorial. |
|
Hee hee..
|
| « Last Edit: Sep 7th, 2007, 1:55am by JiNbOtAk » |
IP Logged |
Quis custodiet ipsos custodes?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Walking up stairs
« Reply #8 on: Sep 7th, 2007, 2:25am » |
Quote Modify
|
on Sep 6th, 2007, 4:39pm, srn347 wrote:
If there is one step, you can take the stairs in 1 way (1)
If there are two steps, you can take it in 2 ways (1,1 or 2)
If there are three steps, you can take it in 4 ways (1,1,1 or 1,2 or 2,1 or 3)
subfactorials go
!1 = 0
!2 = 1
!3 = 2
!4 = 9
the observed sequence 1,2,4 does not fit, not even with a shift (i.e. if we take !(n+1) for n steps, or even !(n+k) for some fixed k).
Based on the first three observations it would have made more sense to suggest it goes like powers of 2 than subfactorials.
|
| « Last Edit: Sep 7th, 2007, 2:27am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Walking up stairs
« Reply #9 on: Sep 7th, 2007, 6:43am » |
Quote Modify
|
I dont know whether subfactorial has anything to do with this problem, but it certainly has something to do with derangement"s".
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: Walking up stairs
« Reply #10 on: Sep 7th, 2007, 6:52am » |
Quote Modify
|
on Sep 7th, 2007, 2:25am, towr wrote:
Based on the first three observations it would have made more sense to suggest it goes like powers of 2 than subfactorials. |
|
Like Polynacci...? 
|
| « Last Edit: Sep 7th, 2007, 6:52am by mikedagr8 » |
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
raj1
Newbie
Posts: 15
|
|
Re: Walking up stairs
« Reply #11 on: Feb 4th, 2008, 9:33pm » |
Quote Modify
|
So is the solution posted
Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4
correct?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Walking up stairs
« Reply #12 on: Feb 5th, 2008, 1:16am » |
Quote Modify
|
on Feb 4th, 2008, 9:33pm, raj1 wrote:So is the solution posted
Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4
correct? |
|
Yes.
It is easy to check the first three cases must be correct; and then in general, you can get to the Nth step from 1, 2 or 3 steps back.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Walking up stairs
« Reply #13 on: Feb 5th, 2008, 5:59pm » |
Quote Modify
|
You can express it as
F(n) = Ar1n + Br2n + Cr3n,
Where r1, r2, r3 are the roots of the equation r3 - r2 - r - 1 = 0, and the coefficients A, B, C are chosen to make the first three values = 1, 2, 4 respectively. Unfortunately, the expressions for the 3 r's are not very nice, so you are generally better off just calculating values recursively.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
temporary
Full Member
Posts: 255
|
|
Re: Walking up stairs
« Reply #14 on: Feb 5th, 2008, 6:01pm » |
Quote Modify
|
on Feb 4th, 2008, 9:33pm, raj1 wrote:So is the solution posted
Solution to F(n) = F(n-1) + F(n-2) + F(n-3) with F(1) = 1, F(2) = 2, F(3) = 4
correct? |
|
Srn347 was not completely correct, but he was close. n-1, n-2, and n-3 would make it just like factorial if it didn't end right there, but instead ended at 1.
|
|
IP Logged |
My goal is to find what my goal is, once I find what my goal is, my goal will be complete.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Walking up stairs
« Reply #15 on: Feb 5th, 2008, 6:11pm » |
Quote Modify
|
No. Factorials are products. This is a sum.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
temporary
Full Member
Posts: 255
|
|
Re: Walking up stairs
« Reply #16 on: Feb 14th, 2008, 8:39pm » |
Quote Modify
|
Oh. So he was close to being close.
|
|
IP Logged |
My goal is to find what my goal is, once I find what my goal is, my goal will be complete.
|
|
|
JiNbOtAk
Uberpuzzler
Hana Hana No Mi
Gender:
Posts: 1187
|
|
Re: Walking up stairs
« Reply #17 on: Feb 15th, 2008, 3:57am » |
Quote Modify
|
on Feb 14th, 2008, 8:39pm, temporary wrote:| Oh. So he was close to being close. |
|
Nope, he was not right, and he was not close. He was not even wrong.
|
|
IP Logged |
Quis custodiet ipsos custodes?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print