Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 6 / b / Solution

After one jump, the largest reachable index is two. After at most two jumps, the reachable indices form the prefix $[0,5]$: index two can reach five, but no reachable departure before that second jump can go further. From indices zero through five, the largest endpoint of one further jump is $4+A[4]=9$. Thus three jumps cannot reach index ten.

The two routesare valid and use four jumps. Therefore $\boxed{\text{the minimum is four jumps, and the minimizing route is not unique}}$. The frontier argument proves the lower bound independently of merely exhibiting a route. In fact these are the two minimizing index sequences: the last departure in a four-jump solution must be eight or nine, reached in three jumps through four, which is reached in two jumps only through two.