Logic puzzles, riddles, math puzzles and brainteasers - pzzls.com

Vandaag is het 19 January 2018

Add using:

Painting stairs - math puzzle

Difficulty: 

   Rating: 2.4/5.0

Share this pzzl:  

To enter the house of the professor, you first have to walk up a stairs which consists out of twenty steps. The professor thinks his stairs are boring so he decides to paint them. He buys two colors, yellow and green.

Every step will be either painted yellow or green and moreover the professor does not want to have two yellow steps directly after each other. In how many ways can the professor paint his stairs? And what is the name of the professor?
stairs

Explanation

treden
Suppose the stairs consists out of one step. Then the staris can be painted in two ways, see the figure above.
If the stairs have two steps, there are three possibilities.
If the stairs have three steps, there are five possibilities.

The rules for painting are:
After each yellow step there will be a green step.
After each green steps there will be either a yellow or a green step.

Let's call the number of ways in which the professor can paint a stairs of x steps N(x). Then it is easily seen that the latest step of a stairs with x steps can be painted green in N(x-1) ways. De latest step of a stairs with x - 1 steps can be painted green in N(x-2) ways. From this is follows that the latest step of a stairs with x steps can be painted yellow in N(x-2) ways.

So the professor can paint a stairs of x steps in N(x) = N(x-1) + N(x-2) ways.

From the figure it follows that N(1) = 2 en N(2) = 3.

Hence
x12345 678910
N(x)235813 21345589144
A calculation learns that N(20) = 17711. The professor can paint his stairs in 17711 ways. Such a series is called the Fibonaci series, after an Italian mathematician. Most probably the professor is called Fibonaci.