To enter a building’s front door, residents must climb 8 steps. If a resident standing before the first step can climb one or two steps at a time, how many different ways can the person reach the top of the steps?
I solved it correctly by brute force. I added up the number of ways if the person climbs two steps 0, 1, 2, 3, or 4 times, which is 1+7+15+10+1=34. Are there any ways to solve it without brute force?
I think I get it, is it like a Fibonacci sequence? 1, 2, 3, 5, 8, 13, 21, 34
That’s one way, you can also use raw combinatorics.
How do you do it with raw combinatorics?
For the Fibonacci way, let f(n) be the number of options for n steps, n > 2.
If you start with a single step, you then have f(n-1) options for the remaining steps.
If you start with a double step, you have f(n-2) options for the remaining.
These two sets are disjoint.
So: f(n) = f(n-1) + f(n-2).
This was Greg’s approach to the problem.
Consider the ways you can reach 8 steps. One way is 11111111 - there is only one way to do that. Then, with one 2 (21111111), you have 7 possible ways. With two 2s (221111), you have \frac{6!}{2!4!} = 15 ways. With 3 2s, you have (22211) - this is \frac{5!}{3!2!} = 10 ways. With 4 2s, you again have only one way, namely 2222.
Hence, it sums up to 1 + 7 + 15 + 10 + 1 = 25 + 9 = 34.
Edit: I didn’t realise that you potentially meant this as brute-force, my bad if so. This and Fibonacci are the two main ways to work it out.
That was similar to the way I solved it. See my post.
Sorry I guess it was this way of counting and adding up 1+7+15+10+1=34 is pretty time consuming, so I said it’s brute force.
What do you think of my Fibonacci approach?
That is a reasonable approach to work out the problem, and the one I came up first.
btw, where did Greg posted the videos for “GRE Quant Problem Solving” solutions?
He hasn’t produced a dedicated series of solutions yet, however, some of them (including this one) were featured in past quant classes or the POTD (problem of the day).
Some of the solutions can be found in
https://new.gregmat.com/course/quant-practice
and
https://new.gregmat.com/daily
and
Help Us Out - Quant Questionshttps://new.gregmat.com/course/non-sequenced-quantclasses
To enter a building’s front door, residents must climb 8 steps. If a resident standing before the first step can climb one or two steps at a time, how many different ways can the person reach the top of the steps?
My try:
I) 1+1+1+1+1+1+2
for different arrangements I get 7 arrangements
ii) 1 + 1+1+1+2+2
I get 30 different arrangement
iii) 1+1+2+2+2
I get 20 different arrangements
iv) 1+1+1+1+1+1+1+1
Only 1 arrangement
and finally 2+2+2+2
Total no of ways to get to front door = 30+20+7+1+1=59
But the answer is 34. How is it? Am I doing it wrong?
How did you get 30 here, it would 15
Again, it would be 10, not 20
15 + 10 + 7 + 1 + 1 = 34
Yes. I did it wrong. I messed up the total arrangment calculation.
