IMO 1989 SL 22

Origin: PHI

Problem

Prove that the set {1, 2, . . ., 1989} can be expressed as the disjoint union of 17 subsets A1, A2, . . . , A17 such that: (i) each Ai contains the same number of elements; (ii) the sum of all elements of each Ai is the same for i = 1, 2, . . . , 17.

Solution

The statement remains valid if 17 is replaced by any divisor k of 1989 = 32\cdot 13 \cdot17, 1 < k < 1989, so let k be one such divisor. The set {1, 2, . . ., 1989} can be partitioned as {1, 2, . . ., 3k} \cup%L j=1{(2j + 1)k + 1, (2j + 1)k + 2, . . . , (2j + 1)k + 2k} = X \cupY1 \cup\cdot \cdot \cdot \cupYL, where L = (1989 −3k)/2k. The required statement will be an obvious consequence of the following two claims. Claim 1. The set X = {1, 2, . . ., 3k} can be partitioned into k disjoint subsets, each having 3 elements and the same sum. Proof. Since k is odd, let t = k −1/2 and X = {1, 2, . . ., 6t + 3}. For l = 1, 2, . . . , t, define X2l−1 = {l, 3t + 1 + l, 6t + 5 −2l}, X2l = {t + 1 + l, 2t + 1 + l, 6t + 4 −2l} X2t+1 = Xk = {t + 1, 4t + 2, 4t + 3}. It is easily seen that these three subsets are disjoint and that the sum of elements in each set is 9t + 6. Claim 2. Each Yj = {(2j +1)k +1, . . . , (2j +1)k +2k} can be partitioned into k disjoint subsets, each having 2 elements and the same sum. Proof. The obvious partitioning works: Yj = {(2j+1)k+1, (2j+1)k+2k}\cup\cdot \cdot \cdot\cup{(2j+1)k+k, (2j+1)k+(k+1)}.