IMO shortlist 1995/N7 solution

36th IMO 1995 shortlist

Problem N7

Does there exist n > 1 such that the set of positive integers may be partitioned into n non-empty subsets so that if we take an arbitrary element from every set but one then their sum belongs to the remaining set?

Solution

Answer: no.

Obviously no partition is possible for n = 2. So assume n > 2. Let the partition be A₁ ∪ A₂ ∪ ... ∪ A_n. We show first that if a, b, c (not necessarily distinct) belong to the same subset then a + b and a + c must belong to the same subset.

So suppose a, b, c belong to A₁, a+b belongs to A₂ and a+c belongs to A₃. Take any elements a₄ in A₄, a₅ in A₅, ... , a_n in A_n. Then c + (a+b) + a₄ + ... + a_n must be in A₃. But it equals b + (a+c) + a₄ + ... + a_n which must be in A₂. Contradiction.

Suppose a+b belongs to A₁ and a+c belongs to A₃. As before take any a_i in A_i. Then b + a₃ + ... + a_n must be in A₂, so (b + a₃ + ... + a_n) + (a+c) + a₄ + ... + a_n = (a+b+c) + (a₃ + ... + a_n) + (a₄ + ... + a_n) must be in A₁. But c + a₃ + ... + a_n must be in A₂, so (a+b) + (c + a₃ + ... + a_n) + a₄ + ... + a_n = (a+b+c) + (a₃ + ... + a_n) + (a₄ + ... + a_n) must be in A₃. Contradiction. The only remaining possibility is that a+b and a+c belong to the same subset, as claimed.

Now take a_i in A_i. Put s = a₁ + ... + a_n. Without loss of generality s is in A₁. Put b_i = s - a_i. We can also write b_i as a sum of an element from each subset except A_i, so b_i must be in A_i. Now a_i + b_i = s, which is in A₁. Hence a_i + a_i = 2a_i is also in A₁ (by the preliminary result).

Now suppose 2m in any even positive integer. We have m in some A_i. Take the set b_j, where b_j = a_j except for b_i = m. The same argument shows that 2b₁, 2b₂, ... , 2b_n are all in the same subset. But if we take any j not equal to i, we already know that 2b_j = 2a_j is in A₁. So 2m must also be in A₁. In other words, all the even numbers are in A₁.

Consider a₁ + a₃ + ... + a_n. It is in A₂. Keep a₃, a₄, ... , a_n fixed and let a₁ run through all the even numbers. Then we see that all odd numbers greater than a₃ + ... + a_n must be in A₂. Similarly, by considering a₁ + a₂ + a₄ + ... + a_n, we see that all odd numbers greater than a₂ + a₄ + ... + a_n must be in A₃. Contradiction.

36th IMO shortlist 1995