Условие
Два мудреца играют в следующую игру. Выписаны числа 0, 1, 2,..., 1024. Первый
мудрец зачёркивает 512 чисел (по своему выбору), второй зачёркивает 256 из
оставшихся, затем снова первый зачёркивает 128 чисел и т.д. На десятом шаге
второй мудрец зачёркивает одно число; остаются два числа. После этого
второй мудрец платит первому разницу между этими числами. Как выгоднее играть
первому мудрецу? Как второму? Сколько уплатит второй мудрец первому, если оба
будут играть наилучшим образом? (Ср. с задачей
78710 и с задачей
78716.)
Решение
Ответ: при правильной игре разность оставшихся чисел равна 32
(как говорят, ``цена игры'' равна 32).
На этот ответ наводят следующие соображения: первый игрок
стремится к тому, чтобы разность между оставшимися числами была
как можно больше, и он должен все время стараться максимально ``
разредить'' остающееся множество чисел, а второму выгодно
вычёркивать числа ``с краёв''
Эти соображения, конечно, не являются строгим доказательством.
Для того чтобы полностью обосновать ответ, в этой задаче (как и при
исследовании любой игровой ситуации) нужно доказать два утверждения: 1) как
бы ни играл второй, первый может получить не меньше 32; 2) как бы ни играл
первый, второй может потерять не больше 32.
Для доказательства утверждения 1) мы укажем такую стратегию первого игрока,
которая независимо от ходов второго гарантирует, что разность оставшихся двух
чисел будет не меньше 32. Эта стратегия описывается очень просто: при
каждом ходе вычёркивать числа через одно, то есть вычёркивать второе,
четвёртое, шестое, ...число из оставшихся (мы считаем, что числа
расположены в порядке возрастания). Тогда после 1-го хода разность между
любыми соседними из оставшихся чисел будет не меньше 2, после 2-го — не
меньше 4, после 3-го — не меньше 8, после 4-го — не меньше 16
и после 5-го — не меньше 32.
Для доказательства утверждения 2) достаточно указать стратегию второго
игрока, которая независимо от ходов первого позволит ему проиграть не больше
32. Она состоит в следующем. Первым ходом он вычёркивает все числа, меньшие
512, или все числа, большие 512 (ясно, что или тех, или других осталось
не больше 256). После этого разность между крайними из оставшихся чисел
будет не больше 512. Аналогично вторым ходом он может добиться того, что
все оставшиеся числа будут находиться только в одном из отрезков [0, 256];
[256, 512];
[512, 768];
[768, 1024], то есть уменьшить разность между
крайними числами по крайней мере до 256. Точно так же 3-м ходом он может
уменьшить эту разность до 128, 4-м — до 64 и 5-м — до 32.
Разумеется, аналогично можно было бы доказать, что если игра состоит из
n
ходов и начинается с чисел
0, 1, 2,..., 2
2n, то "цена игры"
равна 2
n. Но детальное исследование подобной игры, начинающейся с
произвольного множества чисел (не обязательно арифметической прогрессии)
представляет собой существенно более трудную задачу.
Ответ
Ответ
При правильной игре разность оставшихся чисел равна 32
(как говорят, <<цена игры>> равна 32).
Источники и прецеденты использования
