Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A garden path is a row of paving slabs. Lin starts just before the first slab and moves forward, each time onto the next slab or by jumping one slab to land on the slab after it. She must finish on the last slab. Different orders of short and long moves count as different ways.
Find the number of ways she can reach the last slab. Set up a recurrence by looking at her last move, and work forward from the starting values. Then find how many of those ways use exactly long jumps, by a second method: count the moves and choose which are long.
Name the count . Split on the first or the last step so that each case is a smaller copy of the same question. Check that the cases do not overlap and cover everything, then find the starting values by hand.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. A Fibonacci recurrence for the total; a binomial coefficient for the second part.
Step 1. The recurrence. Let be the number of ways to reach slab . The last move comes from slab or from slab , and these cases do not overlap. So .
Step 2. Starting values. (one short move) and (two short moves, or one long jump).
Step 3. Work forward. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610. So .
Step 4. Exactly four long jumps. Four long jumps cover slabs, so slabs are left for short moves. That is moves, and we choose which are long: .
Check. Adding over to long jumps gives , the same total.
Answer: ways, of which use exactly long jumps.
Log in to join the discussion.
Loading…