### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 32-41 |

Number of pages | 10 |

Journal | Discrete Applied Mathematics |

Volume | 162 |

DOIs | |

State | Published - 10 Jan 2014 |

### Keywords

- Algorithms
- Combinatorial games
- Puzzles

## Fingerprint Dive into the research topics of 'More on the one-dimensional sliding-coin puzzle'. Together they form a unique fingerprint.

## Cite this

Lin, T-Y., Tsai, S-C., Tsai, W. N., & Tsay, J. C. (2014). More on the one-dimensional sliding-coin puzzle.

*Discrete Applied Mathematics*,*162*, 32-41. https://doi.org/10.1016/j.dam.2013.08.013