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$.
 A: 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$
