Title: More on the one-dimensional sliding-coin puzzle
Authors: Lin, Ting-Yu
Tsai, Shi-Chun
Tsai, Wen-Nung
Tsay, Jong-Chuang
Department of Computer Science
Keywords: Combinatorial games;Puzzles;Algorithms
Issue Date: 10-Jan-2014
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 hew 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. (C) 2013 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.dam.2013.08.013
ISSN: 0166-218X
DOI: 10.1016/j.dam.2013.08.013
Volume: 162
Begin Page: 32
End Page: 41
Appears in Collections:Articles

Files in This Item:

  1. 000328311400004.pdf