IMO 1990 SL 15

Origin: MEX

Problem

Determine for which positive integers k the set X = {1990, 1990 + 1, 1990 + 2, . . . , 1990 + k} can be partitioned into two disjoint subsets A and B such that the sum of the elements of A is equal to the sum of the elements of B.

Solution

Let S(Z) denote the sum of all the elements of a set Z. We have S(X) = (k+1)\cdot1990+ k(k+1) . To partition the set into two parts with equal sums, S(X) must be even and hence k(k+1) must be even. Hence k is of the form 4r or 4r + 3, where r is an integer. For k = 4r + 3 we can partition X into consecutive fourtuplets {1990 + 4l, 1990 + 4l + 1, 1990 + 4l + 2, 1990 + 4l + 3} for 0 \leql \leqr and put 1990 + 4l, 1990 + 4l + 3 \inA and 1990 + 4l + 1, 1990 + 4l + 2 \inB for all l. This would give us S(A) = S(B) = (3980 + 4r + 3)(r + 1). For k = 4r the numbers of elements in A and B must differ. Let us assume without loss of generality |A| < |B|. Then S(A) \leq(1990+2r+1)+(1990+ 2r+2)+\cdot \cdot \cdot+(1990+4r) and S(B) \geq1990+1991+\cdot \cdot \cdot+(1990+2r). Plug- ging these inequalities into the condition S(A) = S(B) gives us r \geq23 and consequently k \geq92. We note that B = {1990, 1991, . . ., 2034, 2052, 2082} and A = {2035, 2036, . . ., 2051, 2053, . . ., 2081} is a partition for k = 92 that satisfies S(A) = S(B). To construct a partition out of higher k = 4r we use the k = 92 partition for the first 93 elements and construct for the remaining elements as was done for k = 4r + 3. Hence we can construct a partition exactly for the integers k of the form k = 4r + 3, r \geq0, and k = 4r, r \geq23.