# An amphibious enigma

Another week, another Riddler. The question:

A frog needs to jump across 20 lily pads. He starts on the shore (Number 0) and ends precisely on the last lily pad (Number 20). He can jump one or two lily pads at a time. How many different ways can he reach his destination?

What if he can jump one, two or three at a time? Or four? Five? Six? Etc.

The way to beat this game is to look at the ways to reach pad. The first pad (pad_1) can only be reached by jumping from pad_0, so there is only one way to get there. Pad_2 can only be reached from pad_0 and pad_1, so number of ways to get to pad_2 is the sum of the ways to get to pad_0 and pad_1, which is two. Continuing this the number of ways to get to pad_3 is the sum of pad_2 and pad_1, which is 5.

This results in the Fibonacci Sequence, shown here. This means the number of ways to get to pad_20 is 10946.

If the frog can jump 3, 4, 5, etc the sequence becomes the Tribonacci Numbers (121415), Tetranacci numbers (283953), etc

Advertisements