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