IMO 1995 SL N7

Origin: BLR | Category: Number Theory

Problem

Does there exist an integer n > 1 that satisfies the following condition? The set of positive integers can be partitioned into n nonempty subsets such that an arbitrary sum of n −1 integers, one taken from each of any n −1 of the subsets, lies in the remaining subset.

Solution

We shall show that there is no such n. Certainly, n = 2 does not work, so suppose n \geq3. Let a, b be distinct elements of A1, and c any integer greater than −a and −b. We claim that a + c, b + c belong to the same subsets. Suppose to the contrary that a+c \inA1 and b+c \inA2, and take arbitrary elements xi \inAi, i = 3, . . . , n. The number b + x3 + \cdot \cdot \cdot + xn is in A2, so that s = (a + c) + (b + x3 + \cdot \cdot \cdot + xn) + x4 + \cdot \cdot \cdot + xn must be in A3. On the other hand, a+x3 +\cdot \cdot \cdot+xn \inA2, so s = (a+x3 +\cdot \cdot \cdot+xn)+ (b + c) + x4 + \cdot \cdot \cdot + xn is in A1, a contradiction. Similarly, if a + c \inA2 and b + c \inA3, then s = a + (b + c) + x4 + \cdot \cdot \cdot + xn belongs to A2, but also s = b + (a + c) + x4 + \cdot \cdot \cdot + xn \inA3, which is impossible. For i = 1, . . . , n choose xi \inAi; set s = x1 +\cdot \cdot \cdot+xn and yi = s−xi. Then yi \inAi. By what has been proved above, 2xi = xi+xi belongs to the same subset as xi + yi = s does. It follows that all numbers 2xi, i = 1, . . . , n, are in the same subset. Since we can arbitrarily take xi from each set Ai, it follows that all even numbers belong to the same set, say A1. Similarly, 2xi + 1 = (xi + 1) + xi is in the subset to which (xi + 1) + yi = s + 1 belongs for all i = 1, . . . , n; hence all odd numbers greater than 1 are in the same subset, say A2. By the above considerations, 3 −2 = 1 \inA2 also. But then nothing remains in A3, . . . , An, a contradiction.