標題: More on the one-dimensional sliding-coin puzzle 作者: Lin, Ting-YuTsai, Shi-ChunTsai, Wen-NungTsay, Jong-Chuang資訊工程學系Department of Computer Science 關鍵字: Combinatorial games;Puzzles;Algorithms 公開日期: 10-Jan-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.013http://hdl.handle.net/11536/23375 ISSN: 0166-218X DOI: 10.1016/j.dam.2013.08.013 期刊: DISCRETE APPLIED MATHEMATICS Volume: 162 Issue: 起始頁: 32 結束頁: 41 Appears in Collections: Articles

Files in This Item: