Climbing 100 Steps
Date: 05/01/2003 at 12:02:08 From: Matt Subject: Combinatorics Find the number of ways in which you can climb 100 steps if you can go up 1 or 2 steps at a time. I was thinking that n = 100 steps and there are two choices for each step you land on, but I wasn't sure how to break it down using 1 step and 2 steps at a time. I figured that there must be an even number of 1-steps and of course an even number of 2-steps to make 100, but I lost it there.
Date: 05/01/2003 at 14:34:24 From: Doctor Robert Subject: Re: Combinatorics Start with an easier problem. Let's just have 10 steps. Then a table will show the number of 1-step and 2-step jumps needed. 1-step 2-step 10 0 8 1 6 2 4 3 2 4 0 5 Now the question is, "For each of these possibilities, how many ways can the different steps be arranged?" There's only one way to do the steps one at a time. There are nine ways to do eight one-step and one 2-step jumps. These numbers turn out to be C(10,0), C(9,1), respectively. For the next, the possibilities number C(8,2) or 28. C(7,3)= 35 C(6,4) = 15 C(5,0) = 1. The total number of ways is therefore 1+9+28+35+15+1 = 89 ways for TEN steps. Good luck on the ONE HUNDRED steps. There might be a clever way to find the sum without doing all the grunt work. - Doctor Robert, The Math Forum http://mathforum.org/dr.math/
Date: 05/01/2003 at 17:43:11 From: Doctor Douglas Subject: Re: Combinatorics Hi Matt, Thanks for writing to the Math Forum. I'd like to supplement Dr. Robert's answer. There is another way to approach this problem, which is to try to enumerate the number of ways to reach a given step. step ways to get there ---- ----------------- 1 1 (has to be a 1-step) 2 2 (either a 2-step, or two 1-steps) 3 3 (either 1+1+1, 1+2, or 2+1) 4 5 (1+1+1+1, 1+2+1, 2+1+1, 1+1+2, 2+2) 5 8 Why? The reason is that in order to get to step 5, we must either get to step 3 (and take a 2-step), or get to step 4 (and take a 1-step). Thus the number of ways to get to step 5 is the number of ways to get to step 3 plus the number of ways to get to step 4: N(5) = N(4) + N(3) The case of getting to step 3 and then taking a 1-step and then another 1-step is counted in the number of ways to get to step 4. Let's continue the table: 6 13 7 21 8 34 9 55 10 89 (so Dr. Robert's method is verified) 11 144 Do these numbers look familiar? If they do, they should - it is a Fibonacci sequence, and the answer to your question is the hundredth (or perhaps the 101st, depending on how you index things) Fibonacci number. I'm sure you'll agree that this method is somewhat less work computationally than going through the entire combinatorial list. - Doctor Douglas, The Math Forum http://mathforum.org/dr.math/
Date: 05/01/2003 at 19:31:22 From: Matt Subject: Combinatorics Thanks for the prompt replies; you guys are awesome. After seeing the numbers that were sent from that method, I figured I could use recurrence equations and get an answer a lot quicker for the 100 steps. It came out to be a messy answer but I'm almost 100% sure it's correct. I'm a mathematics major and your help will help me get a better grade on my final tomorrow no doubt. Thanks again.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.