Problem A. 852. (April 2023)

A. 852. Let \(\displaystyle (a_i,b_i)\) be pairwise distinct pairs of positive integers for \(\displaystyle 1 \le i \le n\). Prove that

\(\displaystyle (a_1+a_2+\dots+a_n) (b_1+b_2+\dots+b_n)>\frac{2}{9} n^3, \)

and show that the statement is sharp, i.e. for an arbitrary \(\displaystyle c>\frac{2}{9}\) it is possible that

\(\displaystyle (a_1+a_2+\dots+a_n) (b_1+b_2+\dots+b_n)<cn^3. \)

Submitted by Péter Pál Pach, Budapest, based on an OKTV problem

(7 pont)

Deadline expired on May 10, 2023.

Let \(\displaystyle c_j\) denote the number of pairs where \(\displaystyle a_i=j\). Let \(\displaystyle k\) be the maximum value of \(\displaystyle j\) for which \(\displaystyle c_j>0\). To decrease the sum of the \(\displaystyle b_i\)'s we can assume that the \(\displaystyle b_i\)'s corresponding to \(\displaystyle a_i=j\) are \(\displaystyle 1\), \(\displaystyle 2\),..., \(\displaystyle c_j\). Now it's easy to see that \(\displaystyle c_1+...+c_k=n\), \(\displaystyle a_1+...+a_n=c_1+2c_2+...+kc_k\) and \(\displaystyle b_1+...+b_n=(c_1^2+c_1+c_2^2+c_2+...+c_k^2+c_k)/2=(c_1^2+...+c_k^2+n)/2\). Thus we have to prove that

\(\displaystyle (c_1+2c_2+...+kc_k)(c_1^2+...+c_k^2+n)/2\ge 2/9n^3. \)

Dividing both sides by \(\displaystyle n^3\) and using notation \(\displaystyle x_j=c_j/n\) we get that

\(\displaystyle (x_1+2x_2...+kx_k)(x_1^2+...+x_k^2+1/n)\ge 4/9 \)

is to be proved, where \(\displaystyle x_j\ge 0\) and \(\displaystyle x_1+...+x_k=1\). Obviously the \(\displaystyle 1/n\) should be omitted from the second factor at this point. Now suppose that \(\displaystyle x_1+2x_2+...+kx_k\) is fixed value, let's say \(\displaystyle m\). The two linear conditions on the \(\displaystyle x_j\)'s define a \(\displaystyle k-2\) dimensional plane, and we need to find its point that minimizes the sum of the squares of the coordinates, i.e. its point that is closest to the origin. This is the orthogonal projection of the origin to this \(\displaystyle k-2\) dimensional plane, so this point is defined by being in the 2-dimensional plane defined by the normal vectors \(\displaystyle (1,2,...,k)\) and \(\displaystyle (1,1,...,1)\) (of hyperplanes \(\displaystyle x_1+2x_2+...+kx_k=m\) and \(\displaystyle x_1+...+x_k=1\)). Denoting the coefficients by \(\displaystyle \lambda\) and \(\displaystyle \mu\), we get that our point of minimum is at \(\displaystyle (x_1,x_2,...,x_k)=(\lambda+\mu,2\lambda+\mu,...,k\lambda+\mu)\). Now substituting this back into the linear conditions we get a system of equations for \(\displaystyle \lambda\) and \(\displaystyle \mu\):

\(\displaystyle \frac{k(k+1)}{2}\lambda+k\mu=1 \)

and

\(\displaystyle \frac{k(k+1)(2k+1)}{6}\lambda+\frac{k(k+1)}{2}\mu=m. \)

Using these results we get

\(\displaystyle x_1^2+...+x_k^2=\frac{k(k+1)(2k+1)}{6}\lambda^2+2\frac{k(k+1)}{2}\lambda\mu+k\mu^2=m\lambda+\mu. \)

Now the system of equations for \(\displaystyle \lambda\) and \(\displaystyle \mu\) simplifies to

\(\displaystyle (k+1)\lambda+2\mu=\frac{2}{k} \)

and

\(\displaystyle (2k+1)\lambda+3\mu=\frac{6m}{k(k+1)}. \)

Solving this system of equations yields \(\displaystyle \lambda=\frac{6(2m-(k+1))}{(k-1)k(k+1)}\) and \(\displaystyle \mu=\frac{2(2k+1)-6m}{(k-1)k}\). Now the non-negativity of the \(\displaystyle x_i\)'s yield conditions

\(\displaystyle x_1=\lambda+\mu=\frac{4}{k}-\frac{6m}{k(k+1)}\ge 0 \)

and

\(\displaystyle x_k=k\lambda+\mu=\frac{6m}{k(k+1)}-\frac{2}{k}\ge 0 \)

which lead to the condition of \(\displaystyle \frac{k+1}{3}\le m\le \frac{2(k+1)}{3}\). Finally we can calculate product

\(\displaystyle (x_1+...+kx_k)(x_1^2+...+x_k^2)=m(m\lambda+\mu)=\frac{12m^3-12m^2(k+1)+2m(k+1)(2k+1)}{(k-1)k(k+1)}, \)

and we need to minimize this for \(\displaystyle \frac{k+1}{3}\le m\le \frac{2(k+1)}{3}\). Now note that increasing \(\displaystyle k\) will decrease the minimum in the problem, thus we are only interested in the asymptotic behaviour of this expression as \(\displaystyle k\) goes to infinity. Thus the whole thing can be simplified to

\(\displaystyle \frac{12m^3-12m^2k+4mk^2}{k^3}. \)

Now the derivative of the numerator in \(\displaystyle m\) is

\(\displaystyle 36m^2-24mk+4k^2=(6m-2k)^2 \)

thus the minimum is reached at \(\displaystyle m=k/3\), and the value is

\(\displaystyle \frac{12}{27}-\frac{12}{9}+\frac{4}{3}=\frac{12}{27}=\frac{4}{9}. \)

We can be arbitrarily close to this value by choosing a large \(\displaystyle k\) and choosing \(\displaystyle x_i\)'s to be rational values very close to the optimal values (\(\displaystyle n\) will be their common denominator).

We can also give a simple explicit construction for the \(\displaystyle a_i's\) and \(\displaystyle b_i's\): for a fixed positive integer \(\displaystyle k\) let us consider all pairs for which \(\displaystyle a_i+b_i\le k+1\). To get these pairs we can also say that we consider those triplets of positive integers for which \(\displaystyle a+b+c=k+2\) (and take the first two of them). To break up \(\displaystyle k+2\) into three such parts we need to pick two of the \(\displaystyle k+1\) possible points where we can break \(\displaystyle k+2\) up, thus the number of pairs is \(\displaystyle n=\binom{k+1}{2}\). Because of symmetry the sum of the \(\displaystyle a\)'s, \(\displaystyle b\)'s and \(\displaystyle c\)'s are all the same, and thus all sums must be \(\displaystyle (k+2)\binom{k+1}{2}/3=\binom{k+2}{3}\). So finally

\(\displaystyle \frac{(a_1+...+a_n)(b_1+...+b_n)}{n^3}=\frac{\binom{k+2}{3}^2}{\binom{k+1}{2}^3}=\frac{8(k+2)^2}{36k(k+1)}, \)

which goes to \(\displaystyle \frac{8}{36}=\frac{2}{9}\) as \(\displaystyle k\) goes to infinity.

Statistics:

5 students sent a solution.
6 points:	Varga Boldizsár.
5 points:	1 student.
4 points:	2 students.
2 points:	1 student.

Problems in Mathematics of KöMaL, April 2023