Тургор(осенний) 2024, 10-11, 6 задача.
Замок Мерлина состоит из 100 комнат и 1000 коридоров. Каждый коридор соединяет какие-то две комнаты, каждые две комнаты соединены не более чем одним коридором. Мерлин выдал мудрецам план замка и объявил испытание. Мудрецы должны будут распределиться по комнатам, как хотят. Далее каждую минуту Мерлин указывает коридор, и один из мудрецов переходит по нему из комнаты на любом его конце в комнату на другом его конце. Мерлин победит, если когда-то укажет коридор, на концах которого нет мудрецов. Число m назовём волшебным числом замка, если m мудрецов могут, сговорившись перед испытанием, действовать так, чтобы никогда не проиграть, причём m — минимальное такое число. Чему может равняться волшебное число замка? (Все, включая Мерлина, всегда знают расположение всех мудрецов.)
Подсказка
- Нужно делать по индукции.
- Пусть из каждой комнаты, при наличии в ней нескольких людей выходит «самый старший».
- Добейтесь сначала одной пустой комнаты, а затем смотрите на коридоры из неё.
Решение
Ответ: m = 1000. Сначала докажем, что 1000 мудрецов всегда смогут выдержать испытание, независимо от того, как располагаются комнаты и коридоры в замке. Для этого мудрецы договариваются о следующем: каждый коридор закрепляется за каким-то конкретным мудрецом, который всегда находится в одной из комнат на концах этого коридора и переходит по нему, когда на этот коридор указывает Мерлин. Отсюда следует, что m ≤ 1000. Докажем, что m ≥ 1000.
Покажем, что при 999 мудрецах у Мерлина есть план победы. Для удобства предположим, что если мудрец выходит из комнаты, то он – самый младший из тех, кто в ней находился (в действительности совершенно неважно, кто из мудрецов где, важно только их количество в каждой из комнат).
Докажем, что если мудрецов в замке меньше, чем коридоров, то Мерлин может выбирать коридоры так, чтобы через несколько ходов вне зависимости от действий мудрецов образовался пустой коридор (обе комнаты на его концах пустые).
Индукция по числу мудрецов. База индукции очевидна: если коридоры есть, а мудрецов нет, то есть пустой коридор.
Переход индукции. Сначала покажем, что Мерлин может получить одну пустую комнату, из которой ведёт хотя бы один коридор. Возьмём самого старшего мудреца M. Если в результате команд Мерлина мудрец M покидает свою комнату, то эта комната становится пустой и будет искомой. Поэтому мы можем считать, что M всегда остаётся на своём месте вне зависимости от действий Мерлина.
Наденем на M мантию-невидимку, по предположению индукции, Мерлин может получить две соседние комнаты, в которых никого нет (кроме, возможно, M). Таким образом, получена пустая комната, из которой ведёт хотя бы один коридор. Пусть есть пустая комната v. Пусть из неё выходят коридоры e1, . . . , ek и ведут в комнаты v1, . . . , vk. Назовём эти k комнат уютными, а эти k коридоров опасными. Если среди уютных комнат есть пустая, то Мерлин уже победил. Иначе выберем в этих комнатах по мудрецу (мудрец Mi находится в комнате vi), назовём их важными. Не теряя общности, мы можем считать, что k самых пожилых мудрецов – это важные мудрецы.
Запретим Мерлину выбирать опасные коридоры и наденем на важных мудрецов по мантии-невидимке (то есть, мысленно удалим из замка k важных мудрецов и k коридоров вместе с вершиной v). По предположению индукции, у видимых мудрецов нет стратегии защиты от Мерлина. Это значит, что Мерлин может выбирать коридоры таким образом, что в исходном замке в какой-то момент или образуется пустой коридор, или один из важных мудрецов Mi должен будет выйти из своей комнаты vi. В последнем случае в этот момент Мерлин получит две соседние пустые комнаты (vi, v).