# Problem of the Week Problem C and Solution Just Keep Hopping

## Problem

In a computer game, a frog jumps along a row of lily pads. There are ten lily pads in the row, numbered from $$1$$ to $$10$$ starting on the left.

From any lily pad the frog can jump either two lily pads right or three lily pads left, as long as it lands on one of the ten lily pads.

For example from lily pad $$8$$, the frog can jump either three lily pads left to pad $$5$$, or two lily pads right to pad $$10$$. However, from lily pad $$2$$, the frog can only jump two lily pads right to pad $$4$$ because jumping three lily pads left would take it past pad $$1$$ so there would be no lily pad to land on.

If the frog starts on lily pad $$1$$ and visits every lily pad exactly once, what is the number on the last lily pad it lands on?

This problem was inspired by a past Beaver Computing Challenge (BCC) problem.

## Solution

Starting on lily pad $$1$$, the frog can only jump two lily pads right to pad $$3$$. From there, it can only jump two lily pads right to pad $$5$$. Lily pads that have been visited are shown in grey.

From lily pad $$5$$ the frog can either jump three lily pads left to pad $$2$$, or two lily pads right to pad $$7$$. However, the only way to visit pad $$2$$ is from pad $$5$$, and since the frog visits each lily pad exactly once, it canâ€™t come back to pad $$5$$ later. So the frog must jump to pad $$2$$ now.

From lily pad $$2$$ the frog can only jump two lily pads right to pad $$4$$. From there, it can only jump two lily pads right to pad $$6$$, from there it can only jump two lily pads right to pad $$8$$, and from there it can only jump two lily pads right to pad $$10$$.

From lily pad $$10$$ the the frog can only jump three lily pads left to pad $$7$$. From there, it can only jump two lily pads right to pad $$9$$.

At this point all of the lily pads have been visited exactly once. Therefore, the last lily pad that the frog lands on is pad $$9$$.