Let and be distinct positive integers. There is an infinite chessboard, and each cell can be filled with a nonnegative integer. The board is initially empty. We continually perform the following operation:
(i) If a pair of identical numbers can be found on the board, then we choose two cells with identical numbers, and increase the number in one cell by and the number in the other cell by .
(ii) If no pair of identical numbers can be found on the board, then we fill two empty cells each with a .
Prove that: no matter what, after some operation, only operation (i) can be performed from then on.
Solution
Without loss of generality assume , since we can simply divide and both by . Also, without loss of generality assume .
1. First, suppose that after several operations (i) and operations (ii), we are forced to perform operation (ii) once again. For all integers , let denote the total number of times has appeared on the board so far. Clearly , and for all .
Note that for all , since we are forced to perform (ii) in this round, this means that there is currently at most one on the board; and if other 's appeared in previous rounds, this means there were once two 's, one of which was increased to in some previous round. The same holds for . The above observation tells us that we have the following relation:
2. Since , every positive integer can be expressed as , where are nonnegative integers. We now prove:
Lemma 1. For all , we have
Proof. We induct on . The case is clear. Suppose the lemma holds when ; then when , note that at least one of and is positive, and without loss of generality assume . Then by (1) and the induction hypothesis, we have
which proves the lemma.
3. Now, suppose that we perform operation (ii) infinitely many times, that is, in part 1 can be any positive integer. Take , and take . Note that can all be expressed as , where and . Hence by Lemma 1, we have
This shows that are all greater than or equal to 2, and hence by (1) and mathematical induction, we know that holds for all . But this means that after finitely many operations, the board would have infinitely many numbers on it, which is impossible, a contradiction!