Jump to content
BrainDen.com - Brain Teasers
  • 0

A Child and a Staircase


ujjagrawal
 Share

Question

15 answers to this question

Recommended Posts

  • 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
Link to comment
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
Link to comment
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.
Link to comment
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.

Link to comment
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.

Link to comment
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>();
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...