Problem A. 869. (January 2024)

A. 869. Let \(\displaystyle A\) and \(\displaystyle B\) be given real numbers. Let the sum of real numbers \(\displaystyle 0\le x_1\le x_2\le\dots\le x_n\) be \(\displaystyle A\), and let the sum of real numbers \(\displaystyle 0\le y_1\le y_2\le\dots\le y_n\) be \(\displaystyle B\). Find the largest possible value of \(\displaystyle {\sum_{i=1}^n (x_i-y_i)^2}\).

Proposed by Péter Csikvári, Budapest

(7 pont)

Deadline expired on February 12, 2024.

If \(\displaystyle A\) or \(\displaystyle B\) is negative, the problem is undefined, so let's suppose \(\displaystyle A,B\ge 0\).

We will prove that the answer is \(\displaystyle (\max(A,B))^2-\frac{2AB}{n}+\frac{(\min(A,B))^2}{n}\), which can be reached with \(\displaystyle x_1=\dots=x_{n-1}=0\), \(\displaystyle x_n=A\) and \(\displaystyle y_1=\dots=y_n=\frac{B}{n}\) for \(\displaystyle A\ge B\), or with \(\displaystyle x_1=\dots=x_n=\frac{A}{n}\) and \(\displaystyle y_1=\dots=y_{n-1}=0\), \(\displaystyle y_n=B\) for \(\displaystyle A<B\).

The main idea is this: points \(\displaystyle (x_1,...,x_n)\) satisfying the conditions will form a solid with \(\displaystyle n\) vertices in an \(\displaystyle n-1\) dimensional subspace of the \(\displaystyle n\)-dimensional space. For example, if \(\displaystyle n=3\) and \(\displaystyle A=2\), we will get a triangle with vertices \(\displaystyle (2/3,2/3,2/3)\), \(\displaystyle (0,1,1)\) and \(\displaystyle (0,0,2)\) is the three dimensional space. The problem asks to find the two points of the two solids that are the furthes away from each other.

To formalize this idea, we note that every \(\displaystyle (x_1,...,x_n)\) satisfying the conditions can be expressed in the form \(\displaystyle \alpha_1(\frac{A}{n}, \ldots, \frac{A}{n})+\alpha_2(0,\frac{A}{n-1},\ldots,\frac{A}{n-1})+...+\alpha_{n-1}(0, \ldots, 0, \frac{A}{2},\frac{A}{2})+\alpha_n(0,\ldots, 0, A)\), where \(\displaystyle A\alpha_1=nx_1\) and \(\displaystyle A\alpha_i=(n+1-i)(x_i-x_{i-1})\) for \(\displaystyle 2\le i \le n\). Observe that \(\displaystyle A(\alpha_1+\alpha_2+\dots+\alpha_n)=x_1+x_2+\dots+x_n=A\), i.e. \(\displaystyle \alpha_1+\alpha_2+\dots+\alpha_n=1\), and every \(\displaystyle \alpha_j\) is a non-negative real number (\(\displaystyle 1\leq{j}\leq{n}\)).

Let \(\displaystyle v_k=(0, 0, \ldots 0, \frac{A}{k}, \frac{A}{k}, \ldots, \frac{A}{k})\) and let \(\displaystyle v_{k,j}\) denote its \(\displaystyle j^{th}\) coordinate. Using these notations, every vector satisfying the conditions can be expressed as \(\displaystyle \sum_{k=1}^n \alpha_k v_k\) such that \(\displaystyle \alpha_k\ge 0\), and \(\displaystyle \sum_{k=1}^n \alpha_k=1\). This is the linear algebra equivalent of saying that the points in the problem form the convex hull of the \(\displaystyle n\) points \(\displaystyle (0,...,0,A)\), \(\displaystyle (0,...,0,\frac{A}{2},\frac{A}{2})\),..., \(\displaystyle (\frac{A}{n},...,\frac{A}{n})\). Now we will phrase and prove formally the intuitive claim that the two points that are the furthest away from each other are vertices of the solids.

Lemma: There exists \(\displaystyle 1\le k \le n\) satisfying \(\displaystyle \sum_{j=1}^n (x_j-y_j)^2\le \sum_{j=1}^n (v_{k,j}-y_j)^2\).

Using the inequality between the weighted arithmetic and quadratic means we get

\(\displaystyle \sum_{k=1}^n \alpha_k (v_{k,j}-y_j)^2\ge \sum_{k=1}^n \big(\alpha_k(v_{k,j}-y_j)\big)^2=(x_j-y_j)^2.\)

for every \(\displaystyle 1\le j \le n\).

Summing these for every \(\displaystyle j\) we get

\(\displaystyle \sum_{k=1}^n \alpha_k \sum_{j=1}^n (v_{k,j}-y_j)^2=\sum_{j=1}^{n} \sum_{k=1}^n \alpha_k (v_{k,j}-y_j)^2\ge \sum_{j=1}^{n} (x_j-y_j)^2.\)

Since weights \(\displaystyle \alpha_k\) are non-negative and their sum is 1, we get that

\(\displaystyle \max_{k} \sum_{j=1}^n (v_{k,j}-y_j)^2\ge \sum_{j=1}^{n} (x_j-y_j)^2,\)

therefore there exists \(\displaystyle k\) for which replacing \(\displaystyle (x_1,...,x_n)\) with \(\displaystyle v_k\) squared distance \(\displaystyle \sum_{j=1}^{n} (x_j-y_j)^2\) won't decrease.

Repeating the same argument we can also replace \(\displaystyle (y_1,...,y_n)\) with vector \(\displaystyle v'_r\) such that \(\displaystyle \sum_{j=1}^{n} (x_j-y_j)^2\) won't decrease. Thus there exists \(\displaystyle e\) and \(\displaystyle f\) for which \(\displaystyle \sum_{j=1}^n (x_j-y_j)^2\le \sum_{j=1}^n (v_{e,j}-v'_{f,j})^2\).

Supposing \(\displaystyle e>f\) we get

\(\displaystyle \sum_{j=1}^n (v_{e,j}-v_{f,j})^2=f(\frac{A}{e}-\frac{B}{f})^2+(e-f)(\frac{A}{e}-0)^2+(n-e)0^2=\frac{A^2}{e}-\frac{2AB}{e}+\frac{B^2}{f}.\)

Therefore in general

\(\displaystyle \sum_{j=1}^n (v_{e,j}-v_{f,j})^2=\frac{A^2}{e}+\frac{B^2}{f}-\frac{2AB}{max(e,f)}.\)

We can assume \(\displaystyle A\ge B\) and apply the rearrangement inequality:

\(\displaystyle \frac{A^2}{e}+\frac{B^2}{f}-\frac{2AB}{\max(e,f)}\le \frac{A^2}{\min(e,f)}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)}.\)

Obviously

\(\displaystyle \frac{A^2}{\min(e,f)}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)}\le \frac{A^2}{1}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)},\)

and \(\displaystyle 0\le B\le A\), therefore \(\displaystyle (B-2A)B\le 0\), and then

\(\displaystyle \frac{A^2}{1}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)}\le A^2+\frac{B^2}{n}-\frac{2AB}{n},\)

so the general answer is

\(\displaystyle \sum_{j=1}^n (x_j-y_j)^2\le (\max(A,B))^2-\frac{2AB}{n}+\frac{(\min(A,B))^2}{n},\)

and equality holds for the choice shown at the beginning of this solution.

Statistics:

15 students sent a solution.
7 points:	Bodor Mátyás, Czanik Pál, Duchon Márton, Fleischman Illés, Foris Dávid, Tarján Bernát, Tianyue DAI, Varga Boldizsár, Wiener Anna.
5 points:	1 student.
3 points:	2 students.
1 point:	1 student.
0 point:	1 student.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, January 2024