Задача 66607

Тема:    [ Теория алгоритмов (прочее) ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Богданов И.И.

Петя и Вася играют в игру. Для каждых пяти различных переменных из набора $x_1,\ldots,x_{10}$ имеется единственная карточка, на которой записано их произведение. Петя и Вася по очереди берут по карточке, начинает Петя. Когда все карточки разобраны, Вася присваивает переменным значения как хочет, но так, что $0\leqslant x_1\leqslant\ldots\leqslant x_{10}$. Может ли Вася гарантированно добиться того, чтобы сумма произведений на его карточках была больше, чем у Пети?

Решение

Покажем, как может действовать Вася, чтобы сумма произведений на его карточках была больше, чем у Пети.

Предположим, что Петя не взял карточку, на которой написано $x_6x_7x_8x_9x_{10}$. Тогда Вася может взять эту карточку, а дальше брать любые карточки. При $$\begin{align*} x_1 = x_2 = x_3 = x_4 = x_5 &= 0, \\ x_6 = x_7 = x_8 = x_9 = x_{10} &= 1 \end{align*}$$ сумма произведений у Пети будет равна $0$, а у Васи будет равна $1$.

Если Петя сразу же взял карточку, на которой написано $x_6x_7x_8x_9x_{10}$, то Вася может взять карточку, на которой написано $x_5x_7x_8x_9x_{10}$, а следующим ходом одну из карточек $x_4x_7x_8x_9x_{10}$ или $x_5x_6x_8x_9x_{10}$ (хотя бы одна из них останется, поскольку за ход Петя может взять только одну из этих двух карточек). Далее Вася может брать карточки как угодно.

В случае, если Вася взял карточку $x_4x_7x_8x_9x_{10}$, он может присвоить переменным следующие значения: $$\begin{align*} x_1 = x_2 = x_3 &= 0, \\ x_4 = x_5 = x_6 &= 1, \\ x_7 = x_8 = x_9 = x_{10} &= 100. \end{align*}$$ Тогда только на $21$ карточке окажется ненулевое произведение, причем для трех карточек $x_4x_7x_8x_9x_{10}$, $x_5x_7x_8x_9x_{10}$ и $x_6x_7x_8x_9x_{10}$ это произведение будет равно $100\,000\,000$, а для остальных не будет превосходить $1\,000\,000$. Таким образом, сумма у Васи будет не меньше $200\,000\,000$, а у Пети не больше $118\,000\,000$.

В случае, если Вася взял карточку $x_5x_6x_8x_9x_{10}$, он может присвоить переменным следующие значения: $$\begin{align*} x_1 = x_2 = x_3 = x_4 &= 0, \\ x_5 = x_6 = x_7 &= 1, \\ x_8 = x_9 = x_{10} &= 10. \end{align*}$$ Тогда только на $6$ карточках окажется ненулевое произведение, причем для трех карточек $x_5x_6x_8x_9x_{10}$, $x_5x_7x_8x_9x_{10}$ и $x_6x_7x_8x_9x_{10}$ это произведение будет равно $1000$, а для остальных трех будет равно $100$. Таким образом, сумма у Васи будет не меньше $2000$, а у Пети не больше $1400$.

Ответ

Да.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Год	2019
Номер	82
класс
	1
Класс	10
задача
Номер	5