Задача 35438

Темы:    [ Теория графов (прочее) ] [ Подсчет двумя способами ] [ Делимость чисел. Общие свойства ]

Сложность: 3 Классы: 7,8,9

Условие

В компании у каждых двух людей ровно пять общих знакомых. Докажите, что количество пар знакомых делится на 3.

Подсказка

Выразите количество троек попарно знакомых людей через количество пар знакомых.

Решение

Обозначим через Р количество пар знакомых людей (то есть число рёбер в соответствующем графе), а через Т – количество треугольников в этом графе. По условию каждое из рёбер входит ровно в 5 треугольников. С другой стороны, в каждый из Т треугольников содержит ровно 3 ребра. Следовательно,
5Р = 3Т.  Поскольку 3 и 5 – взаимно простые числа, Р делится на 3.

Источники и прецеденты использования

web-сайт

задача