|
|
 |
Условие
В королевстве 16 городов. Король хочет построить такую систему дорог, чтобы
из каждого города можно было попасть в каждый, минуя не более одного
промежуточного города, и чтобы из каждого города выходило не более пяти дорог.
а) Докажите, что это возможно.
б) Докажите, что если в формулировке заменить число 5 на число 4,
то желание короля станет неосуществимым.
Решение
а) В качестве примера достаточно рассмотреть четырёхмерный куб: расположим города в его вершинах, а дороги проведём по ребрам и главным диагоналям. Другими словами, занумеруем города четырёхзначными двоичными числами от 0000 до 1111 и проведём дороги между городами, номера которых различаются ровно в одном разряде, и между городами, номера которых различаются во всех разрядах.
б) Предположим, что такая система дорог построена. Рисунок слева показывает, что если из города выходит не более трёх дорог, то из него можно попасть максимум в 12 городов. Значит, из каждого города выходит ровно четыре дороги. Рисунок справа показывает, что если три дороги образуют треугольник, то из города в его вершине можно попасть не более чем в 14 других городов.
Рассмотрим произвольный город A. Как показано выше, из него выходят четыре дороги – в города B, C, D, E, а из них еще 12 дорог в 11 оставшихся городов. Значит, ровно в один из этих 11 городов из A ведут два разных маршрута "длины" 2, то есть A входит ровно в один 4-цикл (четырёхугольник). Поскольку это верно для каждого города, сеть дорог состоит из четырёх 4-циклов.
Рассмотрим один из этих 4-циклов – Q. Из него выходят 8 дорог в другие циклы, значит, в некоторый 4-цикл P ведут (как минимум) три дороги. Если две из них выходят из одного города (или приходят в один город), то возникает треугольник или "лишний" 4-цикл.
Пусть все три выходят из разных городов цикла Q и ведут в разные вершины цикла P. Среди первой тройки городов есть две пары соседей, а среди второй – только одна пара не соседей. Поэтому найдутся соседние города цикла Q, дороги из которых ведут в соседние города
цикла P. Эта четверка городов образует "лишний" 4-цикл. Противоречие.
Замечания
Баллы: 4 + 4
