Задача
ALG-B2-M02-P020 Игра с парами
Петя выбирает \(20\) неотрицательных чисел с суммой \(1\). Вася разбивает их на \(10\) пар и записывает наибольшее произведение в паре. Петя хочет сделать это число как можно больше, Вася — как можно меньше. Найдите значение при правильной игре.
Подсказка 1. Для нижней оценки Петя может взять \(\frac12\) и девятнадцать равных чисел.
Подсказка 2. Для верхней оценки Вася упорядочивает числа и спаривает крайние.
Ответ: \(\frac1{76}\). Петя берёт числа \(\frac12,\frac1{38},\ldots,\frac1{38}\). Число \(\frac12\) обязательно попадёт в пару с \(\frac1{38}\), поэтому максимальное произведение не меньше \(\frac1{76}\), а остальные произведения не больше.
Теперь пусть числа произвольны, \(x_1\ge\cdots\ge x_{20}\). Вася спаривает \(x_k\) с \(x_{21-k}\). Для \(k\le10\) положим \(P=x_kx_{21-k}\). Из \(kx_k\le x_1+\cdots+x_k=S\) и \((21-2k)x_{21-k}\le1-S\) получаем \[P\le\frac{S(1-S)}{k(21-2k)}\le\frac1{4k(21-2k)}\le\frac1{76}.\] Значит, Вася может гарантировать максимум не больше \(\frac1{76}\). Ответ доказан.
A. Анализ источника. Главные объекты: положительные величины, произведение или сумма, выбор правильных слагаемых для AM-GM и строгий случай равенства. Очевидный первый подход обычно пытается применить AM-GM к видимым слагаемым, но этого мало. Скрытое наблюдение: надо предварительно нормировать, упорядочить, домножить или заменить выражение так, чтобы произведение нужных членов стало контролируемым.
B. Новая задача. Формулировка изменена; сохранена только архитектура метода.
C-D. Подсказки. Две подсказки находятся в полях hint: первая мягкая, вторая указывает уровень метода.
E. Полное решение. Дано в поле solution.
F. Обоснование сложности. Региональный уровень 7: требуется стратегия для обеих сторон и AM-GM-оценка \(S(1-S)\le\frac14\).
G. Почему это не одноходовая задача. Нужно доказать и пример, и верхнюю оценку для произвольного выбора.