В некотором государстве 40 городов. Каждая пара городов соединена авиарейсом одной из двух авиакомпаний. Оказалось, что из каждого города выходит ровно 6 авиарейсов первой авиакомпании. Назовем тройку городов A, B, C замкнутой, если все три авиарейса AB, BC, CA осуществляются одной авиакомпанией. Каково наибольшее возможное количество замкнутых троек городов может быть в этом государстве?
математика 10-11 класс
1334
Фактически, нам дан полный граф на 40 вершинах, рёбра которого раскрашены в 2 цвета. Можно считать, что из любой вершины выходит по 6 красных рёбер и по 34 синих. Нас интересует число одноцветных треугольников. Общее число треугольников равно 40⋅39⋅38/6=9880. Подсчитаем число разноцветных. С каждым из них связано ровно две вершины, из которых выходят рёбра разного цвета. Количество пар таких рёбер равно 40⋅6⋅34, и это количество надо разделить пополам. Это даёт 4080 разноцветных треугольника. Остальные9880– 4080= 5800 одноцветных.
О т в е т. 5800 замкнутых троек городов в этом государстве
