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.

Comments

mamartens
3 years ago

Here I use the index $n$, starting at $n=0$, to label the sets.

First, prove that the set $\{1,2,...,669\}$ can be expressed as the union of disjoint sets such that each $a_n$, for $n = 0,1,..., 222$ contains three elements and that the sum of all the elements in each $a_n$ is the same.

Distributing the sum of the series equally over $223$ sets requires the sum of the elements of each set be equal to $\frac{670 * 669}{ 2 * 223} =1005$. This can be achieved using $$ a_n = (1+3n, 2+333+3n, 669-6n) $$ where it is understood that $669$ is either added or subtracted to keep the value of the elements within the range $[1,669]$. Examining $a_n$ for $n=111$ and $n=112$ explicitly gives $$ a_{n=111} = (334, 668, 3) $$ $$ a_{n=112} = (337, 2, 666) $$ and demonstrates that the wrap-around of the second and third elements conveniently coincide to leave the sum of the elements equal to $1005$. Modulo $3$ of the first, second, and third elements are $1,2,0$ respectively ensuring that no member of the set is used twice.

Now construct a collection of sets $b_n$ by adding $669$ to each value of $a_n$ and a collection of sets $c_n$ by adding $669$ to each element of $b_n$. The final answer is then $A_n = a_n \cup b_n \cup c_n$. As check, the sum of the elements of $A_n$ is equal to the sums of the elements of $a_n, b_n$, and $c_n$ which are $1005$, $1005 + 3 * 669$ and $1005 + 6 * 669$. The sum of the elements of $A_n$ is then $9036$ as expected.

Claudio
4 years 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.