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

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

Page

Toolbox

Search

2023 CMO Problems/Problem 4

Problem

Solution 1

See Also