Maths Olympiad Prep

Library / /44 of 44

Algebra Difficulty 7.6 National olympiad, round 2 Prove it Russia

Let n2n \ge 2 be a positive integer. Petya and Vasya play the following game. Petya chooses 2n2n (not necessarily distinct) nonnegative real numbers x1,x2,,x2nx_1, x_2, \dots, x_{2n} whose sum equals 11, and tells those numbers to Vasya. Vasya arranges those numbers in a circle by his own choice, computes the product in each pair of adjacent numbers, 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? (A. Khrabrov)

Solution

Если Петя выберет числа 0,12,14(n1),14(n1),,14(n1)0, \frac{1}{2}, \frac{1}{4(n-1)}, \frac{1}{4(n-1)}, \dots, \frac{1}{4(n-1)}, то, как бы ни расставлял эти числа Вася, число 12\frac{1}{2} будет в одной паре с числом 14(n1)\frac{1}{4(n-1)}. Значит, одно из произведений будет равно 18(n1)\frac{1}{8(n-1)}, а остальные будут не больше него. Тогда на доске окажется число 18(n1)\frac{1}{8(n-1)}.

Покажем, как Вася может для любых чисел получить на доске число, не большее 18(n1)\frac{1}{8(n-1)}. Перенумеруем числа в порядке убывания: x1x2x2nx_1 \ge x_2 \ge \dots \ge x_{2n}. Поставим в какое-то место на круге число x1x_1, от него по часовой стрелке через пустые места числа x2,x3,,xnx_2, x_3, \dots, x_n. Теперь поставим число x2nx_{2n} между x1x_1 и xnx_n; дальше по часовой стрелке от x2nx_{2n} расставим на пустых местах по очереди числа x2n1,x2n2,,xn+1x_{2n-1}, x_{2n-2}, \dots, x_{n+1}. Тогда произведениями пар соседних чисел будут: xnx2nx_n x_{2n},
x1x2n,x2x2n1,x3x2n2,,xkx2nk+1,,xnxn+1x_1 x_{2n}, x_2 x_{2n-1}, x_3 x_{2n-2}, \dots, x_k x_{2n-k+1}, \dots, x_n x_{n+1} и
x1x2n1,x2x2n2,x3x2n3,,xkx2nk,,xn1xn+1x_1 x_{2n-1}, x_2 x_{2n-2}, x_3 x_{2n-3}, \dots, x_k x_{2n-k}, \dots, x_{n-1} x_{n+1}.
Поскольку xkx2nk+1xkx2nkx_k x_{2n-k+1} \le x_k x_{2n-k}, наибольшее произведение может быть лишь во второй строке.
Покажем, что a=xkx2nk18(n1)a = x_k x_{2n-k} \le \frac{1}{8(n-1)} при kn1k \le n-1. Действительно, из неравенств xkxk1x1x_k \le x_{k-1} \le \dots \le x_1 следует, что kxkx1+x2++xkk x_k \le x_1 + x_2 + \dots + x_k, поэтому
ka=kxkx2nk(x1+x2++xk)x2nk. ka = k x_k \cdot x_{2n-k} \le (x_1 + x_2 + \dots + x_k) x_{2n-k}.
Аналогично из неравенств
x2nkx2nk1x2nk2xk+1следует, что(2n2k)x2nkx2nk+x2nk1++xk+1xk+1+xk+2++x2n=1x1x2xk. x_{2n-k} \le x_{2n-k-1} \le x_{2n-k-2} \le \dots \le x_{k+1} \\ \text{следует, что} \\ (2n-2k)x_{2n-k} \le x_{2n-k} + x_{2n-k-1} + \dots + x_{k+1} \le \\ \le x_{k+1} + x_{k+2} + \dots + x_{2n} = 1 - x_1 - x_2 - \dots - x_k.
Поэтому
2k(nk)a(x1+x2++xk)(1x1x2xk)=x(1x),где x=x1+x2++xk. Поскольку по неравенству о средних длядвух чисел x(1x)(x+(1x)2)2=14, получаем неравенствоxkx2n2k=a18k(nk). Осталось показать, что k(nk)n1при kn1. Но последнее неравенство можно переписать ввиде (k1)(nk1)0, а обе скобки в последней формуленеотрицательны. 2k(n-k)a \le (x_1 + x_2 + \dots + x_k) (1 - x_1 - x_2 - \dots - x_k) = x(1-x), \\ \text{где } x = x_1+x_2+\dots+x_k. \text{ Поскольку по неравенству о средних для} \\ \text{двух чисел } x(1-x) \le \left(\frac{x+(1-x)}{2}\right)^2 = \frac{1}{4}, \text{ получаем неравенство} \\ x_k x_{2n-2k} = a \le \frac{1}{8k(n-k)}. \text{ Осталось показать, что } k(n-k) \ge n-1 \\ \text{при } k \le n-1. \text{ Но последнее неравенство можно переписать в} \\ \text{виде } (k-1)(n-k-1) \ge 0, \text{ а обе скобки в последней формуле} \\ \text{неотрицательны.}

Замечание. Оптимальная расстановка для Васи не единственна. Однако можно доказать, что при любом k=1,2,,n1k = 1, 2, \dots, n-1 в любой Васиной расстановке среди произведений пар соседних чисел найдётся число, не меньшее xkx2nkx_k x_{2n-k}; поэтому оптимальными для Васи окажутся расстановки, в которых наибольшее произведение имеет такой вид.

Ответ. 18(n1)\frac{1}{8(n-1)}.

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.