Let $a_1, a_2, \ldots, a_{2023}$ be nonnegative real numbers such that $a_1 + a_2 + \ldots + a_{2023} = 100$. Let $A = \left \{ (i,j) \mid 1 \leqslant i \leqslant j \leqslant 2023, \, a_ia_j \geqslant 1 \right\}$. Prove that $|A| \leqslant 5050$ and determine when the equality holds. Proposed by Yunhao Fu
Problem
Source: 2024 China MO, Day 2, Problem 4
Tags: algebra, inequalities proposed
29.11.2023 09:25
Solution at the contest: WLOG let $a_1 \ge a_2 \ldots \ge a_{2023}$. Furthermore, let $a_1 \ge a_2 \ge \ldots \ge a_m \ge1 > a_{m+1} \ge \ldots \ge a_{2023}$. Obviosly $m \le 100$. Case 1: ${m}$ is even. Let $m=2k$, where $k \le 50$. Obviously all $a_ia_j$ with $1 \le i \le j \le 2k$ meets the condition and all $2k+1 \le i \le j \le 2023$ fails. $$\sum_{1 \le i \le k, k+1 \le j \le 2023}a_ia_j=\sum_{i=1}^k a_i \sum_{j=k+1}^{2023} a_j \le \frac{1}{4}( \sum_{i=1}^{2023} a_i)^2=2500$$This means that $|\left \{ (i,j) \mid 1 \le i \le k < j \le 2023, \, a_ia_j \geqslant 1 \right\}| \le 2500$ since $a_i$ are all nonnegative. Furthermore $|\left \{ (i,j) \mid 1 \le i \le k, 2k < j \le 2023, \, a_ia_j \geqslant 1 \right\}| \le 2500 - k^2$ By our assumption $a_j > a_i$ when $j>i$, so $|\left \{ (i,j) \mid k+1 \le i \le 2k, 2k < j \le 2023, \, a_ia_j \geqslant 1 \right\}| \le 2500 - k^2$. Adding up and we get $|A| \le \frac{2k(2k+1)}{2} + 2(2500 -k^2) +0=5000+k \le 5050$. Case 2: ${m}$ is odd. Let $m=2k+1$, where $k \le 49$. Obviously all $a_ia_j$ with $1 \le i \le j \le 2k+1$ meets the condition and all $2k+2 \le i \le j \le 2023$ fails. $$\sum_{1 \le i \le k+1, k+2 \le j \le 2023}a_ia_j=\sum_{i=1}^{k+1} a_i \sum_{j=k+2}^{2023} a_j \le \frac{1}{4}( \sum_{i=1}^{2023} a_i)^2=2500$$This means that $|\left \{ (i,j) \mid 1 \le i \le k+1 < j \le 2023, \, a_ia_j \geqslant 1 \right\}| \le 2500$ since $a_i$ are all nonnegative. Furthermore $|\left \{ (i,j) \mid 1 \le i \le k+1, 2k+2 < j \le 2023, \, a_ia_j \geqslant 1 \right\}| \le 2500 - k(k+1)$ By our assumption $a_j > a_i$ when $j>i$, so $|\left \{ (i,j) \mid k+2 \le i \le 2k+1, 2k+1 < j \le 2023, \, a_ia_j \geqslant 1 \right\}| < 2500 - k(k+1)$(We can't achieve equality since $k+1>k$). Adding up and we get $|A| < \frac{(2k+1)(2k+2)}{2} + 2(2500 -k(k+1)) +0=5000+k+1 \le 5050$ Equality case is achieved if and only if $a_1… a_{2023}$ are 100 $1$s and 1923 $0$s.
29.11.2023 15:07
Let $n_i$ be the number of $a_j $'s such that $a_ia_j \ge 1$ ($j$ not equal to $i$) and let $m$ be the number of $a_i$ which are bigger than $1$. Note that $m\ge 100$ and $|A|=m+\frac{n_1+n_2+\dots +n_{2023}}{2}$ $a_i(a_1 + a_2 + \ldots + a_{2023})\ge n_i$ if $a_i\le 1$ and $a_i(a_1 + a_2 + \ldots + a_{2023})\ge n_i+1$ if $a_i\ge 1$ After adding all $2023$ such inequalities we will get $2|A|-m = m+n_1+n_2+\dots +n_{2023} \le (a_1 + a_2 + \ldots + a_{2023})^2=100^2$ which implies $|A| \le 5000+\frac{m}{2} \le5050$ Equality hold when $m=100$ that is $a_1=a_2= \dots a_{100}=1 $and rest are zero
29.11.2023 17:39
Didn't realise I wrote a fake proof until the afternoon. Anyway... WLOG $a_1\ge a_2\ge\cdots\ge a_r\ge 1>a_{r+1}\ge \cdots\ge a_{2023}$ and consider sets $S_k=\{j>k:a_ja_k\ge 1\}$. As $r\le 100$ we get \begin{align*}N=&\sum_{k=1}^{r}(1+|S_k|)\\\le&\sum_{k=1}^{r}(\dfrac12+\dfrac12a_k^2+\sum_{j>k}a_ja_k)\\=&\dfrac r2+(\sum_{k=1}^{r}a_k)\cdot(\sum_{k=1}^{2023}a_k)-\dfrac12(\sum_{k=1}^{r}a_k)^2\\\le&\dfrac r2+100(\sum_{k=1}^{r}a_k)-\dfrac12 (\sum_{k=1}^{r}a_k)^2\\\le& 50+5000=5050. \end{align*}
29.11.2023 21:30
$a_1^2+a_2^2+\ldots+a_{2023}^2+2\sum_{i<j}a_ia_j=10000$. Clearly, at most $100$ of the $a_i$ are at least $1$. If $n$ of the $a_i$ are at least $1$ and $S$ is the sum of the squares of the $a_i$, then the number of $i<j$ such that $a_ia_j\geq1$ is at most $\frac12(10000-S)\leq\frac12(10000-n)$, so $|A|\leq\frac12(10000-n)+n\leq5000+\frac12n\leq5050$. Equality holds if and only if $100$ of the $a_i$ are equal to $1$ and the rest are equal to $0$.
29.11.2023 22:10
02.12.2023 08:22
This problem is proposed by me The original problem is as follows Let $a_1, a_2, \ldots, a_m$ be nonnegative real numbers such that $a_1 + a_2 + \ldots + a_m = c$ .($c$ is nonnegative real) Let $A = \left \{ (i,j) \mid 1 \leqslant i \leqslant j \leqslant m, \, a_ia_j \geqslant 1 \right\}$. Find the maximum value of $|A|$.
19.01.2024 13:50
China MO 2024/4 wrote: Let $a_1, a_2, \ldots, a_{2023}$ be nonnegative real numbers such that $a_1 + a_2 + \ldots + a_{2023} = 100$. Let $A = \left \{ (i,j) \mid 1 \leqslant i \leqslant j \leqslant 2023, \, a_ia_j \geqslant 1 \right\}$. Prove that $|A| \leqslant 5050$ and determine when the equality holds. Solution: The equality is achieved iff $100$ of $a_i$ are $1$ while the others are $0$. $\sum a_i^2 + 2\sum a_ia_j = 10000$ Clearly atmost $100$ of the $a_i$ are at least $1$, let $\mathcal{N}$ denote the number of pairs of $a_ia_j \geq1$, $n$ denote the number of $a_i$ greater than $1$. $\mathcal{N} \leq \frac{10000-n}{2} \leq 5050$ hence we're done.
28.02.2024 12:57
We uploaded our solution https://calimath.org/pdf/CNO2023-4.pdf on youtube https://youtu.be/oq2lp7lb1WE.
28.02.2024 15:21
Cali.Math wrote: We uploaded our solution https://calimath.org/pdf/CNO2023-4.pdf on youtube https://youtu.be/oq2lp7lb1WE. May I ask, to change it from CNO to CMO?
03.03.2024 19:04
Reducted
17.06.2024 01:26
Note that $a_1^2+a_2^2+...+a_{2023}^2+2 \cdot \sum_{i<j} a_ia_j=(a_1+a_2+...+a_{2023})^2=10000$, now let $k$ the number of $a_{\ell}$'s greater than $1$, note that $k \le 100$ or else it would contradict non-negativity. Now the finish: $$|A| \le \sum_{(i,j) \in A} a_ia_j \le \frac{10000-k}{2}+k=\frac{10000+k}{2} \le 5050$$With equallity when there is 100 $a_{\ell}$'s equal to $1$ and the rest are $0$. Thus we are done
12.10.2024 16:16
Firstly in order to make a use of the condition $$a_1+a_2+\dots +a_{2023}=100$$Since we are trying to find terms of form $a_ia_j$, hence this motivates us to square the sum $(a_1+a_2+\dots +a_{2023})^2=a_1^2+a_2^2+\dots+a_{2023}^2+ 2\sum_{1 \leq i<j\leq 2023} a_ia_j=10000$. Now we have that the number of $a_i$ in which $a_i \geq 1$ is at most $100$. Hence we have that the number of terms $a_i^2\geq 1$ is at most $100$. While for terms $a_ia_j \geq 1$ is at most $\frac{1}{2}(10000-n)$ where $n$ is equal to the number of terms $a_i\geq 1$, hence \[|A|\leq \frac{1}{2}(10000-n)+n =\frac{1}{2}(10000+n) \leq 5050 \] Now for equality case, we let $a_1, a_2, \dots a_{100} =1 $ while all others equal $0$, we can see that this gives us $5050$, hence we are done.
07.12.2024 05:57
predictableprimes wrote: Let $n_i$ be the number of $a_j $'s such that $a_ia_j \ge 1$ ($j$ not equal to $i$) and let $m$ be the number of $a_i$ which are bigger than $1$. Note that $m\ge 100$ and $|A|=m+\frac{n_1+n_2+\dots +n_{2023}}{2}$ $a_i(a_1 + a_2 + \ldots + a_{2023})\ge n_i$ if $a_i\le 1$ and $a_i(a_1 + a_2 + \ldots + a_{2023})\ge n_i+1$ if $a_i\ge 1$ After adding all $2023$ such inequalities we will get $2|A|-m = m+n_1+n_2+\dots +n_{2023} \le (a_1 + a_2 + \ldots + a_{2023})^2=100^2$ which implies $|A| \le 5000+\frac{m}{2} \le5050$ Equality hold when $m=100$ that is $a_1=a_2= \dots a_{100}=1 $and rest are zero You claimed that m≥100 but in the last line you considered m≤100....I think you were a bit wrong there
13.01.2025 13:38