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

1 Like

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).

1 Like

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.