ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 78721
Темы:    [ Теория игр (прочее) ]
[ Полуинварианты ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Два мудреца играют в следующую игру. Выписаны числа 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,..., 22n, то "цена игры" равна 2n. Но детальное исследование подобной игры, начинающейся с произвольного множества чисел (не обязательно арифметической прогрессии) представляет собой существенно более трудную задачу.

Ответ

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

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

журнал
Название "Квант"
год
Год 1971
выпуск
Номер 1
Задача
Номер М61
олимпиада
Название Московская математическая олимпиада
год
Номер 32
Год 1969
вариант
Класс 10
Тур 2
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .