Maths Olympiad Prep

Library / /37 of 44

Algebra Difficulty 6.8 National olympiad Prove it Russia

Petya and Vasya play the following game. Petya chooses 100 (not necessarily distinct) nonnegative real numbers x1,x2,,x100x_1, x_2, \dots, x_{100} whose sum equals 1, and tells those numbers to Vasya. Vasya splits the numbers into 50 pairs by his own choice, computes the product of numbers in each pair, and writes down the maximal of those products. Petya wants to maximize the written number, while Vasya wants to minimize it. What number will be written at an optimal game?

Solution

Если Петя выберет числа 12,1198,1198,,1198\frac{1}{2}, \frac{1}{198}, \frac{1}{198}, \dots, \frac{1}{198}, то, как бы ни разбивал эти числа Вася, в паре с числом 12\frac{1}{2} будет число 1198\frac{1}{198}.
Их произведение будет равно 1396\frac{1}{396}, а остальные будут не больше него. Тогда на доске окажется число 1396\frac{1}{396}.

Покажем, как Васе для любых Петиных чисел получить на доске число, не большее 1396\frac{1}{396}. Перенумеруем числа в порядке невозрастания: x1x2x100x_1 \ge x_2 \ge \dots \ge x_{100}. Разобьём числа на пары следующим образом: xkx_k в паре с x101kx_{101-k}. Тогда произведениями чисел в парах будут
x1x100,x2x99,x3x98,,xkx101k,,x50x51. x_1x_{100}, x_2x_{99}, x_3x_{98}, \dots, x_kx_{101-k}, \dots, x_{50}x_{51}.
Покажем, что a=xkx101k1396a = x_kx_{101-k} \le \frac{1}{396} при k49k \le 49. Действительно, из неравенств xkxk1x1x_k \le x_{k-1} \le \dots \le x_1 следует, что kxkx1+x2++xkkx_k \le x_1 + x_2 + \dots + x_k, поэтому
ka=kxkx101k(x1+x2++xk)x101k. ka = kx_k \cdot x_{101-k} \le (x_1 + x_2 + \dots + x_k)x_{101-k}.
Аналогично из неравенств x101kx100kx99kxk+1x_{101-k} \le x_{100-k} \le x_{99-k} \le \dots \le x_{k+1} следует, что
(1012k)x101kx101k+x100k++xk+1xk+1+xk+2++x100=1x1x2xk. (101 - 2k)x_{101-k} \le x_{101-k} + x_{100-k} + \dots + x_{k+1} \le \\ \le x_{k+1} + x_{k+2} + \dots + x_{100} = 1 - x_1 - x_2 - \dots - x_k.
Поэтому
k(1012k)a(x1+x2++xk)(1x1x2xk)=x(1x)k(101-2k)a \le (x_1+x_2+\dots+x_k)(1-x_1-x_2-\dots-x_k) = x(1-x), где x=x1+x2++xkx = x_1+x_2+\dots+x_k. Поскольку по неравенству о средних для двух чисел x(1x)(x+(1x)2)2=14x(1-x) \le \left(\frac{x+(1-x)}{2}\right)^2 = \frac{1}{4}, получаем неравенство
xkx101k=a14k(1012k)x_kx_{101-k} = a \le \frac{1}{4k(101-2k)}. Осталось доказать, что k(1012k)99k(101 - 2k) \ge 99 при k49k \le 49. Это неравенство можно переписать в виде (k1)(992k)0(k-1)(99-2k) \ge 0, и обе скобки в последней формуле неотрицательны.

Осталось доказать, что x50x511396x_{50}x_{51} \le \frac{1}{396}. Поскольку x50x49x48x2x1x_{50} \le x_{49} \le x_{48} \le \dots \le x_2 \le x_1, имеем
x50x1+x2++x5050150 x_{50} \le \frac{x_1 + x_2 + \dots + x_{50}}{50} \le \frac{1}{50}
и, аналогично,
x51x1+x2++x5151151. x_{51} \le \frac{x_1 + x_2 + \dots + x_{51}}{51} \le \frac{1}{51}.
Следовательно, x50x5115051<1396x_{50}x_{51} \le \frac{1}{50 \cdot 51} < \frac{1}{396}.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.