Solution

ID: 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 : 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 . Thus three jumps cannot reach index ten.
The two routes
are valid and use four jumps. Therefore . 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.

New to topics? Read the docs here!