Posted 21 Jun 2012 There is a staircase with 10 steps. A child runs up the steps, either 1 step or 2 steps with each stride. How many different ways can the stairs be climbed by him? 0 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 one way.... he can either run up the stairs or walk .. lol 0 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 one way.... he can either run up the stairs or walk .. lol ... no sorry that makes it two... easy answer... if u want to rest ur brain 0 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 Either way, hh3 got it wrong with his answer. There was not one way as explained by him, but 2 ways. 0 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 Unless I missed something... All 1 steps - 1 way One 2 step - 8 ways Two 2 steps - 6 ways Three 2 steps - 4 ways Four 2 steps - 2 ways Five 2 steps - 1 way Total = 22 ways 0 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 Either way, hh3 got it wrong with his answer. There was not one way as explained by him, but 2 ways. dude... look at the spoiler in my second post... hi hi.. but the answer still could me wrong..bt anyways.. 0 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 I would say 89 because 1 1 1 1 1 1 1 1 1 1 (only 1 combination) 1 1 1 1 1 1 1 1 2 (9 combinations) 1 1 1 1 1 1 2 2 (28 combinations) 1 1 1 1 2 2 2 (35 combinations) 1 1 2 2 2 2 (15 combinations) 2 2 2 2 2 (only 1 combination) 1 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 Let F(n) be the number of different ways staircase of n steps can be climbed. You can start either with 2 steps (and n-2 remaining) or with 1 step (and n-1 remaining), which leads to a recurrence relation: F(n) = F(n-1) + F(n-2) Obviously F(0) = 1, F(1), and F(n+2) = F(n) + F(n+1) so you are looking for 10th Fibonacci number, which is 89. 3 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 Unless I missed something... All 1 steps - 1 way One 2 step - 8 ways Two 2 steps - 6 ways Three 2 steps - 4 ways Four 2 steps - 2 ways Five 2 steps - 1 way Total = 22 ways Not only did I miss something, I missed a lot - combinations of the 2 step options! The actual ways would be much more. 0 Share this post Link to post Share on other sites

0 Posted 21 Jun 2012 I have a clarification question. If there are 10 steps and a landing at the bottom and the top, the child would have to take 11 steps if taken one at a time, right? 0 Share this post Link to post Share on other sites

0 Posted 22 Jun 2012 442. Since we can solve this with either Fibonacii numbers or combinations, we can conclude that F10 = C(10,0) + C(9.1)+ ...+c(5.5). More generally Fn = C(n,0) + C(n-1.1) + C(n-2,2) + ... as long as the first number is no les than the second. NOTE If you interpet the question to mean 10 steps plus the upper landing the answer would be F11, a point one poster raised. In addition if we distinquish between first strride right foot and first stride left we would double our answer. 0 Share this post Link to post Share on other sites

0 Posted 22 Jun 2012 Congrats to witzar! I just counted them. 0 Share this post Link to post Share on other sites

0 Posted 22 Jun 2012 Solved. Congrats to all of you who got it correct. Yes, 89 is the correct answer. i.e. 10^{th}^{}number in the Fibonacci series (1,2,3,5,8,13,21,34,55,89,144). However, I agrees with Rackmond question's too, if we consider 10 steps + a upper landing then the answer will be 144. 0 Share this post Link to post Share on other sites

0 Posted 6 Jan 2013 I think 89 is correct. Here's a simple C# implementation that you can test out if you want to use LinqPad: void Main() { countWays(10).Dump(); } int countWays(int steps) { if (steps < 0) return 0; if (steps == 0) return 1; if (_map.ContainsKey(steps)) return _map[steps]; _map[steps] = countWays(steps - 1) + countWays(steps - 2); return _map[steps]; } private readonly Dictionary<int, int> _map = new Dictionary<int, int>(); 0 Share this post Link to post Share on other sites

Posted

There is a staircase with 10 steps. A child runs up the steps, either 1 step or 2 steps with each stride. How many different ways can the stairs be climbed by him?

## Share this post

## Link to post

## Share on other sites