A square is divided into cells. In total tokens are placed at some cell. During every round, a player can move one token from cell to cell , and one token from cell to cell , provided that cell contained at least two tokens, and are symmetric with respect to , and finally and are adjacent to . Is it possible that after a few such rounds every cell on the board contains exactly one token, in case:
a) ;
b) ?
Solution
Answer: a) impossible; b) possible.
a) Consider square , for positive integer . Let us denote the most left column by , adjacent column by , and so on, the most right column by . For any cell we denote function , provided that cell is located in the column . For every token in the same way let provided that token is placed on the cell in the column at the moment. Finally, by we denote the sum of for all tokens on the board. It is clear that after every round is not changed. At the end of our process we must have
At the beginning of our process provided that all tokens are placed at the cell in . And for we get a contradiction.
b) Let us consider the case . It follows from previous arguments that the statement of the problem could be true only in the case when all tokens are placed on the central cell at the beginning. In this case we provide the algorithm. Let us note that in every cell we write the number of tokens placed there. Using induction, we prove the following statements
Statement 1. For every positive integer in a row of length from the position
we can get the position
Statement 2. For every positive integer in a row of length from the position
we can get the position
Proof. It is clear for . Suppose that for statements are true, let us prove them for . At the beginning, we have tokens on the central cell. Two of them we will not move. The rest tokens we can move (according to the induction hypothesis) to the position
Now consider the following replacing
We can apply the induction hypothesis now, and get
Both statements are proved now.
We can easily prove the statement of the problem now. Divide all tokens into equal groups with tokens in every group. Using our statements, we can replace tokens such that in every cell of the central column exactly one group will be placed. And then just use the statements again to replace tokens such that in every cell of every row exactly one token will be placed.