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

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

Условие

Система укреплений состоит из блиндажей. Некоторые из блиндажей соединены траншеями, причём из каждого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Назовём систему надёжной, если у пушки нет гарантированной стратегии поражения пехотинца (то есть такой последовательности выстрелов, благодаря которой пушка поразит пехотинца независимо от его начального местонахождения и последующих передвижений).

  а) Докажите, что система укреплений, изображённая на рисунке, надёжна.
  б) Найдите все надёжные системы укреплений, которые перестают быть надёжными после разрушения любой из траншей.


Решение

  а) Обозначим блиндажи, как показано на рисунке. Ограничим начальные положения пехотинца блиндажами O, A2, B2 и C2 (эти блиндажи мы будем называть чётными, а остальные – нечётными). Мы считаем, что пехотинец настолько удачлив, что спасается, если только это возможно.

  Заметим, что выстрел пушки по одному из нечётных блиндажей заведомо бесполезен. Если пушка выстрелит по блиндажу O (удачливый пехотинец, конечно, не там), то из оставшихся трёх чётных блиндажей пехотинец сможет перебежать в любой из шести нечётных. Теперь, если пушка выстрелит по одному из этих нечётных блиндажей, то пехотинец из оставшихся пяти сможет перебежать в любой из четырёх чётных. Таким образом, повторится начальная расстановка.   Если же первым своим выстрелом пушка накроет один из чётных блиндажей на ветвях трилистника, скажем A2 (сначала блиндажи A2, B2 и C2 ничем друг от друга не отличаются), то пехотинец из оставшихся блиндажей O, B2 и C2 сможет перебежать в любой из блиндажей A1, B1, B3, C1, C3. Если после этого пушка стреляет не по блиндажу A1, то пехотинцу доступна любая из четырёх чётных вершин. Снова начальная ситуация. Если же второй выстрел пушка производит по A1, то из оставшихся четырёх блиндажей пехотинец сможет перебежать в блиндажи O, B2 и C2. Дальнейший перебор сведём в таблицу. В левом её столбце – блиндажи, по которым стреляет пушка, в правом – блиндажи, куда после этого может перебежать пехотинец. Горизонтальными линиями разделены различные варианты. Некоторые случаи не разобраны (про них написано "то же"). Это означает, что получается та же ситуация с точностью до перестановки ветвей. Каждый случай разбирается до повторения ситуации, которая уже встречалась.
  Итак, после каждого выстрела пехотинец может оказаться более чем в одном блиндаже. Так что у него каждый раз есть выбор, благодаря которому он спасётся. Поэтому система-трилистник надёжна.

  б) Если в системе есть цикл из нескольких блиндажей  A1-A2-...-An-A1,  то такая система укреплений надёжна. Ведь пехотинец, перебегая только по этому циклу, каждый раз может выбирать тот из двух доступных ему блиндажей, который не будет накрыт следующим выстрелом.
  Заметим, что если какая-то часть системы укреплений сама по себе надёжна, то пехотинец может спасаться только в этой части, таким образом и вся система надёжна. Поэтому, если кроме цикла  A1-A2-...-An-A1  имеются другие траншеи, то такая система уже не минимальна.
  Покажем, что любой цикл минимален. Разрушив, скажем, траншею  An-A1,  мы получим линейный лабиринт  A1-A2-...-An.  Вот как должна действовать пушка. Она последовательно стреляет по блиндажам A2, A3, ..., An.  Если сначала пехотинец был в блиндаже с чётным номером, то один из этих выстрелов его накроет. Если же этого не произошло, то пушка производит ещё одну серию выстрелов, начиная с блиндажа A1 или A2 и последовательно перемещаясь по возрастанию номера блиндажа. То, с какого блиндажа она начинает вторую серию, зависит от чётности номера блиндажа, в котором в этот момент находится пехотинец (это легко вычислить, так как сначала номер был нечётен и после каждого перебегания чётность номера меняется).
  Осталось рассмотреть системы укреплений без циклов. Покажем, что единственная минимальная надёжная среди них – это трилистник. Возьмём любую систему, не содержащую ни цикла, ни трилистника, и укажем, как должна действовать пушка. (Мы опишем стратегию для связной системы. Если же система несвязна, то есть состоит из нескольких участков, не связанных между собой траншеями, то пушка должна последовательно реализовать эту стратегию для каждого участка.)
  Назовём блиндаж перекрёстком, если из него выходят три или более траншеи. Траншею, ведущую из блиндажа, назовём сквозной, если, пробежав через неё, пехотинец может перебежать ещё два раза, не побывав дважды ни в одном блиндаже. Например, в трилистнике траншея A1A2, ведущая из блиндажа A1, не сквозная, а траншея A2A1 из A2 сквозная. Наконец, блиндаж назовём тупиковым, если из него ведёт единственная траншея. Так как наша система не содержит трилистника, из любого блиндажа выходит не более двух сквозных траншей.
  Возьмём любой перекрёсток. Если из него ведут две сквозные траншеи, причём каждая ведёт к другому перекрёстку, то выберем одну из них и проследуем через неё до ближайшего перекрёстка. Если из этого нового перекрёстка выходит ещё одна сквозная траншея, ведущая к перекрёстку, перейдём по этой траншее до следующего ближайшего перекрёстка. Действуем так, пока не придём к перекрёстку с единственной выходящей из него сквозной траншеей или с двумя, через одну из которых можно дойти до тупикового блиндажа, не проходя ни одного перекрёстка. В первом случае пройдём по любой несквозной траншее в соседний блиндаж, во втором – пройдём по этой сквозной траншее до блиндажа, соседнего с тупиковым. Таким образом мы определили, с какого блиндажа начать обстрел.
  Разобьём блиндажи на чётные и нечётные, так что пехотинец каждый раз перебегает из блиндажа одной чётности в блиндаж другой чётности (это возможно, поскольку циклов в системе нет). Покажем, как нужно стрелять, чтобы гарантированно поразить пехотинца при условии, что он изначально находится в блиндаже той же чётности, что и блиндаж, с которого начнётся обстрел. (Если, сделав все эти выстрелы, пушка так и не накроет пехотинца, значит, он находился в блиндаже другой чётности; теперь уже точно известна чётность блиндажа с пехотинцем.) Пусть пушка последовательно поразит блиндажи, начиная с выбранного и заканчивая перекрёстком. Тогда на обстрелянном линейном участке системы пехотинца нет. Мы так выбрали начальный блиндаж, чтобы среди траншей, ведущих в другие участки системы, было не более одной сквозной. (Если всего их две, то вторая ведёт в только что обстрелянный участок.) Любая несквозная траншея ведёт либо в тупиковый блиндаж, либо в блиндаж, из которого можно попасть в несколько тупиковых или же вернуться на перекрёсток. В обоих случаях за этой траншеей всего один блиндаж чётности, противоположной чётности рассматриваемого перекрёстка. После того как пушка накрыла перекрёсток, пехотинец перебежал как раз в блиндаж, чётность которого противоположна чётности перекрёстка, так что если он находится за этой траншеей, то, ударив по блиндажу, в который ведёт эта траншея, пушка поразит пехотинца. Если же нет, пушка снова бьёт по перекрёстку, не давая пехотинцу пробежать на уже проверенные участки системы укреплений. Проверив все несквозные траншеи, пушка приступает к единственной сквозной, поражает блиндаж, в который ведёт эта траншея, и далее последовательно все блиндажи до ближайшего перекрёстка. Там повторяется проверка несквозных проходов и т. д. Так можно проверить всю систему.
  Тем самым, любая система, не содержащая ни циклов, ни трилистника, ненадёжна. Разрушив любую траншею в трилистнике, мы получим ненадёжную систему, так что трилистник является минимальной надёжной системой. Наконец, любая система, состоящая из трилистника и чего-то ещё, надёжна, но не минимальна.


Ответ

Это трилистник и все системы, состоящие только из одного цикла блиндажей A1-A2-...-An-A1.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 63
Год 2000
вариант
Класс 9
задача
Номер 6

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

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