標題: | 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 |
顯示於類別: | 期刊論文 |