ujjagrawal Posted June 21, 2012 Report Share Posted June 21, 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? Quote Link to comment Share on other sites More sharing options...
0 hhh3 Posted June 21, 2012 Report Share Posted June 21, 2012 one way.... he can either run up the stairs or walk .. lol Quote Link to comment Share on other sites More sharing options...
0 hhh3 Posted June 21, 2012 Report Share Posted June 21, 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 Quote Link to comment Share on other sites More sharing options...
0 MouseMan Posted June 21, 2012 Report Share Posted June 21, 2012 I'm guessing around 75? Quote Link to comment Share on other sites More sharing options...
0 MouseMan Posted June 21, 2012 Report Share Posted June 21, 2012 Either way, hh3 got it wrong with his answer. There was not one way as explained by him, but 2 ways. Quote Link to comment Share on other sites More sharing options...
0 Peekay Posted June 21, 2012 Report Share Posted June 21, 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 Quote Link to comment Share on other sites More sharing options...
0 hhh3 Posted June 21, 2012 Report Share Posted June 21, 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.. Quote Link to comment Share on other sites More sharing options...
0 MikeD Posted June 21, 2012 Report Share Posted June 21, 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 Quote Link to comment Share on other sites More sharing options...
0 witzar Posted June 21, 2012 Report Share Posted June 21, 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 Quote Link to comment Share on other sites More sharing options...
0 Peekay Posted June 21, 2012 Report Share Posted June 21, 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. Quote Link to comment Share on other sites More sharing options...
0 Rockmond Posted June 21, 2012 Report Share Posted June 21, 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? Quote Link to comment Share on other sites More sharing options...
0 jim Posted June 22, 2012 Report Share Posted June 22, 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. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted June 22, 2012 Report Share Posted June 22, 2012 Congrats to witzar! I just counted them. Quote Link to comment Share on other sites More sharing options...
0 ujjagrawal Posted June 22, 2012 Author Report Share Posted June 22, 2012 Solved. Congrats to all of you who got it correct. Yes, 89 is the correct answer. i.e. 10thnumber 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. Quote Link to comment Share on other sites More sharing options...
0 wilbloodworth Posted January 6, 2013 Report Share Posted January 6, 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>(); Quote Link to comment Share on other sites More sharing options...
0 wolfgang Posted January 6, 2013 Report Share Posted January 6, 2013 89 steps Quote Link to comment Share on other sites More sharing options...
Question
ujjagrawal
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?
Link to comment
Share on other sites
15 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.