Posts Tagged ‘Puzzles’

Fibonacci Numbers

January 21, 2010

I’m guessing that all my blog readers know what the Fibonacci sequence is. For the uninitiated, it is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…. ad infinitum.

Each number is the sum of the preceding 2 numbers. That is,

F(n) = F(n-1) + F(n-2)

where,
F(0) = 0
F(1) = 1

A Neat Trick:
————-
How can you easily convert miles to kilometers? You can use Fibonacci numbers: 5 miles is 8 kilometers (actually 8.045 km). 8 miles is 13 kilometers (12.87 km). 13 miles is, yes you guessed it, 21 kilometers (20.917 km). “But hey, this will only work for Fibonacci numbers!”. Well, I’m not done yet! Say you want to convert 20 miles to kilometers. Simply express 20 as the sum of Fibonacci numbers:

20 = 13 + 5 + 2.

Convert each number according to our mile-kilometer rule:

= 21 + 8 + 3
= 32

Voila! In actuality, 20 miles comes to 32.18 km. Neat huh?

Can you guess the logic behind this? The reason this works is as follows:
To convert from miles to kilometers, we have to multiply by a factor of 1.609. Now, the Fibonacci sequence has an extremely interesting property – the ratio of two consecutive Fibonacci numbers approaches the Golden Ratio: 1.618. Mystery solved!

A Puzzle:
———
Now here is a question I was once asked:

“For a flight of stairs with n steps, write a program to print the number of ways you can climb it if you can only move either one or two steps forward at any point.”

I couldn’t figure it out in time, but understood the approach later (I think Prajwalit was the one who told me the answer). Since this post is about Fibonacci numbers, it’s a given that they make an appearance in this puzzle. The challenge is to explain why the Fibonacci numbers show up.

Finally, for a tougher programmatic challenge, modify the problem as follows:

“For a flight of stairs with n steps, write a program to print all the combinations of ways you can climb it if you can only move either one or two steps forward at any point. If n is entered as 3, your program should show the following output –
n = 3
1 1 1
1 2
2 1”