2023 CMO Problems/Problem 4

Problem

Let non-negative real numbers $a_1, a_2, \ldots, a_{2023}$ satisfy \[a_1+a_2+\cdots+a_{2023}=100\]

Define $N$ as the number of elements in the set \[\left\{(i, j) \mid 1 \leq i \leq j \leq 2023, a_i a_j \geq 1\right\}\]

Prove that $N \leq 5050$ and provide necessary and sufficient conditions for the equality to hold.

Solution 1

Let $S=\{1,2, \ldots, 2023\}, B=\left\{i \in S \mid a_i \geq 13\right\}$, and $C=S \backslash B$. It is easy to see that $|B| \leq 100$. Since $\sum_{i=1}^{2023} a_i>1000$, there is a solution! \[|A| =\sum_{1 \leq i<j \leq 2023} 1\] \[=\sum_{1 \leq i<j \leq 2023} a_i a_j+\sum_{i \in B} 1\] \[=\sum_{1 \leq i<j \leq 2023}^{2023} a_i a_j+|B|\] \[=\left(\sum_{i=1}^{2023} a_i\right)^2-\sum_{i=1}^{2023} a_i^2+|B|\] \[=5000-\sum_{i=1}^{2023} a_i^2+|B|\] \[\sum a_i^2+2 a_i a_j\geq \sum a_i^2 \geq \sum_{i \in B} 1\]

Therefore, \[|A|=5000-|B|+1 \geq 5000+|B|-1\]

Given that $|B| \leq 100$, we have $|A| \leq 5050$.

Equality is attained when $a_i=0$ for all $i \notin B$ and $a_i=1$ for all $i \in B$. This is perfect. (Note the equality condition of the subsequent inequality. It is achieved when $a_i=0$ for all $i \notin B$ and $a_i=1$ for all $i \in B$, satisfying the subsequent inequality conditions.)

~zata2|szm


See Also

2023 CMO(CHINA) (ProblemsResources)
Preceded by
Problem 3
Followed by
Problem 5
1 2 3 4 5 6
All CMO(CHINA) Problems and Solutions