Задача М61‍‍

Ответ: При правильной игре разность оставшихся чисел равна 32 (как говорят, «цена игры» равна 32).

На этот ответ наводят следующие соображения: первый игрок стремится к тому, чтобы разность между оставшимися числами была как можно больше, и он должен всё время стараться максимально «разредить» остающееся множество чисел, а второму выгодно вычёркивать числа «с краёв» (рис. 1). Эти соображения, конечно, не являются строгим доказательством. Многие читатели, руководствуясь не менее правдоподобными, на первый взгляд, соображениями, например, такими: первый должен вычёркивать числа из середины, чтобы оставались числа с большой разностью, получали неверные ответы: 1 или 5, или 6 и разные другие.

Для того чтобы полностью обосновать ответ, в этой задаче (как и при исследовании любой игровой ситуации) нужно доказать два утверждения:

1. как бы ни играл второй, первый может получить не меньше 32;
2. как бы ни играл первый, второй может потерять не больше 32.

Для доказательства утверждения 1) мы укажем такую стратегию первого игрока, которая независимо от ходов второго гарантирует, что разность оставшихся двух чисел будет не меньше 32. Эта стратегия описывается очень просто: при каждом ходе вычёркивать числа через одно, т. е. вычёркивать второе, четвёртое, шестое, $\ldots$‍‍ число из оставшихся (мы считаем, что числа расположены в порядке возрастания). Тогда после 1-го хода разность между любыми соседними из оставшихся чисел будет не меньше 2, после 2-го — не меньше 4, после 3-го — не меньше 8, после 4-го — нe меньше 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, $\ldots$‍,‍ $2^{2n}$‍,‍ то «цена игры» равна $2^n$‍.‍ Но детальное исследование подобной игры, начинающейся с произвольного множества чисел (не обязательно арифметической прогрессии) представляет собой существенно более трудную задачу.