Maths Olympiad Prep

Library / /303 of 383

Combinatorics Difficulty 8.9 Shortlist Prove it IMO

Let aa and bb 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 aa and the other by bb.
(ii) If no such pair exists, we write down two times the number 00.
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 gcd(a,b)=1\gcd(a, b)=1; otherwise we work in the same way with multiples of d=gcd(a,b)d=\gcd(a, b).
Suppose that after NN moves of type (ii) and some moves of type (i) we have to add two new zeros. For each integer kk, denote by f(k)f(k) the number of times that the number kk appeared on the board up to this moment. Then f(0)=2Nf(0)=2N and f(k)=0f(k)=0 for k<0k<0. Since the board contains at most one kak-a, every second occurrence of kak-a on the board produced, at some moment, an occurrence of kk; the same stands for kbk-b. Therefore,
f(k)=f(ka)2+f(kb)2,(1) f(k)=\left\lfloor\frac{f(k-a)}{2}\right\rfloor+\left\lfloor\frac{f(k-b)}{2}\right\rfloor, \tag{1}
yielding
f(k)f(ka)+f(kb)21.(2) f(k) \geqslant \frac{f(k-a)+f(k-b)}{2}-1 . \tag{2}
Since gcd(a,b)=1\gcd(a, b)=1, every integer x>ababx>ab-a-b is expressible in the form x=sa+tbx=sa+tb, with integer s,t0s, t \geqslant 0.
We will prove by induction on s+ts+t that if x=sa+btx=sa+bt, with s,ts, t nonnegative integers, then
f(x)>f(0)2s+t2(3) f(x)>\frac{f(0)}{2^{s+t}}-2 \tag{3}
The base case s+t=0s+t=0 is trivial. Assume now that (3) is true for s+t=vs+t=v. Then, if s+t=v+1s+t=v+1 and x=sa+tbx=sa+tb, at least one of the numbers ss and tt—say ss—is positive, hence by (2),
f(x)=f(sa+tb)f((s1)a+tb)21>12(f(0)2s+t12)1=f(0)2s+t2. f(x)=f(sa+tb) \geqslant \frac{f((s-1)a+tb)}{2}-1>\frac{1}{2}\left(\frac{f(0)}{2^{s+t-1}}-2\right)-1=\frac{f(0)}{2^{s+t}}-2 .
Assume now that we must perform moves of type (ii) ad infinitum. Take n=ababn=ab-a-b and suppose b>ab>a. Since each of the numbers n+1,n+2,,n+bn+1, n+2, \ldots, n+b can be expressed in the form sa+tbsa+tb, with 0sb0 \leqslant s \leqslant b and 0ta0 \leqslant t \leqslant a, after moves of type (ii) have been performed 2a+b+12^{a+b+1} times and we have to add a new pair of zeros, each f(n+k),k=1,2,,bf(n+k), k=1,2, \ldots, b, is at least 22. In this case (1) yields inductively f(n+k)2f(n+k) \geqslant 2 for all k1k \geqslant 1. But this is absurd: after a finite number of moves, ff 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 kk 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 kk; the base case k=0k=0 is trivial, since no moves are possible. Assume now that k1k \geqslant 1. Fix some canonical process, consisting of kk moves M1,M2,,MkM_{1}, M_{2}, \ldots, M_{k}, and reaching the final arrangement AA. Consider any sample process m1,m2,m_{1}, m_{2}, \ldots 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 AA.
Let move m1m_{1} consist in replacing two copies of xx with x+ax+a and x+bx+b. If move M1M_{1} does the same, we may apply the induction hypothesis to the arrangement appearing after m1m_{1}. Otherwise, the canonical process should still contain at least one move consisting in replacing (x,x)(x+a,x+b)(x, x) \mapsto (x+a, x+b), because the initial arrangement contains at least two copies of xx, while the final one contains at most one such.
Let MiM_{i} be the first such move. Since the copies of xx are indistinguishable and no other copy of xx disappeared before MiM_{i} in the canonical process, the moves in this process can be permuted as Mi,M1,,Mi1,Mi+1,,MkM_{i}, M_{1}, \ldots, M_{i-1}, M_{i+1}, \ldots, M_{k}, without affecting the final arrangement. Now it suffices to perform the move m1=Mim_{1}=M_{i} and apply the induction hypothesis as above.

Claim 2. Consider any process starting from the empty board, which involved exactly nn moves of type (ii) and led to a final arrangement where all the numbers are distinct. Assume that one starts with the board containing 2n2n zeroes (as if nn 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 2n2n 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 nn such that, starting from 2n2n zeroes, one may apply type (i) moves indefinitely.

In order to prove this, we start with an obvious induction on s+t=k1s+t=k \geqslant 1 to show that if we start with 2s+t2^{s+t} zeros, then we can get simultaneously on the board, at some point, each of the numbers sa+tbsa+tb, with s+t=ks+t=k.

Suppose now that a<ba<b. Then, an appropriate use of separate groups of zeros allows us to get two copies of each of the numbers sa+tbsa+tb, with 1s,tb1 \leqslant s, t \leqslant b.

Define N=ababN=ab-a-b, and notice that after representing each of numbers N+k,1kbN+k, 1 \leqslant k \leqslant b, in the form sa+tb,1s,tbsa+tb, 1 \leqslant s, t \leqslant b we can get, using enough zeros, the numbers N+1,N+2,,N+aN+1, N+2, \ldots, N+a and the numbers N+1,N+2,,N+bN+1, N+2, \ldots, N+b.

From now on we can perform only moves of type (i). Indeed, if nNn \geqslant N, the occurrence of the numbers n+1,n+2,,n+an+1, n+2, \ldots, n+a and n+1,n+2,,n+bn+1, n+2, \ldots, n+b and the replacement (n+1,n+1)(n+b+1,n+a+1)(n+1, n+1) \mapsto (n+b+1, n+a+1) leads to the occurrence of the numbers n+2,n+3,,n+a+1n+2, n+3, \ldots, n+a+1 and n+2,n+3,,n+b+1n+2, n+3, \ldots, n+b+1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.