Question 1020312: if a cat can climb 1 or 2 steps at a time. in how many ways can she climb a flight of 10 stairs
Answer by Theo(13342)   (Show Source):
You can put this solution on YOUR website! if we let a = the cat takes 1 step at a time, and we let b = the cat takes 2 steps at a time, then we will get the following possible combinations.
5b + 0a
4b + 2a
3b + 4a
2b + 6a
1b + 8a
0b + 10a
5b means the cat takes 10 stair steps 2 at a time for a total of 5 cat steps.
4b + 2a means the cat takes 8 stair steps 2 at a time and 2 stair steps 1 at a time for a total of 6 cat steps.
order is important because the cat can take 1 stair step at a time and then 2 stair steps at a time, or the cat can take 2 stair steps at a time and then 1 stair step at a time. each of those counts as a different possible way for the cat to climb the stair steps.
5b + 0a can occur in 5! / (5! * 0!) = 1 way.
4b + 2a can occur in 6! / (4! * 2!) = 15 ways.
3b + 4a can occur in 7! / (3! * 4!) = 35 ways.
2b + 6a can occur in 8! / (2! * 6!) = 28 ways.
1b + 8a can occur in 9! / (1! * 8!) = 9 ways
0b + 10a can occur in 10! / (0! * 10!) = 1 way.
the total possible number of ways that the cat can climb the stair steps is therefore 1 + 15 + 35 + 28 + 9 + 1 = 89 ways.
we'll detail 4b + 2a so you can see how it works.
the possible ways are:
bbbbaa
bbbaab
bbbaba
bbaabb
bbabab
bbabba
baabbb
bababb
babbab
babbba
aabbbb
ababbb
abbabb
abbbab
abbbba
that's a total of 15 possible ways.
the others work the same way.
5b + 0a can only be bbbbb
0b + 10a can only be aaaaaaaaaa
1b + 8a can be:
baaaaaaaa
abaaaaaaa
aabaaaaaa
aaabaaaaa
aaaabaaaa
aaaaabaaa
aaaaaabaa
aaaaaaaba
aaaaaaaab
that a total of 9 possible ways.
if i did this correctly, then the total possible number of ways will be 89.
i detailed all the possible ways if there were only 6 steps instead of 10 and the method i used looks to be correct. therefore i'm assuming that the same method will work with 10 steps even though i didn't detail all the possible ways, but just some of them.
it is interesting that the combination formula will provide the same answer.
for example:
7! / (3! * 4!)= 35 and c(7,3) will also give you 35.
the combination formula is c(n,x) = n! / (x! * (n-x)!)
then n = 7 and x = 3, you get c(7,3) = 7! / (3! * 4!).
they're identical, so you can expect to get the same answer.
the key to solving this problem was not the formulas, but how to set up the problem logically.
that i did up front when i determined the possible combinations were:
5b
4b + 2a
etc.....
i used the bigger variable as the controlling variable.
with 1b, you can have 8 a's because 1b takes 2 steps and there are 8 steps remaining.
with 2b, you can have 6 a's because 2b's take 4 steps and there are 6 steps remaining.
etc.....
|
|
|
