Maths Olympiad Prep

Library / /177 of 397

Combinatorics Difficulty 5.7 AIME, harder Prove it Taiwan

Let aa and bb 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 aa and the number in the other cell by bb.
(ii) If no pair of identical numbers can be found on the board, then we fill two empty cells each with a 00.
Prove that: no matter what, after some operation, only operation (i) can be performed from then on.

Solution

Without loss of generality assume gcd(a,b)=1\gcd(a, b) = 1, since we can simply divide aa and bb both by gcd(a,b)\gcd(a, b). Also, without loss of generality assume b>ab > a.

1. First, suppose that after several operations (i) and NN operations (ii), we are forced to perform operation (ii) once again. For all integers kk, let fN(k)f_N(k) denote the total number of times kk has appeared on the board so far. Clearly fN(0)=2Nf_N(0) = 2N, and fN(k)=0f_N(k) = 0 for all k<0k < 0.

Note that for all kk, since we are forced to perform (ii) in this round, this means that there is currently at most one kak - a on the board; and if other kak - a's appeared in previous rounds, this means there were once two kak-a's, one of which was increased to kk in some previous round. The same holds for kbk - b. The above observation tells us that we have the following relation:
fN(k)=[fN(ka)2]+[fN(kb)2].(1) f_N(k) = \left[ \frac{f_N(k-a)}{2} \right] + \left[ \frac{f_N(k-b)}{2} \right]. \qquad (1)

2. Since gcd(a,b)=1\gcd(a, b) = 1, every positive integer x>ababx > ab - a - b can be expressed as x=as+btx = as + bt, where s,ts, t are nonnegative integers. We now prove:

Lemma 1. For all x=as+btx = as + bt, we have
fN(x)>fN(0)2s+t2. f_N(x) > \frac{f_N(0)}{2^{s+t}} - 2.

Proof. We induct on s+ts+t. The case s+t=0s+t=0 is clear. Suppose the lemma holds when s+t=vs+t=v; then when s+t=v+1s+t=v+1, note that at least one of ss and tt is positive, and without loss of generality assume s>0s>0. Then by (1) and the induction hypothesis, we have
fN(x)=fN(sa+tb)[fN((s1)a+tb)2][12(fN(0)2v2)]>fN(0)2v+12, \begin{aligned} f_N(x) &= f_N(sa + tb) \ge \left[ \frac{f_N((s-1)a + tb)}{2} \right] \\ &\ge \left[ \frac{1}{2} \left( \frac{f_N(0)}{2^v} - 2 \right) \right] > \frac{f_N(0)}{2^{v+1}} - 2, \end{aligned}
which proves the lemma.

3. Now, suppose that we perform operation (ii) infinitely many times, that is, NN in part 1 can be any positive integer. Take n=ababn = ab-a-b, and take N=2a+b+1N = 2^{a+b+1}. Note that n+1,n+2,,n+bn+1, n+2, \dots, n+b can all be expressed as sa+tbsa+tb, where 0sb0 \le s \le b and 0ta0 \le t \le a. Hence by Lemma 1, we have
fN(n+k)>fN(0)2s+t2=2N2s+t2=2a+b+22s+t22a+b+22a+b2=2. f_N(n+k) > \frac{f_N(0)}{2^{s+t}} - 2 = \frac{2N}{2^{s+t}} - 2 = \frac{2^{a+b+2}}{2^{s+t}} - 2 \ge \frac{2^{a+b+2}}{2^{a+b}} - 2 = 2.
This shows that fN(n+1),,fN(n+k)f_N(n+1), \dots, f_N(n+k) are all greater than or equal to 2, and hence by (1) and mathematical induction, we know that fN(x)2f_N(x) \ge 2 holds for all x>nx > n. But this means that after finitely many operations, the board would have infinitely many numbers on it, which is impossible, a contradiction!

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 translated into English from zh; metadata (topic, difficulty) added by this project.