Задача 66757

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

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

Условие

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

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

Решение

  Допустим, Петя не взял карточку, на которой написано  $x_{6}x_{7}x_{8}x_{9}x_{10}$.  Тогда Вася может взять эту карточку, а дальше брать любые карточки. При  $x_{1}=x_{2}=x_{3}=x_{4}=x_{5}=0$,  $x_{6}=x_{7}=x_{8}=x_{9}=x_{10}=1$  сумма произведений у Пети будет равна 0, а у Васи – 1.
  Если Петя сразу же взял карточку, на которой написано  $x_{6}x_{7}x_{8}x_{9}x_{10}$,  то Вася может взять карточку, на которой написано  $x_{5}x_{7}x_{8}x_{9}x_{10}$,  а следующим ходом одну из карточек  $x_{4}x_{7}x_{8}x_{9}x_{10}$  или  $x_{5}x_{6}x_{8}x_{9}x_{10}$  (хотя бы одна из них останется). Далее Вася может брать карточки как угодно.
  В случае, если Вася взял карточку  $x_{4}x_{7}x_{8}x_{9}x_{10}$,  он присваивает переменным значения  $x_{1}=x_{2}=x_{3}=0$,  $x_{4}=x_{5}=x_{6}=1$,  $x_{7}=x_{8}=x_{9}=x_{10}=100$.  Тогда только на 21 карточке окажется ненулевое произведение, причём для трёх карточек  $x_{4}x_{7}x_{8}x_{9}x_{10}$,  $x_{5}x_{7}x_{8}x_{9}x_{10}$  и  $x_{6}x_{7}x_{8}x_{9}x_{10}$  это произведение будет равно $10^8$, а для остальных не будет превосходить $10^6$. Таким образом, сумма у Васи будет не меньше $2\cdot 10^8$, а у Пети не больше $1,18\cdot 10^8$.
  В случае, если Вася взял карточку  $x_{5}x_{6}x_{8}x_{9}x_{10}$,  он присваивает переменным значения  $x_{1}=x_{2}=x_{3}=x_{4}=0$,  $x_{5}=x_{6}=x_{7}=1$,  $x_{8}=x_{9}=x_{10}=10$.
Тогда только на шести карточках окажется ненулевое произведение, причём для трёх карточек  $x_{5}x_{6}x_{8}x_{9}x_{10}$,  $x_{5}x_{7}x_{8}x_{9}x_{10}$  и  $x_{6}x_{7}x_{8}x_{9}x_{10}$  это произведение будет равно 1000, а для остальных трёх – 100. Таким образом, сумма у Васи будет не меньше 2000, а у Пети не больше 1300.

Ответ

Может.

Замечания

8 баллов

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

олимпиада
Название	Турнир городов
номер/год
Дата	2018/19
Номер	40
вариант
Вариант	весенний тур, сложный вариант, 10-11 класс
задача
Номер	6