Problem #PRU-98363

Problems Fun Problems Word Problems Tables and tournaments Chessboards and chess pieces Discrete Mathematics Algorithm Theory Theory of algorithms (other)

Problem

Initially, on each cell of a 1×n board a checker is placed. The first move allows you to move any checker onto an adjacent cell (one of the two, if the checker is not on the edge), so that a column of two pieces is formed. Then one can move each column in any direction by as many cells as there are checkers in it (within the board); if the column is on a non-empty cell, it is placed on a column standing there and unites with it. Prove that in n1 moves you can collect all of the checkers on one square.