IMO 2012 Shortlist A2

Category: Algebra

Problem

Let Z and Q be the sets of integers and rationals respectively. a) Does there exist a partition of Z into three non-empty subsets A,B,C such that the sets A + B, B + C, C + A are disjoint? b) Does there exist a partition of Q into three non-empty subsets A,B,C such that the sets A + B, B + C, C + A are disjoint? Here X + Y denotes the set {x + y | x ∈ X,y ∈ Y }, for X,Y ⊆ Z and X,Y ⊆ Q. Solution 1. a) The residue classes modulo 3 yield such a partition: A = {3k | k ∈ Z}, B = {3k + 1 | k ∈ Z}, C = {3k + 2 | k ∈ Z}. b) The answer is no. Suppose that Q can be partitioned into non-empty subsets A,B,C as stated. Note that for all a ∈ A, b ∈ B, c ∈ C one has a + b − c ∈ C, b + c − a ∈ A, c + a − b ∈ B. (1) Indeed a+b−c / ∈ A as (A+B)∩(A+C) = ∅, and similarly a+b−c / ∈ B, hence a+b−c ∈ C. The other two relations follow by symmetry. Hence A+B ⊂ C+C, B+C ⊂ A+A, C+A ⊂ B+B. The opposite inclusions also hold. Let a,a′ ∈ A and b ∈ B, c ∈ C be arbitrary. By (1) a′

c − b ∈ B, and since a ∈ A, c ∈ C, we use (1) again to obtain a + a′ − b = a + (a′
c − b) − c ∈ C. So A + A ⊂ B + C and likewise B + B ⊂ C + A, C + C ⊂ A + B. In summary B + C = A + A, C + A = B + B, A + B = C + C. Furthermore suppose that 0 ∈ A without loss of generality. Then B = {0} + B ⊂ A + B and C = {0}+C ⊂ A+C. So, since B +C is disjoint with A+B and A+C, it is also disjoint with B and C. Hence B + C is contained in Z \ (B ∪ C) = A. Because B + C = A + A, we obtain A + A ⊂ A. On the other hand A = {0} + A ⊂ A + A, implying A = A + A = B + C. Therefore A+B +C = A+A+A = A, and now B +B = C +A and C +C = A+B yield B +B +B = A+B+C = A, C +C +C = A+B+C = A. In particular if r ∈ Q = A∪B ∪C is arbitrary then 3r ∈ A. However such a conclusion is impossible. Take any b ∈ B (B 6= ∅) and let r = b/3 ∈ Q. Then b = 3r ∈ A which is a contradiction. Solution 2. We prove that the example for Z from the first solution is unique, and then use this fact to solve part b). Let Z = A∪B ∪C be a partition of Z with A,B,C 6= ∅ and A+B, B +C, C +A disjoint. We need the relations (1) which clearly hold for Z. Fix two consecutive integers from different sets, say b ∈ B and c = b+1 ∈ C. For every a ∈ A we have, in view of (1), a−1 = a+b−c ∈ C and a + 1 = a + c − b ∈ B. So every a ∈ A is preceded by a number from C and followed by a number from B. In particular there are pairs of the form c,c + 1 with c ∈ C, c + 1 ∈ A. For such a pair and any b ∈ B analogous reasoning shows that each b ∈ B is preceded by a number from A and followed by a number from C. There are also pairs b,b−1 with b ∈ B, b−1 ∈ A. We use them in a similar way to prove that each c ∈ C is preceded by a number from B and followed by a number from A. By putting the observations together we infer that A,B,C are the three congruence classes modulo 3. Observe that all multiples of 3 are in the set of the partition that contains 0.11 Now we turn to part b). Suppose that there is a partition of Q with the given properties. Choose three rationals ri = pi/qi from the three sets A,B,C, i = 1,2,3, and set N = 3q1q2q3. Let S ⊂ Q be the set of fractions with denominators N (irreducible or not). It is obtained through multiplication of every integer by the constant 1/N, hence closed under sums and differences. Moreover, if we identify each k ∈ Z with k/N ∈ S then S is essentially the set Z with respect to addition. The numbers ri belong to S because r1 = 3p1q2q3 N , r2 = 3p2q3q1 N , r3 = 3p3q1q2 N . The partition Q = A∪B ∪C of Q induces a partition S = A′ ∪B′ ∪C′ of S, with A′ = A∩S, B′ = B ∩ S, C′ = C ∩ S. Clearly A′
B′ , B′
C′ , C′
A′ are disjoint, so this partition has the properties we consider. By the uniqueness of the example for Z the sets A′ ,B′ ,C′ are the congruence classes mod- ulo 3, multiplied by 1/N. Also all multiples of 3/N are in the same set, A′ ,B′ or C′ . This holds for r1,r2,r3 in particular as they are all multiples of 3/N. However r1,r2,r3 are in different sets A′ ,B′ ,C′ since they were chosen from different sets A,B,C. The contradiction ends the proof. Comment. The uniqueness of the example for Z can also be deduced from the argument in the first solution.12