Moving into the Desert with Fibonacci
Martin Aigner · Mathematics Magazine · 1997
In Volume II of their admirable book Winning Ways [1] the authors consider the following solitaire game. Suppose we draw a horizontal line on an unbounded board consisting of squares. On one side of the line stands the (finite) solitaire army, with a square occupied by at most one soldier (peg). On the other side is the desert. A move consists of a jump of one peg over another onto a free place, in the horizontal or vertical direction, removing the peg that has been jumped over. How many soldiers do we need to move a scout one, two, three, .. . n steps into the desert? This rather bland-looking game has a surprising answer. It is easy enough for a scout to venture one or two steps into the desert: