Jump to content
BrainDen.com - Brain Teasers
  • 0
ujjagrawal

A Child and a Staircase

Question

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

15 answers to this question

  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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)

  • Upvote 1

Share this post


Link to post
Share on other sites
  • 0

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.

  • Upvote 3

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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?

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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>();

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.

×