Задача
В парламенте 30 депутатов. Каждые два из них либо дружат, либо враждуют, причём каждый дружит ровно с шестью другими. Каждые три депутата образуют комиссию. Найдите общее число комиссий, в которых все три члена попарно дружат или все трое попарно враждуют.
Решение
Обозначим депутатов точками. Соединим точки красным отрезком, если cоответствующие депутаты дружат, и синим – если враждуют.
Нам нужно найти число одноцветных треугольников с вершинами в данных точках. Число всех треугольников равно 
Подсчитаем сначала число неодноцветных треугольников. В каждом таком треугольнике ровно два угла, в которых сходятся красный и синий отрезки (назовем такие углы разноцветными). В одноцветных треугольниках разноцветных углов нет. В каждой вершине по условию сходятся
6 красных и 23 синих отрезка, то есть имеется 6·23 = 138 разноцветных углов с фиксированной вершиной. Общее количество неодноцветных треугольников, таким образом, равно 138·30 : 2 = 2070. А число одноцветных треугольников равно 4060 – 2070 = 1990.
Ответ
1990 комиссий.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь