Let and be distinct positive integers. The following infinite process takes place on an initially empty board.
(i) If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by and the other by .
(ii) If no such pair exists, we write down two times the number .
Prove that, no matter how we make the choices in (i), operation (ii) will be performed only finitely many times.
Solutions — 2
Solution 1
We may assume ; otherwise we work in the same way with multiples of .
Suppose that after moves of type (ii) and some moves of type (i) we have to add two new zeros. For each integer , denote by the number of times that the number appeared on the board up to this moment. Then and for . Since the board contains at most one , every second occurrence of on the board produced, at some moment, an occurrence of ; the same stands for . Therefore,
yielding
Since , every integer is expressible in the form , with integer .
We will prove by induction on that if , with nonnegative integers, then
The base case is trivial. Assume now that (3) is true for . Then, if and , at least one of the numbers and —say —is positive, hence by (2),
Assume now that we must perform moves of type (ii) ad infinitum. Take and suppose . Since each of the numbers can be expressed in the form , with and , after moves of type (ii) have been performed times and we have to add a new pair of zeros, each , is at least . In this case (1) yields inductively for all . But this is absurd: after a finite number of moves, cannot attain nonzero values at infinitely many points.
Solution 2
We start by showing that the result of the process in the problem does not depend on the way the operations are performed. For that purpose, it is convenient to modify the process a bit.
Claim 1. Suppose that the board initially contains a finite number of nonnegative integers, and one starts performing type (i) moves only. Assume that one had applied moves which led to a final arrangement where no more type (i) moves are possible. Then, if one starts from the same initial arrangement, performing type (i) moves in an arbitrary fashion, then the process will necessarily stop at the same final arrangement.
Proof. Throughout this proof, all moves are supposed to be of type (i).
Induct on ; the base case is trivial, since no moves are possible. Assume now that . Fix some canonical process, consisting of moves , and reaching the final arrangement . Consider any sample process starting with the same initial arrangement and proceeding as long as possible; clearly, it contains at least one move. We need to show that this process stops at .
Let move consist in replacing two copies of with and . If move does the same, we may apply the induction hypothesis to the arrangement appearing after . Otherwise, the canonical process should still contain at least one move consisting in replacing , because the initial arrangement contains at least two copies of , while the final one contains at most one such.
Let be the first such move. Since the copies of are indistinguishable and no other copy of disappeared before in the canonical process, the moves in this process can be permuted as , without affecting the final arrangement. Now it suffices to perform the move and apply the induction hypothesis as above.
Claim 2. Consider any process starting from the empty board, which involved exactly moves of type (ii) and led to a final arrangement where all the numbers are distinct. Assume that one starts with the board containing zeroes (as if moves of type (ii) were made in the beginning), applying type (i) moves in an arbitrary way. Then this process will reach the same final arrangement.
Proof. Starting with the board with zeros, one may indeed model the first process mentioned in the statement of the claim, omitting the type (ii) moves. This way, one reaches the same final arrangement. Now, Claim 1 yields that this final arrangement will be obtained when type (i) moves are applied arbitrarily.
Claim 2 allows now to reformulate the problem statement as follows: There exists an integer such that, starting from zeroes, one may apply type (i) moves indefinitely.
In order to prove this, we start with an obvious induction on to show that if we start with zeros, then we can get simultaneously on the board, at some point, each of the numbers , with .
Suppose now that . Then, an appropriate use of separate groups of zeros allows us to get two copies of each of the numbers , with .
Define , and notice that after representing each of numbers , in the form we can get, using enough zeros, the numbers and the numbers .
From now on we can perform only moves of type (i). Indeed, if , the occurrence of the numbers and and the replacement leads to the occurrence of the numbers and .