66th Czech and Slovak Mathematical Olympiad

We first exclude small values of $n$. The three subsets have to have in total at least $1+2+3=6$ elements, hence $n\ge 6$. For $n=6$, the smallest subset (in size) contains a single number and its sum is therefore at most $6$. The sum of the remaining numbers is at least $15$, hence the sum of at least one of the two remaining subsets is at least $8$, a contradiction. Similarly we exclude $n=7$ and $n=8$ where, again, the smallest subset contains a single number. For $n=9$ the subsets $\{9,8\}$, $\{7,6,3\}$, $\{5,4,2,1\}$ satisfy the conditions. For $n=10$, the smallest subset contains at most $2$ numbers and its sum is therefore at most $19$. The sum of the remaining numbers is at least $36$ and we reach contradiction as above. Similarly we exclude $n=11$. Now we describe how to create the subsets for any $n\ge 12$. Let $n=3k+r$, $k\ge 4$, $r\in \{0,1,2\}$. We fix the sizes of the subsets to $k-1$, $k$, $k+r+1$ and define the subsets as follows: Set $M_1$ consists of $k-1$ largest numbers from $\{1,2,\dots ,n\}$, that is numbers $n-k+2,\dots ,n$. Set $M_2$ consists of the $k$ next largest numbers (that is, numbers $n-2k+2,\dots ,n-k+1$). The remaining numbers $1,\dots ,k+r+1$ form the subset $M_3$. We aim to show that $M_1$ has larger sum than $M_2$. Since all the numbers from $M_1$ are greater than all the numbers from $M_2$, and $M_2$ has just one more element, it suffices to show that the sum of the three largest numbers of $M_1$ is greater than the sum of the four smallest numbers of $M_2$. Such three numbers always exist ($k\ge 4$).

and the desired inequality $n+(n-1)+(n-2)>(n-2k+2)+(n-2k+3)+(n-2k+4)+(n-2k+5)$ is equivalent to $8k-n>17$ which, after plugging in $n=3k+r$ rewrites as $5k>17+r$. This is true as $5k\ge 20$ and $17+r\le 19$. Similarly, we show that $M_2$ has larger sum than $M_3$, which has $r+1$ more elements than $M_2$: Two largest numbers of $M_2$ have larger sum than $r+3$ smallest numbers of $M_3$ as $(n-k+1)+(n-k)=2(3k+r-k)+1=4k+2r+1\ge 17>15=1+2+3+4+5$. The answer is all $n\ge 12$ together with $n=9$.