24
Окружение гесканма
А. П. Савин
Игра в крестики-ноликки на клетчатой бумаге давно стала одним из любимых развлечений школьников и студентов, поскольку ручка или карандыш и листок бумаги в клетку, у них всегда под рукой.
В задаче М91 был предложен новый вариант этой игры.
М91. Двое играют в «крестики» и «ноликки» на бесконечном листе клетчатой бумаги. Начинающий ставит крестик в любую клетку. Каждый следующим своим ходом он должен ставить крестик в любую свободную клетку, соседнюю с одной клеткой считается любая, имеющая с ней общую сторону или общую вершину. Второй играющий каждим своим ходом может ставить сразу три поликка в любые три свободные клетки (не обязательно рядом друг с другом). Докажите, что, как бы ни играл первый, второй может его «запереть»: добиться того, чтобы первому больше некуда было поставить крестик.
Исследуйте аналогичные игры, в которых второму разрешается за один ход ставить не три, а только два или только один поликк. Каков здесь будет результат при правильной игре партеравов: удаться ли поликам «запереть» крестики (и какое наиболее чисто ходов могут «продержаться» крестики) или игра может продолжаться до бесконечности?
Попробуйте изучить другие варианты этой игры: когда соседними с данной считаются только клетки, имеющие с ней общую сторону; когда плоскость разбията не на квадраты, а на правильные шестиугольники; когда первому разрешается ставить сразу р крестиков, а второму — q поликков.
Дейстия крестиков очень похожи на действия десята, пытающегося избежать окружения, поэтому мы и называли эту игру «окружение десята».
Простейший вариант этой игры таков: начинающий ставит крестик, второй — три поликка на любые три свободных поля, затем первый ставит
Рис. 1. Рис. 2. а) Рис. 6)
25
еше один крестик на свободное поле, соседнее с тем, где уже стоит крестик, а второй — ещё три полка на свободные поля. И так далее, каждый раз крестики ставятся на свободные поля, соседние с тем, где уже стоит крестики, а полки — на любые свободные поля. Начинающий ставется поставить как можно больше крестиков, а второй — помещать ему это сделать.
В этом варианте задачу решили многое наши читатели. Они показали, что начинающий может поставить не более 7 крестиков. На рисунке 1 показана стратегия полков при первом ходе, обеспечивающая этот результат. Действительно, после этого начинающий может поставить крестик на одно из пятей полей. Нетрудно видеть, что, лишь ставя его на юго-восточное поле, первый может надеться при правальной игре поставить семь крестиков, потому что при ответе полков, изображенным на рисунке 2, а, он может надеться лишь на то, чтобы поставить крестики на поля, отмеченные точками, причем из двух полей, отмеченных красными точками, он смотет поставить крестик не более чем на одном. Как при этом должен ставить полки второй, ясно из рисунка 2, 6.
Если же начинающий ставит второй крестик на другое поле, то после хода второго полукается одна из ситуаций, изображенная на рисунке 3, где уже лишь 4 поля (они также отмечены точками), на которые начинающий может поставить крестик при правальной игре второго. Она заключится в отрезании всех полей продвижения от поставленного вместе точки крестика, аналогично тому, как это делалось и в первом случае (рис. 2, 6).
Попробуем теперь условия задачи полков. Разрешим второму ставить при своем ходе не по 3 полика, а лишь по 2. Интересно, что если с самого начала пытается ставить полки на клетки, соседние с крестиками, то второй не сможет задержать движения крестиков. Посмотрите на рисунок 4. Здесь полки не могут помещать продвижению крестиков вверх (красные знаки — первый ход, черные — второй, зеленье — третий).
Это ясно, поскольку каждим своим ходом полки перекрывают лишь два поля из трех, ведущих вверх.
26
Казалось бы, что тут уже поликни не смогут окружить крестики и, тем более, если на каждый крестик второй ставит лишь по одному полику. Последнее утверждение содержится в подавляющем большинстве письем.
А если второму попытаться организовать вдалеке от первого крестика оборону? Сможет ли он хотя бы помещать двijжению крестиков вверх? Оказывается, да! И даже в случае, если на каждый крестик второй отвечает лишь одним поликом. Эту стратегию второго (она нам понадобится и для окончательного решения задачи) называем «отражением любовой атаки».
Итак, мы пытаемся оставить двijжение крестиков вверх. Посмотрите на рисунок 5. Казалось бы, невозможно не пропустить крестики выше горизонтальной линии, ведь через шесть ходов крестики могут оказаться на любом из 13 квадратов, отмещенных точками, а второй за это время сможет поставить лишь 6 поликов. Тепер посмотрим на рисунок 6. Игра началась, и с каждым ходом крестики угрожают все меньше числу полей за горизонтальной чертой.
После второго хода — одинадится полям, после третього — девяты, после четверого — семи. Но второму удается поставить за четые хода поликки так, что на угрожаемых полях они стоит через поле. (Попробуйте доказать самостояльно, что при любой игре первого второго сможет это сделать.)
Тепер после пятого хода крестиков получится одна из двух ситуаций, изображенных на рисунке 7. В случае a) второй может ставить поликки в две оставшиеся незаполненные клеточки в любом порядке, а в случае b) он сначала ставит полик в среднюю клетку, а потом, в зависимости от хода первого, влевую или вправую, и крестикам путь прегражден.
Итак, «любовая атака» отбита! второй может не пропустить крестики
выше шестой горизонтали (от той, где стоит первый крестик).
Казалось бы, задача уже решена. Ведь таким же образом мы сможем не пропустить крестики в любом из направлений, то есть ограничить, например, все крестики внутри некоторого квадрата. Однако этот вывод