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

Рассмотрим город, который связан с наибольшим количеством других городов (пусть этих городов n, и n > = 2. Если n = 1, то города разбиваются на пары, соединенные рейсами, рейсов не более 18/2 = 9, если n = 0, то рейсов 0). Тогда между любыми из этих n городов нет рейсов. Каждый из оставшихся 18 - 1 - n городов соединён не более с чем n городами, тогда общее число рейсов не больше, чем n + (18 - 1 - n) • n = n (18 - n).

n (18 - n) - квадратичная функция, максимум достигается в вершине n = 18/2 = 9, максимальное значение 81.

Пример, когда значение 81 достигается: пусть города разделены на две группы по 9, и из каждого города есть авиарейсы во все города другой группы. Тогда рейсов 9 * 9 = 81