MathDB

(553) 3

Part of 1997 Tournament Of Towns

Problems(1)

TOT 553 1997 Autumn J A3 checkers on a 1xn board

Source:

9/11/2024
Initially there is a checker on every square of a 1×n1\times n board. The first move consists of moving a checker to an adjacent square thus creating a stack of two checkers. Then each time when making a move, one can choose a stack and move it in either direction as many squares on the board as there are checkers in the stack. If after the move the stack lands on a non-empty square, it is placed on top of the stack which is already there. Prove that it is possible to stack all the checkers on one square in n−1n - 1 moves.
(A Shapovalov)
combinatorics