Задача 66734

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

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

Условие

Автор: Погудин Г.А.

Рокфеллер и Маркс играют в такую игру. Имеется  $n > 1$  городов, во всех одно и то же число жителей. Сначала у каждого жителя есть ровно одна монета (монеты одинаковы). За ход Рокфеллер выбирает по одному жителю из каждого города, а Маркс перераспределяет между ними их деньги произвольным образом с единственным условием, чтобы распределение не осталось таким, каким только что было. Рокфеллер выиграет, если в какой-то момент в каждом городе будет хотя бы один человек без денег. Докажите, что Рокфеллер может действовать так, чтобы всегда выигрывать, как бы ни играл Маркс, если в каждом городе
  а) ровно $2n$ жителей;
  б) ровно  $2n - 1$  житель.

Решение

  Пусть $k$ – количество жителей в городе. Будем изображать ситуацию в игре таблицей с $n$ строками и $k$ столбцами: в i-й строке будут перечислены благосостояния $a_{i1}, ..., a_{ik}$ всех жителей i-го города в порядке неубывания. Пусть $S_j$ – сумма чисел в j-м столбце.

  а) Стратегия Рокфеллера. Если  $S_j = S_{j+1}$,  выбрать всех жителей из j-го столбца.
  Предположим, что  $S_j = S_{j+1}$;  тогда  $a_{ij} = a_{i,j+1}$  при всех $i$. После марксова перераспределения числа $S_{j+1}, ..., S_k$ не уменьшатся. С другой стороны, у одного из выбранных жителей (пусть он в i-м городе) благосостояние станет больше чем $a_{ij}$. Это значит, что одна из сумм $S_k$ при  $k \geqslant j + 1$  увеличится (та, в которую попало новое число). Поэтому последовательность $S_k, S_{k-1}, ..., S_1$ лексикографически увеличится. Это не может продолжаться бесконечно долго (наборов из $k$ чисел с фиксированной суммой конечное количество), так что в некоторый момент все числа $S_1, ..., S_k$ окажутся различными.
  Пусть  $S_1 \geqslant 1$.  Тогда  $S_i \geqslant i$  при всех $i$, откуда  $nk = S_1 + ... + S_k \geqslant 1 + 2 + ... + k = \frac{1}{2} k(k + 1)$,  то есть  $k \leqslant 2n - 1$.  Противоречие.
  Значит, $S_1 = 0$, и Рокфеллер победил.

  б) Пусть  $k = 2n - 1$.  Применяя стратегию из пункта а), Рокфеллер либо выиграет, либо добьётся состояния  $S_i = i$  при всех  $i = 1, ..., k$.  Покажем, как ему выиграть, начиная с такой позиции.
  Скажем, что игра находится в i-й ситуации  ($1 \leqslant i \leqslant n + 1$),  если (возможно, после перенумерации строк) выполнены следующие условия:
  - при  $j = 1, 2, ..., i - 1$  в j-м столбце стоят $j$ единиц в верхних клетках, а остальные числа – нули;
  - в i-м столбце нижние  $n + 1 - i$  элементов – нули.
  Покажем, что в рассматриваемый момент игра находится в i-й ситуации при некотором $i$. Переставим строки так, чтобы количества нулей в них не убывали сверху вниз. Пусть при некотором  $i \leqslant n$  в i-м столбце не стоит i единиц; выберем наименьшее такое $i$. Тогда (из условия на нули в строках) в предыдущих столбцах единицы стоят "треугольником", а в i-м столбце есть  $n + 1 - i$  нулей, то есть игра в i-й ситуации. Если же такого $i$ нет, то в первых n столбцах единицы стоят "треугольником", и игра в (n+1)-й ситуации.
  Покажем, что при  $i > 1$,  если игра в i-й ситуации, Рокфеллер может уменьшить номер ситуации одним ходом. Так он рано или поздно добьётся 1-й ситуации, то есть своего выигрыша.
  Действительно, Рокфеллер выбирает (i–1)-й столбец. Пусть $j$ – наименьший индекс, при котором число в j-й строке уменьшится (т.е. превратится в 0) в результате действия Маркса. Поскольку  $j\leqslant i-1$,  то после этого хода (и упорядочивания строк, при котором этот 0 переместится в начало строки) будет наблюдаться j-я ситуация (здесь мы уже не требуем равенств  $S_k = k$),  что и требовалось.

Замечания

баллы: 10 + 4

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

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