標題: More on the one-dimensional sliding-coin puzzle
作者: Lin, Ting-Yu
Tsai, Shi-Chun
Tsai, Wen-Nung
Tsay, Jong-Chuang
資訊工程學系
Department of Computer Science
關鍵字: Combinatorial games;Puzzles;Algorithms
公開日期: 10-一月-2014
摘要: 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
http://hdl.handle.net/11536/23375
ISSN: 0166-218X
DOI: 10.1016/j.dam.2013.08.013
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 162
Issue: 
起始頁: 32
結束頁: 41
顯示於類別:期刊論文


文件中的檔案:

  1. 000328311400004.pdf