More on the one-dimensional sliding-coin puzzle
Consider a line of n n nickels and n n pennies with all nickels arranged to the left of all pennies, where n?3 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 k adjacent coins to new positions without rotating. We first prove that for any integer k?2 k ? 2 it takes at least n n moves to achieve the goal. A well-known optimal solution for the case k=2 k = 2 matches the lower bound. We also give optimal solutions for the case k=3 k = 3 .
puzzles combinatorial games algorithms