В некотором государстве 36 городов. Каждая пара городов соединена авиарейсом одной из двух авиакомпаний. Оказалось, что из каждого города выходит ровно 8 авиарейсов первой авиакомпании. Назовем тройку городов замкнутой, если все три авиарейса осуществляются одной авиакомпанией. Каково наибольшее возможное количество замкнутых троек городов может быть в этом государстве?
математика 10-11 класс
2260
Нам дан полный граф на 36 вершинах, рёбра которого раскрашены в 2 цвета. Можно считать, что из любой вершины выходит по 8 рёбер одного цвета и по 28 ребер другого. Нас интересует число одноцветных треугольников. Общее число треугольников равно 36⋅35⋅34/6=7140. Подсчитаем число разноцветных. С каждым из них связано ровно две вершины, из которых выходят рёбра разного цвета. Количество пар таких рёбер равно 36⋅8⋅28, и это количество надо разделить пополам. Это даёт 4032 разноцветных треугольника. Остальные (7140-4032)=3108 одноцветные.
Вопросы к решению (1)
по 8 рёбер одного цвета и по 28 ребер другого.
