Maths Olympiad Prep

Library / /188 of 520

Algebra Difficulty 6.3 National olympiad Find the answer

Example 2 Let 0xi1(1in)0 \leqslant x_{i} \leqslant 1(1 \leqslant i \leqslant n), find the maximum value of F=1i<jnxixjF=\sum_{1 \leqslant i<j \leq n}\left|x_{i}-x_{j}\right|.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Since FF is continuous on a closed domain, there must exist a maximum value. Fixing x2,x3,,xnx_{2}, x_{3}, \cdots, x_{n}, then F(x1)F\left(x_{1}\right) is a function of x1x_{1}:
F(x1)=x1x2+x1x3++x1xn+2i<jnxixj.F\left(x_{1}\right)=\left|x_{1}-x_{2}\right|+\left|x_{1}-x_{3}\right|+\cdots+\left|x_{1}-x_{n}\right|+\sum_{2 \leqslant i<j \leqslant n}\left|x_{i}-x_{j}\right| .

Thus, F(x1)F\left(x_{1}\right) attains its maximum value if and only if x1x2+x1x3++x1xn\left|x_{1}-x_{2}\right|+\left|x_{1}-x_{3}\right|+\cdots+\left|x_{1}-x_{n}\right| attains its maximum value. Since 0xi10 \leqslant x_{i} \leqslant 1, by the lemma mentioned above, when F(x1)F\left(x_{1}\right) attains its maximum value, it must be that x1{0,1}x_{1} \in\{0, 1\}. By symmetry, when FF attains its maximum value, it must be that xi{0,1}(1in)x_{i} \in\{0,1\}(1 \leqslant i \leqslant n).

Therefore, we can assume that when FF attains its maximum value, xix_{i} has kk zeros and nkn-k ones. Then,
F(00)×Ck2+(11)×Cnk2+Ck1Cnk1=k(nk)[k+(nk)2]2=n24\begin{aligned} F & \leqslant(0-0) \times \mathrm{C}_{k}^{2}+(1-1) \times \mathrm{C}_{n-k}^{2}+\mathrm{C}_{k}^{1} \mathrm{C}_{n-k}^{1} \\ & =k(n-k) \leqslant\left[\frac{k+(n-k)}{2}\right]^{2}=\frac{n^{2}}{4} \end{aligned}

Since FF is an integer, we have F[n24]F \leqslant\left[\frac{n^{2}}{4}\right].
Equality holds when x1=x2==x[n2]=0,x[n2]+1==xn=1x_{1}=x_{2}=\cdots=x\left[\frac{n}{2}\right]=0, x\left[\frac{n}{2}\right]+1=\cdots=x_{n}=1. Therefore, the maximum value of FF is [n24]\left[\frac{n^{2}}{4}\right].

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.