• 0

A Child and a Staircase

Question

Posted · Report post

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

15 answers to this question

  • 0

Posted · Report post

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 · Report post

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 · Report post

I'm guessing around 75?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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 · Report post

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 · Report post

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 · Report post

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 · Report post

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 · Report post

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 · Report post

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 · Report post

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 · Report post

Congrats to witzar! I just counted them.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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
  • 0

Posted · Report post

89 steps

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.