|
|
 |
Условие
Рокфеллер и Маркс играют в такую игру. Имеется $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
