Задать свой вопрос   *более 50 000 пользователей получили ответ на «Решим всё»

Задача 12621 В некотором государстве 37 городов....

Условие

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

математика 10-11 класс 1916

Решение

Нам дан полный граф на 37 вершинах, рёбра которого раскрашены в 2 цвета. Можно считать, что из любой вершины выходит по 8 рёбер одного цвета и по 29 ребер другого. Нас интересует число одноцветных треугольников. Общее число треугольников равно 37⋅36⋅35/6=7 770. Подсчитаем число разноцветных. С каждым из них связано ровно две вершины, из которых выходят рёбра разного цвета. Количество пар таких рёбер равно 37⋅8⋅29, и это количество надо разделить пополам. Это даёт 4292 разноцветных треугольника. Остальные (7770–4292)=3478 одноцветные.

Написать комментарий

Меню

Присоединяйся в ВК