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

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