Prove that the set {1, 2, ... , 1989} can be expressed as the disjoint union of subsets A1, A2, ... , A117 in such a way that each Ai contains 17 elements and the sum of the elements in each Ai is the same.
Solution
We construct 116 sets of three numbers. Each set sums to 3 x 995 = 2985. The 348 numbers involved form 174 pairs {r, 1990 - r}. At this point we are essentially done. We take a 117th set which has one {r, 1990 - r} pair and 995. The original 1989 numbers comprise 995 and 994 {r, 1990 - r} pairs. We have used up 995 and 175 pairs, leaving just 819 pairs. We now add 7 pairs to each of our 117 sets, bringing the total of each set up to 2985 + 7.1990 = 1990 x 17/2.
It remains to exhibit the 116 sets. There are many possibilities. We start with:
301, 801, 1883 and the "complementary" set 1990 - 301 = 1689, 1990 - 801 = 1189, 1990 - 1883 = 107. We then add one to each of the first two numbers to get:
302, 802, 1881 and 1688, 1188, 109, and so on:
303, 803, 1879 and 1687, 1187, 111,
...
358, 858, 1769 and 1632, 1132, 221.
We can immediately see that these triples are all disjoint. So the construction is complete.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
16 Nov 1998