More on the one-dimensional sliding-coin puzzle

Ting-Yu Lin, Shi-Chun Tsai*, Wen Nung Tsai, Jong Chuang Tsay

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

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 languageEnglish
Pages (from-to)32-41
Number of pages10
JournalDiscrete Applied Mathematics
Volume162
DOIs
StatePublished - 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