There are n coins placed in a row. The goal is to form n/2 pairs of them
by a sequence of moves. On the first move a single coin has to jump over
one coin adjacent to it, on the second move a single coin has to jump
over two adjacent coins, on the third move a single coin has to jump over
three adjacent coins, and so on, until after n/2 moves n/2 coin pairs are
formed. (On each move, a coin can jump right or left but it has to land on
a single coin. Jumping over a coin pair counts as jumping over two coins.
Any empty space between adjacent coins is ignored.) Determine all the
values of n for which the problem has a solution and design an algorithm
that solves it in the minimum number of moves for those n’s.
- via Algorithmic puzzles