IMO 1993 SL 9

Origin: IND

Problem

(a) Show that the set Q+ of all positive rational numbers can be par- titioned into three disjoint subsets A, B, C satisfying the following conditions: BA = B, B2 = C, BC = A, where HK stands for the set {hk | h \inH, k \inK} for any two subsets H, K of Q+ and H2 stands for HH. (b) Show that all positive rational cubes are in A for such a partition of Q+. (c) Find such a partition Q+ = A \cupB \cupC with the property that for no positive integer n \leq34 are both n and n + 1 in A; that is, min{n \inN | n \inA, n + 1 \inA} > 34.

Solution

We shall first complete the “multiplication table” for the sets A, B, C. It is clear that this multiplication is commutative and associative, so that we have the following relations: AC = (AB)B = BB = C; A2 = AA = (AB)C = BC = A; C2 = CC = B(BC) = BA = B. (a) Now put 1 in A and distribute the primes arbitrarily in A, B, C. This distribution uniquely determines the partition of Q+ with the stated property. Indeed, if an arbitrary rational number x = p\alpha1 1 \cdot \cdot \cdot p\alphak k q\beta1 1 \cdot \cdot \cdot q\betal l r\gamma1 1 \cdot \cdot \cdot r\gammam m is given, where pi \inA, qi \inB, ri \inC are primes, it is easy to see that x belongs to A, B, or C according as \beta1 + \cdot \cdot \cdot + \betal + 2\gamma1 + \cdot \cdot \cdot + 2\gammam is congruent to 0, 1, or 2 (mod 3). (b) In every such partition, cubes all belong to A. In fact, A3 = A2A = AA = A, B3 = B2B = CB = A, C3 = C2C = BC = A. (c) By (b) we have 1, 8, 27 \inA. Then 2 ̸\inA, and since the problem is symmetric with respect to B, C, we can assume 2 \inB and conse- quently 4 \inC. Also 7 ̸\inA, and also 7 ̸\inB (otherwise, 28 = 4 \cdot 7 \inA and 27 \inA), so 7 \inC, 14 \inA, 28 \inB. Further, we see that 3 ̸\inA (since otherwise 9 \inA and 8 \inA). Put 3 in C. Then 5 ̸\inB (otherwise 15 \inA and 14 \inA), so let 5 \inC too. Consequently 6, 10 \inA. Also 13 ̸\inA, and 13 ̸\inC because 26 ̸\inA, so 13 \inB. Now it is easy to distribute the remaining primes 11, 17, 19, 23, 29, 31: one possibility is A = {1, 6, 8, 10, 14, 19, 23, 27, 29, 31, 33, . . .}, C = {3, 4, 5, 7, 18, 22, 24, 26, 30, 32, 34, . . .}, B = {2, 9, 11, 12, 13, 15, 16, 17, 20, 21, 25, 28, 35, . . .}. Remark. It can be proved that min{n \inN | n \inA, n + 1 \inA} \leq77.