Экономный король

В стране 210 городов и совсем нет дорог. Король хочет построить несколько дорог с односторонним движением так, чтобы для любых трех городов A, B, C, между которыми есть дороги, ведущие из A в B и из B в C, не было бы дороги, ведущей из A в C. Какое наибольшее число дорог он сможет построить?

Задача была предложена на Санкт-Петербургской математической олимпиаде в 2005 году. Авторы задачи - Д.В. Карпов и К.А. Сухов.

Для начала заметим, что если мы рассмотрим произвольные 4 города, и между любыми двумя из этих городов будет идти дорога с односторонним движением, то мы сможем выбрать из этих четырёх городов три (назовём их L, M, N), что из L идут дороги в M и N, а из M идёт дорога в N.
Действительно, из какого-то города ведёт хотя бы две дороги. Этот город и выберем в качестве L. Два, города, куда ведут дороги назовём M и N в зависимости от того, куда идёт дорога между ними.

Рассмотрим теперь граф с n=210 вершинами. И будем соединять две вершины (два города) ребром, если между ними есть дорога (нам не важно, что она с односторонним движением). Из предыдущего замечания мы видим, что в таком графе не должно найтись четырёх попарно соединённых вершин. Лемма Турана (я писал про её частный случай) говорит нам, что тогда в графе должно быть не больше n^2/3 рёбер. В нашем случае это 14700.

Теперь построим пример. Покажем, что в нашем графе может быть 14700 ребер. Разделим 210 городов на три группы A, B, C по 70 городов. Пусть все дороги ведут из городов группы A в города группы B; из городов группы B в города группы C; из городов группы C в города группы A.