Staircase climbing

Question:

You are climbing a stair case. Each time you can either climb 1 stair or 2 stairs. The staircase has n stairs. In how many distinct ways can you climb the staircase ?

Answer:

There are two possibilities for the last performed step: one stair or two stairs.

Thus, the number of possibilities for n stairs will be the number of possibilities to climb n-1 stairs (in case the last step is one stair long) plus the number of possibilities to climb  n-2 stairs (in case the last step is two stairs long).
Looks like the answer is related to Fibonacci numbers:
S(n)=S(n-1)+S(n-2) with S(1)=1 and S(2)=2

 Source: http://www.manager.ro/articole/analize/16-intrebari-din-iad-puse-in-timpul-interviurilor-de-angajare-la-facebook-google-citigroup-si-altii-9423.html

 

Advertisements
This entry was posted in Math. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s