Let $k \geqslant 1$ be an integer. Find the smallest integer $N$ for which there exist $2 k+1$ distinct integers $a_{1}, \ldots, a_{2 k+1} \geqslant 1$ satisfying:

- The sum of the $a_{i}$ is at least $N$.

- The sum of any $k$ distinct integers chosen from the $a_{i}$ is always less than or equal to $\frac{N}{2}$.

## Solved by Gaëtan Dautzenberg and Georges Tézé
solved by Gaëtan Dautzenberg and Georges Tézé

Let $N$ be an integer such that there exist $2 k+1$ distinct integers $a_{1}, \ldots, a_{2 k+1} \geqslant 1$ satisfying the statement. Without loss of generality, we can assume that $a_{1} \leqslant \ldots \leqslant a_{2 k+1}$. We then have $a_{1}+\cdots+a_{2 k+1} \geqslant N$ and $a_{k+2}+\cdots+a_{2 k+1} \leqslant \frac{N}{2}$. Therefore, we deduce that:

$$
a_{k+2}+\cdots+a_{2 k+1} \leqslant \frac{N}{2} \leqslant a_{1}+\cdots+a_{k+1}
$$

We also have that if $1 \leqslant i \leqslant 2 k$, then $a_{i+1} \geqslant a_{i}+1$ by monotonicity and since the $\left(a_{i}\right)$ are integers and distinct. In particular, $a_{n+m} \geqslant a_{n}+m$ if $1 \leqslant n+m \leqslant 2 k+1$. In particular,

$$
a_{2}+\cdots+a_{k+1}+k^{2} \leqslant a_{k+2}+\cdots+a_{2 k+1}
$$

This inequality, coupled with the previous one, implies that $a_{1} \geqslant k^{2}$. We thus have that

$$
\frac{N}{2} \geqslant a_{k+1}+\cdots+a_{2 k+1} \geqslant k^{2}+k+2+\cdots+k^{2}+2 k \geqslant k^{3}+k^{2}+\frac{k(k+1)}{2}
$$

Hence, $N \geqslant 2 k^{3}+3 k^{2}+k$.

Conversely, let's show that $2 k^{3}+3 k^{2}+k$ is indeed the minimal value of $N$. Take $a_{i}=k^{2}+i-1$ for $i$ between 1 and $2 k+1$. The sum of the $a_{i}$ is $k^{2}(2 k+1)+\frac{2 k(2 k+1)}{2}=2 k^{3}+3 k^{2}+k$ and the largest sum that can be formed with $k a_{i}$ is, by monotonicity, $a_{k+2}+\cdots+a_{2 k+1}=$ $k^{3}+k^{2}+(1+\cdots+k)=\frac{2 k^{3}+2 k^{2}+k(k+1)}{2}=\frac{N}{2}$. Thus, the sequence satisfies the statement, so $N=$ $2 k^{3}+3 k^{2}+k$ is indeed the minimal value.