# IMO problem number theory

Determine the greatest positive integer $k$ that satisfies the following property.
The set of positive integers can be partitioned into $k$ subsets $A_1,A_2,A_3,\ldots,A_k$ such that for all integers $n\ge 15$ and all $i\in\{1,2,\ldots,k\}$ there exist two distinct elements of $A_i$ such that their sum is $n$.

The greatest such number is $3$

First we are going to show that there exists a construction for $k = 3$ and then we are going to prove that $k \not\ge 4$

## PART 1

We build the 3 sets $A_1,A_2\ and\ A_3$ as:

\begin{align} \\&A_1 = \{1,2,3\} \cup \{3m\ |\ m \ge\ 4\} \\&A_2 = \{4,5,6\} \cup \{3m - 1\ |\ m \ge\ 4\} \\&A_3 = \{7,8,9\} \cup \{3m - 2\ |\ m \ge\ 4\} \end{align}

Here we easily see that,

• all $n\ge13$ can be represented as the sum of two unique elements of $A_1$
• all $n\ge15$ can be represented as the sum of two unique elements of $A_2$
• all $n\ge17$ can be represented as the sum of two unique elements of $A_3$

So we are only left to see that $15\ and\ 16$ can be represented as the sum of two distinct elements of $A_3$ which is given by:

$$\\15 = 7+8 \\16 = 7+9$$

## PART 2

Here we prove that $k \not\ge 4$

Let us assume that such a construction exists for $k \ge 4$. So let the sets $A_1,A_2,A_3...A_k$ satisfy the condition for $k \ge 4$

If $A_1,A_2,A_3...A_k$ satisfy the conditions, so does $A_1,A_2,A_3,A_4 \cup A_5 \cup A_6 \cup...\cup A_k$

Thus we assume that $k = 4$

$\therefore$ we assume the sets to be $A_1,A_2,A_3\ and\ A_4$

Now, we construct sets $B_1,B_2,B_3\ and\ B_4$ such that $B_i = A_i \cap \{1,2,3...,23\}$

Then $\forall i \in {1,2,3,4}$ each of the $10$ numbers $15,16,17...,24$ can be represented as the sum of two distinct numbers in $B_i$

$\therefore$ we must have $n = |B_i|$ such that $\binom{n}{2} \ge 10$

$\therefore\ |B_i| \ge 5\ \forall i \in \{1,2,3,4\}$ as $\binom{5}{2} = 10$

But we have $|B_1| + |B_2| + |B_3| + |B_4| = 23$ as we have done intersection with ${1,2,3,...23}$ and $B_1 \cap B_3 \cap B_3 \cap B_4 = \phi$

$\therefore \exists\ j \in \{1,2,3,4\}$ such that $|B_j| = 5$

Now let $B_j = \{x_1,x_2,x_3,x_4,x_5\}$

Now, the sums of two distinct elements of $A_j$ representing the numbers $15, 16, . . . , 24$ must exactly be equal to all the pairwise sums of the elements of $B_j$

Let the pairwise sum of all elements of $B_j$ be equal to $S$

$\therefore S = 4(x_1 + x_2 + x_3 + x_4 + x_5)$

Again, $S = 15 + 16 + 17 ... 24 = 195$

which gives $4(x_1 + x_2 + x_3 + x_4 + x_5) = 195$ which clearly is impossible.

Thus we have proved that $k \not \ge 4$

Thus, the anser is $k =3$

• This looks good to me! (Except for that word "unique" in part 2, which doesn't look right.) – TonyK Feb 22 '15 at 11:58
• Well the sum has to be of two unique numbers as we have assumed that to be true for all A_i and B_i is just a subset. – Crazy-Fool Feb 22 '15 at 12:00