p&c q15

[Saumyojit]

In how many ways can a 12 step staircase be climbed taking 1 step or 2steps at a time ?


Now the approach is
Either 12 single steps --> 12c1=12 .

Or
10 single steps and one two Steps= 12c2= 66

Total 78


in the question 2 steps at a time means at one moment he can take two step at a time but that doesn't mean he can take only one two steps in the entire journey at a time .



where am I wrong?

 

[Dr.Peterson]

In how many ways can a 12 step staircase be climbed taking 1 step or 2steps at a time ?

in the question 2 steps at a time means at one moment he can take two step at a time but that doesn't mean he can take only one two steps in the entire journey at a time .

As always, we have to start by making sure we understand what it means, especially since you are not familiar with all English idioms. So rather than starting by showing an attempt to solve the problem, you should start by showing your interpretation.

If we take two steps at a time, it means that each time we move, we go up two steps. If we take one or two steps at a time, each time we move we go up either one or two steps.

Taking a small example (which is an excellent way to start), suppose there are only 4 steps. Here are the possible ways:

1+1+1+1 (one step each time)
1+1+2
1+2+1
2+1+1
2+2

As you can see, one way to model this is as "the number of different sums whose terms are either 1 or 2, and whose sum is 4". But we can't just count ways to arrange 1 and 2, because the number of terms varies. Likewise the number of 2s can vary.

There are many ways you could think about this. If you start the way you did, you will need to continue, until you have covered all possible numbers of double steps.

 

[Saumyojit]

There are many ways you could think about this. If you start the way you did, you will need to continue, until you have covered all possible numbers of double steps.

Starting from left as if it's the bottom ..
a b c d e f g h i j k l

Possible combination :
12 single step --> one way

10 single + one double step = (eg: abcd ef ghijkl --->one combo )
But i have to make sure that the two steps that i will take for DOUBLE are consecutive . How to ensure that ?

8 Single + two double , 6 single + three double , 4 single + four double , 2 single + 5 double , 6 doubles.

 

[pka]

Comment: This is such a standard counting problem that there is no need to tell either of us the workings of it.
There are eleven ways to reach the twelfth step using one twostep and ten single steps.
That is the number of ways that one can rearrange the string [imath]EEEEEDEEEEE[/imath]

 

[Dr.Peterson]

Starting from left as if it's the bottom ..
a b c d e f g h i j k l

Possible combination :
12 single step --> one way

10 single + one double step = (eg: abcd ef ghijkl --->one combo )
But i have to make sure that the two steps that i will take for DOUBLE are consecutive . How to ensure that ?

8 Single + two double , 6 single + three double , 4 single + four double , 2 single + 5 double , 6 doubles.

You can ensure that by treating the double step as a single item. I think you've seen that done before. pka showed you what to do for one double step, using one D and 10 Es.

And in my example for 4 steps, I gave you a model:

Arrange each of these in all possible ways:​

​

1111​

211​

22​

 

[Saumyojit]

Comment: This is such a standard counting problem that there is no need to tell either of us the workings of it.
There are eleven ways to reach the twelfth step using one twostep and ten single steps.
That is the number of ways that one can rearrange the string [imath]EEEEEDEEEEE[/imath]

yeah so easy .

Thanks

 

[Cubist]

There is an easier method, which I think is hinted at in this post by @Dr.Peterson :-
https://www.freemathhelp.com/forum/threads/p-c-q14.130815/post-542569, "The standard solution to this doesn't even use combinations or permutations, though it can be done that way".

I suspect that he didn't reveal the other method because you seem to be learning about combinations and permutations at the moment. Therefore that is the method that you ought to use. But, for interest, here is another way to solve the problem...

Write down the ways for 1 and 2 steps:- 1, 2. Now the next number in the list (in this case for three steps) is given by the SUM of:-

• the previous number in the list (because you can take a single step after each one of those ways)
• the number before that (because you can take a double step after each one of those ways)

So: 1, 2, 1+2=3, 2+3=5, 3+5=8, 5+8=13, 8+13=21, 13+21=34, 21+34=55, 34+55=89, 55+89=144, ?+?=? (the last is the ways to climb 12 steps)

This is actually a famous sequence, with a direct formula. Have you heard of it and can you remember its name?

 

[Dr.Peterson]

There is an easier method, which I think is hinted at in this post by @Dr.Peterson :-
https://www.freemathhelp.com/forum/threads/p-c-q14.130815/post-542569, "The standard solution to this doesn't even use combinations or permutations, though it can be done that way".

I suspect that he didn't reveal the other method because you seem to be learning about combinations and permutations at the moment. Therefore that is the method that you ought to use. But, for interest, here is another way to solve the problem...

Write down the ways for 1 and 2 steps:- 1, 2. Now the next number in the list (in this case for three steps) is given by the SUM of:-

• the previous number in the list (because you can take a single step after each one of those ways)
• the number before that (because you can take a double step after each one of those ways)

So: 1, 2, 1+2=3, 2+3=5, 3+5=8, 5+8=13, 8+13=21, 13+21=34, 21+34=55, 34+55=89, 55+89=144, ?+?=? (the last is the ways to climb 12 steps)

This is actually a famous sequence, with a direct formula. Have you heard of it and can you remember its name?

Yes, that's exactly what I had in mind, and the reason I didn't pursue it. In particular, although there is an explicit formula for this famous sequence, it's not the least bit obvious or intuitive, so the most natural way to use it would be your successive additions (which is easier than the other calculations, but might not be for a really long stairway).

In particular, I was hoping for an eventual opportunity to mention my blog post that shows several problems like this, and includes the combinatorial solution and the formula(s) for the Famous Sequence, which I will still not name here though the link will reveal it ...