Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Будем называть замкнутый маршрут из пяти дорог, существование которого запрещено условием, 5-циклом.

Докажем сначала, что если мы рассмотрим какие-либо шесть городов, между ними будет проведено не более 10 дорог из возможных 15. Предположим противное: пусть между какими-то шестью городами проведено не менее 11 дорог. Тогда среди этих шести городов и соединяющих их дорог найдём 5-цикл, существование которого запрещено условием.

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

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

Какие-то две антидороги точно выходят из одного города. Исключим его и рассмотрим оставшиеся пять городов. Пронумеруем их числами от 1 до 5. Между этими городами не более двух антидорог. Опять же, достаточно найти 5-цикл в ситуации, когда этих антидорог ровно две, в противном случае он найдётся и подавно.

Есть две возможных ситуации: когда эти антидороги имеют общий конец, и когда не имеют.

В первом случае без ограничения можно считать, что антидороги соединяют город 1 с городами 2 и 3. Тогда мы можем найти следующий 5-цикл: 1-4-2-3-5-1.

Во втором случае можно считать, что наши антидороги соединяют город 1 с городом 2, а город 3 с городом 4. Тогда мы сможем найти такой 5-цикл: 1-3-5-2-4-1.

Мы доказали, что среди любых 5 городов проведено не более 10 дорог из 15, то есть максимум от всех возможных дорог. Поскольку каждая пара городов с проведённой между ними дорогой или антидорогой входит в равное число таких шестёрок, поэтому общее количество дорог также составляет не более от максимально возможного, то есть максимум

Докажем это чуть более строго. В каждой шестёрке городов не более 10 дорог. Всего этих шестёрок Итого получаем дорог, однако, каждая из них посчитана несколько раз. А именно, к каждой паре городов можно подобрать ещё 4 города способами, значит, именно столько раз мы посчитали каждую дорогу.

Таким образом, всего дорог не более