Prove that the set $\{1, 2, \cdots, 2007\}$ can be expressed as the union of disjoint subsets $A_i$ for $i=1,2,\cdots, 223$ such that each $A_i$ contains nine elements and the sum of all the elements in each $A_i$ is the same.
Problem
Source: 2008 Philippine Mathematical Olympiad Problem 1
Tags: combinatorics
tenniskidperson3
07.05.2014 01:19
Note that they're disjoint. You have found the correct sum, but you need to show that there are $223$ mutually disjoint subsets with that sum.
sengupta_arka123
21.04.2015 19:35
Can anyone post a complete solution?
JayJuly
22.04.2015 05:47
Clearly the value of the sum of each $A_i$ must be equal to $\frac{1 + 2 + \cdots + 2007}{223} = 9036$. For $k = 0, 1, \cdots, 111, j = 1, 2, \cdots, 111$ let: $A_{2k + 1} = \{2k + 1, 335 - k, 669 - k, 2k + 670, 1004 - k, 1338 - k, 2k + 1339, 1673 - k, 2007 - k\}$, $A_{2j} = \{2j, 447 - j, 558 - j, 2j + 669, 1116 - j, 1227 - j, 2j + 1338, 1785 - j, 1896 - j\}$. With these definitions, summing the elements of any $A_i$ will yield $9036$ and no two $A_i$ contain a common element. QED. As for how I got this solution, I did casework for $[9]$ with $i = 1, 2, 3$ and $[15]$ with $i = 1, 2, 3, 4, 5$. After, I was able to form a solution for $[669]$ with $i = 1, 2, \cdots, 223$ using the pattern and then just added $669$ to each block of $3$ terms to get the desired result.