admin

Задача 00014

от

Тургор(осенний) 2024, 10-11, 6 задача.

Замок Мерлина состоит из 100 комнат и 1000 коридоров. Каждый коридор соединяет какие-то две комнаты, каждые две комнаты соединены не более чем одним коридором. Мерлин выдал мудрецам план замка и объявил испытание. Мудрецы должны будут распределиться по комнатам, как хотят. Далее каждую минуту Мерлин указывает коридор, и один из мудрецов переходит по нему из комнаты на любом его конце в комнату на другом его конце. Мерлин победит, если когда-то укажет коридор, на концах которого нет мудрецов. Число m назовём волшебным числом замка, если m мудрецов могут, сговорившись перед испытанием, действовать так, чтобы никогда не проиграть, причём m — минимальное такое число. Чему может равняться волшебное число замка? (Все, включая Мерлина, всегда знают расположение всех мудрецов.)

Подсказка
  1. Нужно делать по индукции.
  2. Пусть из каждой комнаты, при наличии в ней нескольких людей выходит «самый старший».
  3. Добейтесь сначала одной пустой комнаты, а затем смотрите на коридоры из неё.

Решение

Ответ: 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).

LaTeX DEMO

от


At first, we sample f(x) in the N (N is odd) equidistant points around x^*:

    \[ f_k = f(x_k),\: x_k = x^*+kh,\: k=-\frac{N-1}{2},\dots,\frac{N-1}{2} \]

where h is some step. Then we interpolate points \{(x_k,f_k)\} by polynomial

(1)   \begin{equation*} P_{N-1}(x)=\sum_{j=0}^{N-1}{a_jx^j} \end{equation*}

Its coefficients \{a_j\} are found as a solution of system of linear equations:

(2)   \begin{equation*} \left\{ P_{N-1}(x_k) = f_k\right\},\quad k=-\frac{N-1}{2},\dots,\frac{N-1}{2} \end{equation*}

Here are references to existing equations: (1), (2). Here is reference to non-existing equation (??).

Задача 00012

от

а) В группе из четырёх человек, говорящих на разных языках, любые трое могут общаться (возможно, один переводит двум другим).
Доказать, что их можно разбить на пары, в каждой из которых имеется общий язык.
б) То же для группы из 100 человек.
в) То же для группы из 102 человек.

Решение

  а) Рассмотрим граф с четырьмя вершинами A, B, C, D, соответствующими людям, и соединим ребрами людей, знающих общий язык. Условие означает, что каждая тройка вершин соединена хотя бы двумя рёбрами. А доказать нужно, что есть два ребра без общих вершин. Пусть это неверно.
  Первый способ. Если в тройке  (A, B, C)  проведены рёбра AB и AC, то рёбер BD и CD нет. Но тогда в тройке  (B, C, D)  не больше одного ребра. Противоречие.
  Второй способ. Всего есть 4 тройки. Каждое ребро входит в две тройки. Следовательно, рёбер не менее  4·2 : 2 = 4.  С другой стороны, каждому ребру соответствует отсутствующее «противоположное» ребро. Следовательно, рёбер не более трёх. Противоречие.

  в) Отделим двух человек, говорящих на одном языке, а остальных разобьём на четвёрки. Согласно а) каждую четвёрку можно разбить на две пары с общим языком.

Задача 00011

от

Посёлок построен в виде квадрата 3 квартала на 3 квартала (кварталы – квадраты со стороной b, всего 9 кварталов). Какой наименьший путь должен пройти асфальтоукладчик, чтобы заасфальтировать все улицы, если он начинает и кончает свой путь в угловой точке A? (Стороны квадрата – тоже улицы).

Решение

Всего есть 24 отрезка (улицы) длины b, по которым должен проехать асфальтоукладчик. К восьми перекрёсткам подходит нечётное число таких отрезков. По одному из отрезков, подходящему к такому перекрёстку, асфальтоукладчику придётся проехать дважды. Поскольку отрезок соединяет два перекрёстка, лишних проездов не меньше  8 : 2 = 4.  Итого весь путь составит не меньше  24b + 4b = 28b.
  Пример на рисунке показывает, что путь такой длины возможен.

Задача 00010

от

В одной из вершин  а) октаэдра;  б) куба сидит муха. Может ли она проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину?

Решение

а) Пусть, A, B, C, A1, B1, C1 – вершины октаэдра, причём  (A, A1),  (B, B1)  и  (B, B1) – пары противоположных вершин. Тогда любая пара вершин, кроме этих трёх, соединяется ребром. Путь мухи может быть следующим:  ABA1C1BCAC1B1CA1B1A  (см. рис.)

б) В каждой из восьми вершин куба сходится по три ребра. Это означает, что степень каждой вершины полученного графа нечётна, значит, путешествие совершить невозможно.

Задача 00009

от

Какое наибольшее число клеток доски 9×9 можно разрезать по обеим диагоналям, чтобы при этом доска не распалась на несколько частей?

Решение

Пусть разрезано k клеток. Рассмотрим граф, рёбрами которого являются половинки проведённых диагоналей, а вершинами – вершины и центры разрезанных клеток.
Поскольку граничные клетки доски, очевидно, разрезать нельзя, то в полученном графе не более 64 + k вершин и 4k рёбер. Согласно формуле Эйлера (64 + k) – 4k + 1 ≥ 2, то есть k ≤ 21.
Пример с 21 разрезанной клеткой см. на рисунке.

Задача 00008

от

Семиугольник разбит на выпуклые пяти- и шестиугольники, причём так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

Решение

Рассмотрим полученную картинку как плоский граф. Так как из каждой вершины выходит не менее трёх рёбер, то  E ≥ 3V/2.  Подставив в формулу Эйлера, получим  2 = V – E + F ≤ 2E/3 – E + F = F – E/3,  то есть  E ≤ 3F – 6.
  Обозначим количество пятиугольников через a, количество шестиугольников через b. Заметим, что  5a + 6b + 7 = 2E ≤ 6F – 12 = 6(a + b + 1) – 12.  Отсюда  a ≥ 13.

Задача 00006

от

Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток.
Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?

Решение

Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а рёбрами – верёвочки. В этом графе нужно удалить как можно больше рёбер так, чтобы он остался связным. Будем убирать рёбра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число рёбер в нашем графе в этот момент. Количество вершин осталось тем же –  51·601 = 30651.  Число рёбер в дереве на единицу меньше (см. задачу 31098 б), то есть их 30650. Сначала же их было  601·50 + 600·51 = 60650.  Таким образом, можно удалить 30000 рёбер (но не более!).

Задача 00007

от

Дан отрезок OA. Из конца отрезка A выходит 5 отрезков AB1, AB2, AB3, AB4, AB5. Из каждой точки Bi могут выходить ещё пять новых отрезков или ни одного нового отрезка и т.д. Может ли число свободных концов построенных отрезков равняться 1001? Под свободным концом отрезка понимаем точку, принадлежащую только одному отрезку (кроме точки O).

Решение

При проведении пяти отрезков из конца отрезка появляются 5 новых свободных концов и пропадает один старый. В результате число свободных концов увеличивается на 4. Поэтому если пятёрки отрезков проведены k раз, то число свободных концов равно  4k + 1.  При  k = 250  получаем нужное число свободных концов.

Задача 00005

от

Имеются две страны: Обычная и Зазеркалье. У каждого города в Обычной стране есть «двойник» в Зазеркалье, и наоборот. Однако если в Обычной стране какие-то два города соединены железной дорогой, то в Зазеркалье эти города не соединены, а каждые два несоединённых в Обычной стране города обязательно соединены железной дорогой в Зазеркалье. В Обычной стране девочка Алиса не может проехать из города A в город B, сделав менее двух пересадок. Доказать, что Алиса в Зазеркалье сможет проехать из любого города в любой другой, сделав не более двух пересадок.

Решение

Из условия следует, что города A и B в Обычной стране не соединены дорогой и что любой другой город в Обычной стране не соединён либо с A, либо с B. Значит, двойники A’ и B’ городов A и B в Зазеркалье соединены дорогой, а каждый другой город Зазеркалья соединён либо с A’, либо с B’. Следовательно, в Зазеркалье из каждого города можно доехать до одного из городов A’ и B’, затем при необходимости доехать до второго из них, а после доехать до любого другого города Зазеркалья. При этом требуется не более двух пересадок.