Ten Stepping Stones

  • Medium
  • River crossing puzzles
  • Tests: Recognising a recurrence in a crossing

The puzzle

A stream is crossed by ten stepping stones in a line. You may hop to the next stone or skip one and land on the stone after it, but never skip two.

How many different sequences of hops take you across all ten?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Count the small cases first: one stone, two stones, three stones.

Hint 2

To reach stone 10 you arrived from stone 9 or stone 8, and nowhere else.

Show the answer Hide the answer

89 routes - the eleventh Fibonacci number.

How to get there

Let f(n) be the number of ways to reach stone n. The last hop came from stone n-1 or stone n-2, and those two sets of routes are different and cover everything, so f(n) = f(n-1) + f(n-2).

Start it off: f(1) = 1 and f(2) = 2 (one hop then another, or one skip). Then f(3) = 3, f(4) = 5, f(5) = 8, f(6) = 13, f(7) = 21, f(8) = 34, f(9) = 55, f(10) = 55 + 34 = 89.

That is the Fibonacci sequence, arriving here because the restriction "one or two" gives exactly two ways to have made the last move. Allow hops of one, two or three and the recurrence becomes f(n-1) + f(n-2) + f(n-3), which grows faster and is no harder to compute.

The technique worth keeping

Count by the last step. Asking "where did I come from?" splits the routes into disjoint groups and turns a counting problem into a recurrence you can run down a page in seconds.