2
$\begingroup$

This situation occurred today when I was introduced to this riddle.

There are 4 lilypads. There is a frog on the first lilypad that can hop 1 lilypad to the left or right every turn. After 19 turns, the frog must be on the fourth lilypad. How many ways can the frog do this?

So to clarify, X must equal 4 by incrementing or decrementing 19 times. X must stay within $[1,4]$.

Numbering the lilypads 1 2 3 and 4, an example solution could be

1 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 4

or

1 2 3 4 3 2 1 2 3 2 3 4 3 2 1 2 3 4 3 4

I understand that in reality, only 17 of the moves matter since the first move is guaranteed to be to the right, and so is the last, but I don't understand how to calculate every possible solution when lilypads 2 and 3 have 2 different possible branches while 1 and 4 only have one possible branch.

$\endgroup$
2
  • $\begingroup$ You can plot it as a graph. 1-2, 2-3, 3-4. From there you can check, starting from 1, in how many ways you can move as long as you finish at 4. $\endgroup$
    – OFRBG
    Oct 13 '16 at 0:36
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Adjacency_matrix#Matrix_powers ​ ​ $\endgroup$
    – user57159
    Oct 13 '16 at 0:38
0
$\begingroup$

For each lilypad $p$ let $p_n$ denote the number of ways to land on it after exactly $n$ jumps starting from pad 1 (so $1_n$, $2_n$, $3_n$ and $4_n$ from left to right).

Because of parity considerations, we can perform the first compulsory jump to pad 2 first and then consider the remaining 18 jumps in 9 pairs; the frog will always be on pads 2 and 4 in the process. In a pair of jumps:

  • starting from pad 2, the frog can return to pad 2 in two ways and go to pad 4 in one way
  • starting from pad 4, the frog can return to pad 4 in one way and go to pad 2 in one way

In equations these relations become $$2_{2k+1}=2\cdot2_{2k-1}+4_{2k-1}$$ $$4_{2k+1}=2_{2k-1}+4_{2k-1}$$ $$2_1=1,\ 4_1=0$$ For working up to $4_{19}$ it's easier to work explicitly rather than solve a matrix:

n   2_n   4_n
1   1     0
3   2     1
5   5     3
7   13    8
9   34    21
11  89    55
13  233   144
15  610   377
17  1597  987
19  4181  2584

The Fibonacci numbers are generated, the sequence snaking between $2_n$ and $4_n$. The answer to the question is 2584.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.