Задача 67496
|
|
 |
Условие
Замок Мерлина состоит из 100 комнат и 1000 коридоров. Каждый коридор соединяет какие-то две комнаты, каждые две комнаты соединены не более чем одним коридором. Мерлин выдал мудрецам план замка и объявил испытание. Мудрецы должны будут распределиться по комнатам, как хотят. Далее каждую минуту Мерлин указывает коридор, и один из мудрецов переходит по нему из комнаты на любом его конце в комнату на другом его конце. Мерлин победит, если когда-то укажет коридор, на концах которого нет мудрецов.Число $m$ назовём волшебным числом замка, если $m$ мудрецов могут, сговорившись перед испытанием, действовать так, чтобы никогда не проиграть, причём $m$ — минимальное такое число. Чему может равняться волшебное число замка? (Все, включая Мерлина, всегда знают расположение всех мудрецов.)
Решение 1
Сначала докажем, что 1000 мудрецов всегда смогут выдержать испытание, независимо от того, как располагаются комнаты и коридоры в замке. Для этого мудрецы договариваются о следующем: каждый коридор закрепляется за каким-то конкретным мудрецом, который всегда находится в одной из комнат на концах этого коридора и переходит по нему, когда на этот коридор указывает Мерлин. Отсюда следует, что $m\leqslant 1000$. Докажем, что $m\geqslant 1000$.Покажем, что при 999 мудрецах у Мерлина есть план победы. Для удобства предположим, что если мудрец выходит из комнаты, то он — самый младший из тех, кто в ней находился (в действительности совершенно неважно, кто из мудрецов где, важно только их количество в каждой из комнат).
Докажем, что если мудрецов в замке меньше, чем коридоров, то Мерлин может выбирать коридоры так, чтобы через несколько ходов вне зависимости от действий мудрецов образовался пустой коридор (обе комнаты на его концах пустые). Индукция по числу мудрецов. База индукции очевидна: если коридоры есть, а мудрецов нет, то есть пустой коридор.
Переход индукции. Сначала покажем, что Мерлин может получить одну пустую комнату, из которой ведёт хотя бы один коридор. Возьмём самого старшего мудреца $M$. Если в результате команд Мерлина мудрец $M$ покидает свою комнату, то эта комната становится пустой и будет искомой. Поэтому мы можем считать, что $M$ всегда остаётся на своём месте вне зависимости от действий Мерлина. Наденем на $M$ мантию-невидимку, по предположению индукции, Мерлин может получить две соседние комнаты, в которых никого нет (кроме, возможно, $M$). Таким образом, получена пустая комната, из которой ведёт хотя бы один коридор.
Пусть есть пустая комната $v$. Пусть из неё выходят коридоры $e_1, \dots,e_k$ и ведут в комнаты $v_1,\dots, v_k$. Назовём эти $k$ комнат уютными, а эти $k$ коридоров опасными. Если среди уютных комнат есть пустая, то Мерлин уже победил. Иначе выберем в этих комнатах по мудрецу (мудрец $M_i$ находится в комнате $v_i$), назовём их важными. Не теряя общности, мы можем считать, что $k$ самых пожилых мудрецов — это важные мудрецы. Запретим Мерлину выбирать опасные коридоры и наденем на важных мудрецов по мантии-невидимке (то есть, мысленно удалим из замка $k$ важных мудрецов и $k$ коридоров вместе с вершиной $v$). По предположению индукции, у видимых мудрецов нет стратегии защиты от Мерлина. Это значит, что Мерлин может выбирать коридоры таким образом, что в исходном замке в какой-то момент или образуется пустой коридор, или один из важных мудрецов $M_i$ должен будет выйти из своей комнаты $v_i$. В последнем случае в этот момент Мерлин получит две соседние пустые комнаты $(v_i, v)$.
Решение 2
Доказать, что $m \geqslant 1000$, можно и другим способом.Занумеруем все комнаты от 1 до $n$ в любом порядке. Пусть $A_i$ — число мудрецов в комнате $i$, а $k_i$ — число коридоров, ведущих из неё в комнаты с меньшими номерами.
Если $A_i < k_i$ для какой-то комнаты $i$, то Мерлин указывает эти $k_i$ коридоров в порядке убывания номеров их концов до момента, когда случится переход мудреца в комнату $i$ из некоторой комнаты $j$ (где $j < i$). Получится расположение мудрецов $B = (B_1, \ldots, B_n)$, лексикографически меньшее расположения $A$, то есть $B_1 = A_1$, ..., $B_{j-1} = A_{j-1}$, но $B_j < A_j$.
Затем Мерлин ищет в расположении $B$ неравенство $B_l < k_l$, аналогично получает меньшее расположение и так далее. Число расположений конечно. Значит, если мудрецы не проиграют в этом процессе, то когда-то получится расположение $M$, в котором $M_i\geqslant k_i$ для всех $i$. Тогда $$m \geqslant M_1 + \ldots + M_n \geqslant k_1 + \ldots + k_n = 1000,$$ то есть $m \geqslant 1000$.
