Pairs $(j,k)$ for which $a_j+\frac{a_k^2}4\ge\frac1{2022}$

algebra-precalculuscontest-mathinequality

Let $\sum\limits_{i=1}^{2023}a_i=1$, and $a_i\ge0$, $1\le i\le n$. How many ordered pairs $(j,k)$ are there at most, for which $a_j+\frac{a_k^2}4\ge\frac1{2022}$?

I try to find the construction first. I can think of two directions.

The first, the values of (most of) all $a_i$s are equal. Solving the equation $x+\frac{x^2}4=\frac1{2022}$, we get a positive solution $\alpha\in\left[\frac1{2023},\frac1{2022}\right]$. So we take $a_1=a_2=\cdots=a_{2022}=\alpha$, $a_{2023}=1-2022\alpha$. Now the number of pairs desired should be $2022\times2021$.

The second, the $a_i$s can be grouped in two, one with big numbers, the other with small numbers. That is to say, we need to solve
\[m+\frac{n^2}4=\frac1{2022},~n+\frac{m^2}4=\frac1{2022},~m\ne n.\]
However, it has no real roots.

Anyway, I still have no idea how to prove.

Below is a solution!

We shall pick $2023$ pairs of $(i,j)$ for which $a_i+\frac{a^2_j}4<\frac1{2022}$.

Lemma. For $a$, $b\ge0$, $a+b\le\frac2{2023}$, we have $$a+\frac{b^2}4+b+\frac{a^2}4\le\frac{(a+b)^2}4+a+b\le\frac1{2023^2}+\frac2{2023}<\frac2{2022}.$$
Hence either $a+\frac{b^2}4$ or $b+\frac{a^2}4<\frac1{2022}$. Observe equations:
\begin{align}
(a_1+a_{2022})+(a_2+a_{2021})+\cdots+(a_{2023}+a_{2023})=2,\tag0\\
(a_1+a_{2023})+(a_2+a_{2022})+\cdots+(a_{2023}+a_1)=2,\tag1\\
\cdots \cdots \cdots \cdots \cdots\cdots\\
(a_1+a_{2021})+(a_2+a_{2020})+\cdots+(a_{2023}+a_{2022})=2.\tag{2022}
\end{align}
Equation tagged $(x)$ satisfies that the sum of subscripts in each bracket $\equiv x\pmod{2023}$.

By average principle, we find a different pair of $(i,j)$ satisfying $a_i+a_j<\frac1{2022}$ for each equation.

So the answer is $2023^2-2023=4090506$.

Best Answer

Call a pair $(j,k)$ good if $a_j+\frac{{a_k}^2}4\ge\frac1{2022}$. Call it bad otherwise.

WLOG assume $a_1\le a_2\le\cdots\le a_{2023}$. There are two cases.

  • $a_{45}<\frac1{2023}$.
    Since $a_j+\frac{{a_k}^2}4$ $<\frac1{2023}+\frac{(\frac{1}{2023})^2}4$ $<\frac1{2022}$ for all $1\le j, k\le 45$, every pair $(j,k)$ where $1\le j,k\le 45$ is a bad pair. There are $45\times45=2025$ of them..

  • $a_{45}\ge\frac1{2023}$.
    $$\begin{align} &\quad a_1+\frac{{a_{2023}}^2}4\\ &\le a_1 + \frac{(1-44a_1-\frac{1978}{2023})^2}4\tag{1a}\\ &\le\max(\frac{(1-\frac{1978}{2023})^2}4, \frac1{2023}+\frac{(\frac1{2023})^2}4)\tag{1b}\\ &<\max(\frac{(\frac1{30})^2}4,\frac1{2023}+\frac{1}{2022\times2023})\\ &=\frac1{2022} \end{align}$$ Explanations:

    • ($1\text{a}$): Since $a_1+a_2+\cdots+a_{44}\ge44a_1$ and $a_{45}+a_{46}+\cdots+a_{2022}$ $\ge(2022-44)a_{45}$ $\ge\frac{1978}{2023}$, we have $0\le a_{2023}$ $=1-(a_1+a_2+\cdots+a_{44})$ $-$ $(a_{45}+a_{46}+\cdots+a_{2022})$ $\le1-44a_1-\frac{1978}{2023}.$
    • ($1\text{b}$): The expression at ($1\text{a}$) is a quadratic polynomial in variable $a_1$ in interval $[0,\frac1{2023}]$ with a positive leading coefficient, which must reach its maximum when $a_1$ is at the endpoints of $[0,\frac1{2023}]$.

    Since $a_1+\frac{{a_k}^2}4$ $\le a_1+\frac{{a_{2023}}^2}4$ $<\frac1{2022}$ for all $k$, every pair $(1,k)$ is a bad pair. There are $2023$ of them.

In both cases, there are at least $2023$ bad pairs. Hence the number of good pairs is at most $2023^2-2023=2022\times2023$.

Moreover, there are $2022\times2023$ good pairs when $a_1=0$, $a_2=\cdots=a_{2023}=\frac1{2022}$.

Related Question