Jumping Lily Pads

A frog on the shore (think of the shore as lily pad zero) has a line of 20 lily pads, each numbered 1 to 20.  The frog is able to jump one or two lily pads at a time.  That is, starting from shore, the first jump can either be to lily pad 1 or lily pad 2.  How many ways can the frog jump to the 20th lily pad if it can only move forward?

This was the 98th Riddle from FiveThirtyEight, called Can You Help A Frogger Out? 

I will be using combinations and special permutations to count these.  To learn more about counting with combinations and special permutations, check out Counting Can Be Really Tough and Counting When There Are Repeats.

To simplify this problem, the question is asking how many ways can you write a sum of 20 using 1’s and/or 2’s.

Let’s try a simpler problem first, and pretend there are only 5 lily pads.  Let’s count the number of ways the frog can jump to the fifth lily pad.

Approach 1: Using Combinations and Special Permutations

Using only 1’s: 1+1+1+1+1 = 5. This is equivalent to the frog jumping to lily pad 5 one lily pad at a time.  This number can also be arrived at by noticing there are 5 numbers being used, 5 of which are 1’s and none of which are 2’s.  So, using combinations or special permutations, we find

\displaystyle \binom{5}{5}\cdot\binom{0}{0} = 1 = \frac{5!}{5!\cdot 0!}.

Using three 1’s and one 2:

  • 1+1+1+2=5 (the path is 1-2-3-5)
  • 1+1+2+1=5 (the path is 1-2-4-5)
  • 1+2+1+1=5 (the path is 1-3-4-5)
  • 2+1+1+1=5 (the path is 2-3-4-5)

Again, using either combinations or special permutations, we find that using 4 numbers, three of which are 1’s and one of which is 2, there are

\displaystyle \binom{4}{3}\cdot\binom{1}{1} = 4 = \frac{4!}{3!\cdot 1!}.

Finally, using one 1 and two 2’s:

  • 1+2+2=5 (the path is 1-3-5)
  • 2+1+2=5 (the path is 2-3-5)
  • 2+2+1=5 (the path is 2-4-5)

Noticing there are 3 total numbers used, one of which is a 1 and two of which are 2’s, we count

\displaystyle \binom{3}{1}\cdot \binom{2}{2} = 3 = \frac{3!}{1!\cdot 2!}.

Now, for the larger question of the 20 lily pads.  Let’s count systematically:

  • Using 20 (1)’s: \displaystyle \binom{20}{20} = 1
  • Using 18 (1)’s and 1 (2): \displaystyle \binom{19}{18}\cdot \binom{1}{1} = 19
  • Using 16 (1)’s and 2 (2)’s: \displaystyle \binom{18}{16}\cdot \binom{2}{2} = 153
  • Using 14 (1)’s and 3 (2)’s: \displaystyle \binom{17}{14}\cdot \binom{3}{3} = 680
  • Using 12 (1)’s and 4 (2)’s: \displaystyle \binom{16}{12}\cdot \binom{4}{4} = 1820
  • Using 10 (1)’s and 5 (2)’s: \displaystyle \binom{15}{10}\cdot \binom{5}{5} = 3003
  • Using 8 (1)’s and 6 (2)’s: \displaystyle \binom{14}{8}\cdot \binom{6}{6} = 3003
  • Using 6 (1)’s and 7 (2)’s: \displaystyle \binom{13}{6}\cdot \binom{7}{7} = 1716
  • Using 4 (1)’s and 8 (2)’s: \displaystyle \binom{12}{4}\cdot \binom{8}{8} = 495
  • Using 2 (1)’s and 9 (2)’s: \displaystyle \binom{11}{2}\cdot \binom{9}{9} = 55
  • Using 10 (2)’s: \displaystyle \binom{10}{10} = 1.

If we sum all of those numbers up, we get 10946.

Approach 2: Using the Fibonacci Sequence

Since the frog can only jump one or two lily pads at a time, the number of ways he can jump to the fifth lily pad can be found by summing together the number of ways he can jump to the third lily pad with the number of ways he can jump to the fourth lily pad.

Let’s take a closer look at this.  The number of ways we can create a sum of three:

  • 1+1+1
  • 1+2
  • 2+1

The number of ways we can create a sum of four:

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2

If we take the first list of three and add a 2 to each of those sums, and take the list of five and add a 1 to each of those sums, we exhaust all of the ways to get to lily pad 5, which is 8 ways.

Let’s take a look at the first several terms of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ….

The first 1 that you see in the Fibonacci sequence is the zeroth spot.  (The number of ways he can not jump from shore is the vacuous 1 way).

The Fibonacci sequence is created by starting with 1, 1, and then creating the sequence by summing the previous two.

Starting with 0 and counting to 5, we see that the 5th Fibonacci number is 8, which is our answer.  To answer the bigger question posed earlier, go out to the 20th Fibonacci number: 10946.

This short video explaining the five lily pad jumping may help you visualize it best.

 

3 thoughts on “Jumping Lily Pads

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s