Solution
The Frog and Twenty Pads
Show the problem again
Lily pads are numbered 0, 1, 2, ..., 20 in a straight line. A frog starts on pad 0. Each jump takes it forward exactly 2 pads or exactly 3 pads. How many different sequences of jumps bring the frog to land exactly on pad 20? Give an integer.
Worked solution
**Answer: 114.** Let a(n) be the number of jump sequences ending on pad n. The final jump is a 2 or a 3, so a(n) = a(n − 2) + a(n − 3), with a(0) = 1, a(1) = 0, a(2) = 1. Running the recurrence: a(3..20) = 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114. Check by direct counting: with b jumps of 3 and c jumps of 2 we need 3b + 2c = 20, so b is even. The options (b, c) = (0, 10), (2, 7), (4, 4), (6, 1) contribute C(10, 0) + C(9, 2) + C(8, 4) + C(7, 1) = 1 + 36 + 70 + 7 = 114 orderings.
Source: Original problem written for AxiomIQ.