Олимпиадная задача: Наибольшее число пар знакомых на встрече выпускников (8–10 класс)
Задача
На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?
Решение
Поскольку 45 = 1 + 2 + 3 + ... + 9, можно разбить 45 человек на группы по 1, 2, ..., 9 человек. Пусть люди, принадлежащие одной группе, не знакомы между собой, а люди, принадлежащие разным группам, знакомы. Тогда каждый человек из k-й группы имеет 45 – k
знакомых.При этом условие задачи выполнено, и общее количество пар знакомых людей равно 
Докажем, что большего числа знакомств быть не могло. Зафиксируем некоторое k, 0 ≤ k ≤ 44. Пусть некоторый выпускник знаком ровно с k другими. По условию никакой из его знакомых не может иметь ровно k знакомых. Поэтому количество выпускников, знакомых ровно с k другими, не превосходит
45 – k.
Обозначим через A0, A1, ..., A44 количество выпускников, имеющих соответственно 0, 1, ..., 44 знакомых. Как показано выше, Ak ≤ 45 – k, кроме того, A0 + A1 + ... + A44 = 45.
Оценим общее число знакомств: 2S = A1 + 2A2 + ... + 44A44 = A44 + (A44 + A43) + ... + (A44 + A43 + ... + A36) + ... + (A44 + A43 + ... + A0) ≤
≤ 1 + (1 + 2) + ... + (1 + 2 + ... + 9) + 45 + 45 + ... + 45 = 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 36·45 = 1740.
Ответ
870 пар.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь