Разделы 
Дополнительно
Задача по математике - 3323
2019-06-02 
Система укреплений состоит из блиндажей. Некоторые из блиндажей соединены траншеями, причем из любого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Назовем систему надежной, если у пушки нет гарантированной стратегии поражения пехотинца (т. е. такой последовательности выстрелов, благодаря которой пушка поразит пехотинца независимо от его начального местонахождения и последующих передвижений).
а) Докажите, что система укреплений, изображенная на рис., надежна.
б) Найдите все надежные системы укреплений, которые перестают быть надежными после разрушения любой из траншей.
Решение:
а) Докажем, что указанная в условии система укреплений (будем называть ее трилистником) надежна. Обозначим блиндажи, как показано на рис.
Ограничим начальные положения пехотинца блиндажами $O, A_2, B_2$ и $C_2$. При этом задача пушки упростится, но мы докажем, что пушка все равно не сможет накрыть пехотинца.
Эти блиндажи ($O, A_2, B_2$ и $C_2$) мы будем называть четными, а остальные - нечетными. Заметим, что из четного блиндажа пехотинец может перебежать только в нечетный, а из нечетного - только в четный. Поэтому перед выстрелами пушки с четными номерами пехотинец находится в нечетном блиндаже, а перед выстрелами с нечетными номерами - в четном. Значит, пушка должна наносить четные выстрелы по нечетным блиндажам, а нечетные - по четным.
Докажем, что перед каждым нечетным выстрелом пушки пехотинец может оказаться в $O$ и еще в одном из двух четных блиндажей (т. е. пушке неизвестно, в каком из этих трех блиндажей пехотинец).
Для доказательства проведем индукцию по количеству выстрелов. Действительно, вначале наше утверждение верно. Пусть перед $(2k - 1)$-м выстрелом пехотинец может оказаться в $O$ и еще двух четных блиндажах (например, в $A_2$ и $B_2$).
Рассмотрим $(2k - 1)$-й выстрел.
Случай 1: пусть он нанесен по блиндажу $O$, тогда перед следующим выстрелом пехотинец может оказаться в любом из блиндажей $A_1, A_3, B_1$ и $B_3$; $2k$-й выстрел должен быть нанесен по одному из нечетных блиндажей. Нетрудно видеть, что в любом случае перед $(2k + 1)$-м выстрелом пехотинец может снова оказаться в любом из блиндажей $O, A_2, B_2$.
Случай 2: пусть $(2k - 1)$-й выстрел нанесен по блиндажу $A_2$. Тогда перед следующим выстрелом пехотинец может оказаться в любом из блиндажей $A_1, B_1, C_1$ и $B_3$. Если $2k$-й выстрел нанесен по блиндажу $A_1$, то перед $(2к + 1)$-м выстрелом пехотинец может оказаться в $O, B_2$ и $C_2$, если по $B_1$, то в $O, A_2$ и $C_2$, если по $C_1$, то в $O, A_2$ и $B_2$. Если пушка стреляет по одному из блиндажей $A_3, B_3, C_3$, то пехотинец может оказаться в любом из четырех блиндажей. В любом случае перед $(2к + 1)$-м выстрелом пехотинец может оказаться в $O$ и еще двух четных блиндажах, так что в случае 2 наше утверждение доказано.
Случай 3: пусть $(2к - 1)$-й выстрел нанесен по блиндажу $B_2$. Этот случай полностью аналогичен предыдущему.
Случай 4: пусть $(2к - 1)$-й выстрел нанесен по блиндажу $C_2$. Тогда перед следующим выстрелом пехотинец может оказаться в любом из блиндажей $A_1, A_3, B_1$ и $B_3$, и этот случай аналогичен случаю 1.
Итак, перед каждым нечетным выстрелом пехотинец может оказаться в нескольких разных блиндажах, так что пушка не сможет его накрыть. Из предыдущего перебора видно, что пушка не может накрыть его и четным выстрелом.
б) Если в системе есть цикл из нескольких блиндажей $A_1 - A_2 - \cdots - A_n - A_1$, то такая система укреплений надежна. Ведь пехотинец, перебегая только по этому циклу, каждый раз может выбирать тот из двух доступных ему блиндажей, который не будет накрыт следующим выстрелом.
Заметим, что если какая-то часть системы укреплений сама по себе надежна, то пехотинец может спасаться только в этой части, таким образом, и вся система надежна. Поэтому, если кроме цикла $A_1-A_2-\cdots-A_n-A_1$ имеются другие траншеи, то такая система уже не минимальна. Покажем, что любой цикл минимален. Разрушив, скажем, траншею $A_n - A_1$, мы получим линейный лабиринт $A_1-A_2- \cdots -A_n$. Вот как должна действовать пушка. Она последовательно стреляет по блиндажам $A_2, A_3, \cdots, A_n$. Если сначала пехотинец был в блиндаже с четным номером, то один из этих выстрелов его накроет (докажите!). Если же этого не произошло, то пушка производит еще одну серию выстрелов, начиная с блиндажа $A_1$ или $A_2$ и последовательно перемещаясь по возрастанию номера блиндажа. То, с какого блиндажа она начинает вторую серию, зависит от четности номера блиндажа, в котором в этот момент находится пехотинец (это легко вычислить, так как сначала номер был нечетен и после каждого перебегания четность номера меняется).
Осталось рассмотреть системы укреплений без циклов. Покажем, что единственная минимальная надежная среди них - это трилистник. Возьмем любую систему, не содержащую ни цикла, ни трилистника, и укажем, как должна действовать пушка. (Мы опишем стратегию для связной системы. Если же система несвязна, т. е. состоит из нескольких участков, не связанных между собой траншеями, то пушка должна последовательно реализовать эту стратегию для каждого участка.)
Назовем блиндаж перекрестком, если из него выходят три или более траншеи. Траншею, ведущую из блиндажа, назовем сквозной, если, пробежав через нее, пехотинец может перебежать еще два раза, не побывав дважды ни в одном блиндаже. Например, в трилистнике траншея $A_1 - A_2$, ведущая из блиндажа $A_1$, не сквозная, а траншея $A_2 - A_1$ из $A_2$ сквозная. Наконец, блиндаж назовем тупиковым, если из него ведет единственная траншея.
Так как наша система не содержит трилистника и циклов, из любого блиндажа выходит не более двух сквозных траншей. Определим, откуда пушка начнет атаку. Возьмем любой перекресток. Если из него ведут две сквозные траншеи, причем каждая ведет к другому перекрестку, то выберем одну из них и проследуем через нее до ближайшего перекрестка. Если из этого нового перекрестка выходит еще одна сквозная траншея, ведущая к перекрестку, перейдем по этой траншее до следующего ближайшего перекрестка. Действуем так, пока не придем к перекрестку с единственной выходящей из него сквозной траншеей или с двумя, через одну из которых можно дойти до тупикового блиндажа, не проходя ни одного перекрестка. В первом случае пройдем по любой несквозной траншее в соседний блиндаж, во втором - пройдем по этой самой сквозной траншее до блиндажа, соседнего с тупиковым. Таким образом, мы определили, с какого блиндажа начать обстрел.
Разобьем блиндажи на четные и нечетные так, что пехотинец каждый раз перебегает из блиндажа одной четности в блиндаж другой четности (это возможно, поскольку циклов в системе нет). Покажем, как нужно стрелять, чтобы гарантированно поразить пехотинца при условии, что он изначально находится в блиндаже той же четности, что и блиндаж, с которого начнется обстрел. (Если, сделав все эти выстрелы, пушка так и не накроет пехотинца, значит, он находился в блиндаже другой четности; теперь уже точно известна четность блиндажа с пехотинцем.)
Пусть пушка последовательно поразит блиндажи, начиная с выбранного и заканчивая перекрестком. Тогда на обстрелянном линейном участке системы пехотинца нет. Мы так выбрали начальный блиндаж, чтобы среди траншей, ведущих в другие участки системы, было не более одной сквозной. (Если всего их две, то вторая ведет в только что обстрелянный участок.) Любая несквозная траншея ведет либо в тупиковый блиндаж, либо в блиндаж, из которого можно попасть в несколько тупиковых или же вернуться на перекресток. В обоих случаях за этой траншеей всего один блиндаж четности, противоположной четности рассматриваемого перекрестка. После того как пушка накрыла перекресток, пехотинец перебежал как раз в блиндаж, четность которого противоположна четности перекрестка, так что если он находится за этой траншеей, то, ударив по блиндажу, в который ведет эта траншея, пушка поразит пехотинца. Если же нет, пушка снова бьет по перекрестку, не давая пехотинцу пробежать на уже проверенные участки системы укреплений. Проверив все несквозные траншеи, пушка приступает к единственной сквозной, поражает блиндаж, в который ведет эта траншея, и далее последовательно все блиндажи до ближайшего перекрестка. Там повторяется проверка несквозных проходов и т. д. Так можно проверить всю систему.
Тем самым, любая система, не содержащая ни циклов, ни трилистника, ненадежна. Разрушив любую траншею в трилистнике, мы получим ненадежную систему, так что трилистник является минимальной надежной системой. Наконец, любая система, состоящая из трилистника и чего-то еще, надежна, но не минимальна.
Система укреплений состоит из блиндажей. Некоторые из блиндажей соединены траншеями, причем из любого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Назовем систему надежной, если у пушки нет гарантированной стратегии поражения пехотинца (т. е. такой последовательности выстрелов, благодаря которой пушка поразит пехотинца независимо от его начального местонахождения и последующих передвижений).
а) Докажите, что система укреплений, изображенная на рис., надежна.
б) Найдите все надежные системы укреплений, которые перестают быть надежными после разрушения любой из траншей.
Решение:
а) Докажем, что указанная в условии система укреплений (будем называть ее трилистником) надежна. Обозначим блиндажи, как показано на рис.
Ограничим начальные положения пехотинца блиндажами $O, A_2, B_2$ и $C_2$. При этом задача пушки упростится, но мы докажем, что пушка все равно не сможет накрыть пехотинца.
Эти блиндажи ($O, A_2, B_2$ и $C_2$) мы будем называть четными, а остальные - нечетными. Заметим, что из четного блиндажа пехотинец может перебежать только в нечетный, а из нечетного - только в четный. Поэтому перед выстрелами пушки с четными номерами пехотинец находится в нечетном блиндаже, а перед выстрелами с нечетными номерами - в четном. Значит, пушка должна наносить четные выстрелы по нечетным блиндажам, а нечетные - по четным.
Докажем, что перед каждым нечетным выстрелом пушки пехотинец может оказаться в $O$ и еще в одном из двух четных блиндажей (т. е. пушке неизвестно, в каком из этих трех блиндажей пехотинец).
Для доказательства проведем индукцию по количеству выстрелов. Действительно, вначале наше утверждение верно. Пусть перед $(2k - 1)$-м выстрелом пехотинец может оказаться в $O$ и еще двух четных блиндажах (например, в $A_2$ и $B_2$).
Рассмотрим $(2k - 1)$-й выстрел.
Случай 1: пусть он нанесен по блиндажу $O$, тогда перед следующим выстрелом пехотинец может оказаться в любом из блиндажей $A_1, A_3, B_1$ и $B_3$; $2k$-й выстрел должен быть нанесен по одному из нечетных блиндажей. Нетрудно видеть, что в любом случае перед $(2k + 1)$-м выстрелом пехотинец может снова оказаться в любом из блиндажей $O, A_2, B_2$.
Случай 2: пусть $(2k - 1)$-й выстрел нанесен по блиндажу $A_2$. Тогда перед следующим выстрелом пехотинец может оказаться в любом из блиндажей $A_1, B_1, C_1$ и $B_3$. Если $2k$-й выстрел нанесен по блиндажу $A_1$, то перед $(2к + 1)$-м выстрелом пехотинец может оказаться в $O, B_2$ и $C_2$, если по $B_1$, то в $O, A_2$ и $C_2$, если по $C_1$, то в $O, A_2$ и $B_2$. Если пушка стреляет по одному из блиндажей $A_3, B_3, C_3$, то пехотинец может оказаться в любом из четырех блиндажей. В любом случае перед $(2к + 1)$-м выстрелом пехотинец может оказаться в $O$ и еще двух четных блиндажах, так что в случае 2 наше утверждение доказано.
Случай 3: пусть $(2к - 1)$-й выстрел нанесен по блиндажу $B_2$. Этот случай полностью аналогичен предыдущему.
Случай 4: пусть $(2к - 1)$-й выстрел нанесен по блиндажу $C_2$. Тогда перед следующим выстрелом пехотинец может оказаться в любом из блиндажей $A_1, A_3, B_1$ и $B_3$, и этот случай аналогичен случаю 1.
Итак, перед каждым нечетным выстрелом пехотинец может оказаться в нескольких разных блиндажах, так что пушка не сможет его накрыть. Из предыдущего перебора видно, что пушка не может накрыть его и четным выстрелом.
б) Если в системе есть цикл из нескольких блиндажей $A_1 - A_2 - \cdots - A_n - A_1$, то такая система укреплений надежна. Ведь пехотинец, перебегая только по этому циклу, каждый раз может выбирать тот из двух доступных ему блиндажей, который не будет накрыт следующим выстрелом.
Заметим, что если какая-то часть системы укреплений сама по себе надежна, то пехотинец может спасаться только в этой части, таким образом, и вся система надежна. Поэтому, если кроме цикла $A_1-A_2-\cdots-A_n-A_1$ имеются другие траншеи, то такая система уже не минимальна. Покажем, что любой цикл минимален. Разрушив, скажем, траншею $A_n - A_1$, мы получим линейный лабиринт $A_1-A_2- \cdots -A_n$. Вот как должна действовать пушка. Она последовательно стреляет по блиндажам $A_2, A_3, \cdots, A_n$. Если сначала пехотинец был в блиндаже с четным номером, то один из этих выстрелов его накроет (докажите!). Если же этого не произошло, то пушка производит еще одну серию выстрелов, начиная с блиндажа $A_1$ или $A_2$ и последовательно перемещаясь по возрастанию номера блиндажа. То, с какого блиндажа она начинает вторую серию, зависит от четности номера блиндажа, в котором в этот момент находится пехотинец (это легко вычислить, так как сначала номер был нечетен и после каждого перебегания четность номера меняется).
Осталось рассмотреть системы укреплений без циклов. Покажем, что единственная минимальная надежная среди них - это трилистник. Возьмем любую систему, не содержащую ни цикла, ни трилистника, и укажем, как должна действовать пушка. (Мы опишем стратегию для связной системы. Если же система несвязна, т. е. состоит из нескольких участков, не связанных между собой траншеями, то пушка должна последовательно реализовать эту стратегию для каждого участка.)
Назовем блиндаж перекрестком, если из него выходят три или более траншеи. Траншею, ведущую из блиндажа, назовем сквозной, если, пробежав через нее, пехотинец может перебежать еще два раза, не побывав дважды ни в одном блиндаже. Например, в трилистнике траншея $A_1 - A_2$, ведущая из блиндажа $A_1$, не сквозная, а траншея $A_2 - A_1$ из $A_2$ сквозная. Наконец, блиндаж назовем тупиковым, если из него ведет единственная траншея.
Так как наша система не содержит трилистника и циклов, из любого блиндажа выходит не более двух сквозных траншей. Определим, откуда пушка начнет атаку. Возьмем любой перекресток. Если из него ведут две сквозные траншеи, причем каждая ведет к другому перекрестку, то выберем одну из них и проследуем через нее до ближайшего перекрестка. Если из этого нового перекрестка выходит еще одна сквозная траншея, ведущая к перекрестку, перейдем по этой траншее до следующего ближайшего перекрестка. Действуем так, пока не придем к перекрестку с единственной выходящей из него сквозной траншеей или с двумя, через одну из которых можно дойти до тупикового блиндажа, не проходя ни одного перекрестка. В первом случае пройдем по любой несквозной траншее в соседний блиндаж, во втором - пройдем по этой самой сквозной траншее до блиндажа, соседнего с тупиковым. Таким образом, мы определили, с какого блиндажа начать обстрел.
Разобьем блиндажи на четные и нечетные так, что пехотинец каждый раз перебегает из блиндажа одной четности в блиндаж другой четности (это возможно, поскольку циклов в системе нет). Покажем, как нужно стрелять, чтобы гарантированно поразить пехотинца при условии, что он изначально находится в блиндаже той же четности, что и блиндаж, с которого начнется обстрел. (Если, сделав все эти выстрелы, пушка так и не накроет пехотинца, значит, он находился в блиндаже другой четности; теперь уже точно известна четность блиндажа с пехотинцем.)
Пусть пушка последовательно поразит блиндажи, начиная с выбранного и заканчивая перекрестком. Тогда на обстрелянном линейном участке системы пехотинца нет. Мы так выбрали начальный блиндаж, чтобы среди траншей, ведущих в другие участки системы, было не более одной сквозной. (Если всего их две, то вторая ведет в только что обстрелянный участок.) Любая несквозная траншея ведет либо в тупиковый блиндаж, либо в блиндаж, из которого можно попасть в несколько тупиковых или же вернуться на перекресток. В обоих случаях за этой траншеей всего один блиндаж четности, противоположной четности рассматриваемого перекрестка. После того как пушка накрыла перекресток, пехотинец перебежал как раз в блиндаж, четность которого противоположна четности перекрестка, так что если он находится за этой траншеей, то, ударив по блиндажу, в который ведет эта траншея, пушка поразит пехотинца. Если же нет, пушка снова бьет по перекрестку, не давая пехотинцу пробежать на уже проверенные участки системы укреплений. Проверив все несквозные траншеи, пушка приступает к единственной сквозной, поражает блиндаж, в который ведет эта траншея, и далее последовательно все блиндажи до ближайшего перекрестка. Там повторяется проверка несквозных проходов и т. д. Так можно проверить всю систему.
Тем самым, любая система, не содержащая ни циклов, ни трилистника, ненадежна. Разрушив любую траншею в трилистнике, мы получим ненадежную систему, так что трилистник является минимальной надежной системой. Наконец, любая система, состоящая из трилистника и чего-то еще, надежна, но не минимальна.
