Окружение десанта А. П. Савин
Страница переведена на новый сайт https://myeducation.su/ :
страница ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (1972)
Игра в крестики-нолики на клет-
чатой бумаге давно стала одним из
любимых развлечений школьников и
студентов, поскольку ручка или
А. П. Савин
карандаш и листок бумаги в клет-
ку, у них всегда под рукой.
В задаче М91 был предложен но-
вый вариант этой игры.
М 91. Двое играют ¦ «крестики» и «нолики» на бесконечном
листе клетчатой бумаги. Начинающий ставит крестик • любую
клетку. Каждым следующим своим ходом он должен ставить
крестик в любую свободную клетку, соседнюю с одной из клеток,
где уже стоит крестик; соседней с данной клеткой считаетси
любая, имеющая с ней общую сторону или общую вершину. Второй
играющий каждым своим ходом может ставить сразу три нолика
в любые три свободные клетки (не обязательно рядом друг с дру-
гом). Докажите, что, как бы им играл первый, второй может
его «запереть»: добиться того, чтобы первому больше некуда
было поставить крестик.
Окружение десанта
Исследуйте аналогичные игры, в которых второму разрешает-
ся за один ход ставить не три, а только два или только один
нолик. Каков здесь будет результат при правильной игре парт-
неров: удастся ли нолякам «запереть» крестики (и какое наиболь-
шее число ходов могут «продержаться» крестики) или игра может
продолжаться до бесконечности?
Попробуйте изучить другие варианты этой игры: когда со-
седними с данной считаются только клетки, имеющие с ней об-
щую сторону; когда плоскость разбита не на квадраты, а на пра-
вильные шестиугольники; когда первому разрешается ставить
сразу р крестиков, а второму — q ноликов.
Действия крестиков очень похо-
жи на действия десанта, пытающегося
избежать окружения, поэтому мы и
назвали эту игру «окружение десанта».
Простейший вариант этой игры
таков: начинающий ставит крестик,
второй — три нолика на любые три
свободных поля, затем первый ставит
24 Окружение десанта
еще один крестик на свободное поле,
соседнее с тем, где уже стоит крестик,
а второй — еще три нолика на свобод-
ные ноля. И так далее, каждый раз
крестики ставятся на свободные по-
ля, соседние с теми, где уже стоят кре-
стики, а нолики — на любые свобод-
ные поля. Начинающий старается
поставить как можно больше крести-
ков, а второй — помешать ему это
сделать.
В этом варианте задачу решили
многие наши читатели. Они показали,
что начинающий может поставить не
более 7 крестиков. На рисунке 1 по-
казана стратегия ноликов при пер-
вом ходе, обеспечивающая этот ре-
зультат. Действительно, после этого
начинающий может поставить крестик
на одно из нягн полей. Нетрудно ви-
деть, что, лишь ставя его на юго-во-
сточное поле, первый может надеять-
ся при правильной игре поставить
семь крестиков, потому что при отве-
те ноликов, изображенном на рисун-
ке 2, а, он может надеяться лишь
>ia то, чтобы поставить крестики на
поля, отмеченные точками, причем
из двух полей, отмеченных красны-
ми точками, он сможет поставить
крестик не более чем на одном. Как
5?
ГК V
при этом должен ставить нолики вто-
рой, ясно из рисунка 2, б.
Если же начинающий ставит вто-
рой крестик на другое поле, то после
хода второго получается одна из си-
туаций, изображенная на рисунке 3,
где уже лишь 4 поля (они также об-
мечены точками), на которые начи-
нающий может поставить крестик при
правильной игре второго. Она за-
ключается в отрезании всех полей
продвижения от поставленного вместо
точек крестика, аналогично тому, как
это делалось и в первом случае
(рис. 2, б).
Попробуем теперь усложнить за-
дачу ноликов. Разрешим второму ста-
вить при своем ходе не по 3 нолика,
а лишь по 2. Интересно, чго если с
самого начала пытаться ставить но-
лики на клетки, соседние с крести-
ками, то второй не сможет задержать
движения крестиков. Посмотрите на
рисунок 4. Здесь нолики не могут по-
мешать продвижению крестиков вверх
(красные значки — первый ход,
черные — второй, зеленые — тре-
тий).
Это ясно, поскольку каждым сво-
им ходом нолики перекрывают лишь
два поля из трех, ведущих вверх.
25 Окружение десанта
Казалось бы, что тут уже нолики
не смогут окружить крестики и, тем
более, если на каждый крестик вто-
рой ставит лишь по одному нолику.
Последнее утверждение содержится
в подавляющем большинстве пи-
сем.
А если второму попытаться орга-
низовать вдалеке от первого крести-
ка оборону? Сможет ли он хотя бы
помешать движению крестиков вверх?
Оказывается, да! И даже в случае,
если на каждый крестик первого
второй отвечает лишь одним ноли-
ком. Эту стратегию второго (она нам
понадобится и для окончательного
решения задачи) назовем «отражением
лобовой атаки».
Итак, мы пытаемся остановить
движение крестиков вверх. Посмот-
рите на рисунок 5. Казалось бы, не-
возможно не пропустить крестики
выше горизонтальной линии, ведь
через шесть ходов крестики могут
оказаться на любом из 13 квадратов,
отмеченных точками, а второй за это
время сможет поставить лишь 6 но-
ликов. Теперь посмотрим на рису-
нок 6. Игра началась, и с каждым
ходом крестики угрожают все мень-
шему числу полей за горизонтальной
чертой.
После второго хода — одиннадца-
ти полям, после третьего — девяти,
после четвертого — семи. Но второ-
му удается поставить sa четыре хода
нолики так, что на угрожаемых полях
они стоят через поле. (Попробуйте
доказать самостоятельно, что при лю-
бой игре первого второй сможет это
сделать.)
Теперь после пятого хода крести-
ков получится одна из двух ситуа-
ций, изображенных на рисунке 7.
В случае а) второй может ставить
нолики в две оставшиеся незаполнен-
ные клеточки в любом порядке, а
в случае б) он сначала ставит нолик
в среднюю клетку, а потом, в зависи-
мости от хода первого, в левую или
в правую, и крестикам путь преграж-
ден.
Итак, «лобовая атака» отбита! Вто-
рой может не пропустить крестики
26
¦т-г
О
A
Рис. 8.
Рис. 9.
выше шестой горизонтали (от той,
где стоит первый крестик).
Казалось бы, задача уже решена.
Ведь таким же образом мы сможем
не пропустить крестики в любом из
направлений, то есть ограничить, на-
пример, все крестики внутри некото-
рого квадрата. Однако этот вывод
26 Окружение десанта
преждевременен, мы не учли возмож-
ности «атаки на угол».
Если крестик стоит на диагонали
обороняемого квадрата, то он уг-
рожает почти вдвое большему числу
полей за пределами квадрата, чем
при «лобовой атаке» на сторону это-
го квадрата, например, на рисун-
ке 8 он угрожает, как и раньше
(рис. 5), тринадцати полям каждой
стороны, а в совокупности 25 полям.
Неужели ноликам не выдержать
этой атаки? На помощь ноликам при-
ходит возаюжность брать в качестве
плацдарма обороны стороны сколь
угодно большого квадрата. Возьмем
большой квадрат (гораздо больший,
чем на рисунке 9) и проведем в нем
квадрат, отстоящий от сторон перво-
го на шесть клеток. Центр квадрата
возьмем в той клетке, где был постав-
лен первый крестик. Пока крестики
будут находиться внутри меньшего
квадрата, сторонам квадрата лобовая
атака не угрожает и за то время, по-
ка крестики будут продвигаться к
стороне (или углу) внутреннего квад-
рата, нолики смогут укрепить свои
позиции в углах большого квадрата,
например, поставить в каждом углу
по И ноликов (рис. 9), тем самым
«атака на угол» будет лишена смыс-
ла, а атаку на сторону мы научи-
лись отбивать, если она начинается
с расстояния в шесть клеток от сторо-
ны. Чтобы поставить в каждом углу
по 11 ноликов (на самом деле можно
обойтись и меньшим числом), потре-
буется внутренний квадрат со сторо-
ной в 87 клеток, а следовательно,
внешний квадрат будет иметь сторо-
ну в 99 клеток.
Точно сформулировать «выигры-
вающую» стратегию ноликов и иссле-
довать другие варианты этой игры (на-
пример, выяснить, при каких ри <;
нолики не могут «запереть» крестики,
если за один ход ставится р крести-
ков и q ноликов) мы предоставляем
читателям.
Задачи
1. На сторонах А В. ВС,
СА треугольника ABC выб-
раны точки Г,, A,, Bt соот-
ветственно. Доказать, что ок-
ружности, описанные вокруг
треугольников ABC,, BCAt,
С А В,, пересекаются в одной
точке. Обобщить что утверж-
дение на случай шести точек,
выбранных на сторожах те-
траэдра.
2. Дан пятиугольник
ABCDF. Черен копны каж-
дой его стороны и точку пе-
ресечения двух соседних с
ней сторон проводят окруж-
ность. Доказать, что »тн ок-
ружности пересекаются в пя-
ти точкях (отличных от иер-
шин пятиугольника), лежа-
щих из одной окружности.
3. Через точку Р, лежащую
внутри угла ВАС. провести
две равные окружности, од-
на из которых касается пря-
мой АВ. а другая — пря-
мой АС.
4. Две окружности каса-
ются (с одной стороны) пря-
мой /в точке С. я прямая т
параллельна / и пересекает
обе окружности в точках S,
Т, X, У (последовательно).
Доказать, что точка С лежит
на биссектрисе одного из
двух углов, образованных па-
рами касательных к окруж-
ностям в точках S, Т или
Л. У.
5. Треугольник вписан в
окружность, причем квадра-
ты длин его сторон пропор-
циональны длинам перпен-
дикуляров, опущенных из
противоположных вершин на
фиксированную касательную
к окружности. Доказать, что
одна из сторон лежит на
диаметре окружности.
6. Две окружности радиу-
сов R и г расположены так,
что квадрат расстояния меж-
ду центрами окружностей ра-
вен R’1 \~\4Rr-\ г~. Доказать,
что существует бесконечно
много троек окружностей, ка-
сающихся попарно друг дру-
га и обеих данных окружно-
стей.
27 Окружение десанта
