Consider a line of n nickels and n pennies with all nickels arranged to the left of all pennies, where n≥3. The puzzle asks the player to rearrange the coins such that nickels and pennies alternate in the line. In each move, the player is allowed to slide k adjacent coins to new positions without rotating. We first prove that for any integer k≥2 it takes at least n moves to achieve the goal. A well-known optimal solution for the case k=2 matches the lower bound. We also give optimal solutions for the case k=3.
- Combinatorial games