Spring 2018, problem 57

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.


3 months ago

An obvious argument shows that the common value of the sum must be $9036$; because of $9036=36*251$, the mean value for each $A_i$ must be $1004$. Thus we can confine ourselves to split into 223 subset $B_j$ the numbers $\{-1003,-1002,...,0,...,1002,1003\}$; each $B_j$ containing nine elements whose mean value is 0. The goal will then be reached by choosing as elements of $A_j$ the elements of $B_j$ augmented by 1004.

In fact we split our 2007 number into 223 triplets and 669 couples, each subset having 0 as mean value; putting in each subset $B_i$ one triple and 3 couples we reach our goal.

More precisely, one of the triple will be $(-1003,0,1003)$; among the other ones, 111 are of the form $(-a,-b,a+b)$ with $a,b>0$; and 111 will be the opposite ones $(a,b,-a-b)$. Finally, each couple will be of the form $(-c,c)$.

Any programming language allow to write a trivial program showing that it is possible to build these subset using the 2007 numbers from -1003 to 1003; e.g we can build the triplets by using the greedy algorithm: for $a$ from 1 to 111 we search for the biggest $b$ such that $b$ and $b+a$ are not yet used; the remaining unused $c$ will give the couples.

Post an answer:

To post an answer, please log in