Задача 110126

Темы:    [ Разбиения на пары и группы; биекции ] [ Задачи с ограничениями ] [ Степень вершины ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Берлов С.Л.

На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?

Решение

  Поскольку  45 = 1 + 2 + 3 + ... + 9,  можно разбить 45 человек на группы по 1, 2, ..., 9 человек. Пусть люди, принадлежащие одной группе, не знакомы между собой, а люди, принадлежащие разным группам, знакомы. Тогда каждый человек из k-й группы имеет  45 – k  знакомых.

При этом условие задачи выполнено, и общее количество пар знакомых людей равно  
  Докажем, что большего числа знакомств быть не могло. Зафиксируем некоторое k,  0 ≤ k ≤ 44.  Пусть некоторый выпускник знаком ровно с k другими. По условию никакой из его знакомых не может иметь ровно k знакомых. Поэтому количество выпускников, знакомых ровно с k другими, не превосходит
45 – k.
  Обозначим через  A₀, A₁, ..., A₄₄  количество выпускников, имеющих соответственно 0, 1, ..., 44 знакомых. Как показано выше,  A_k ≤ 45 – k,  кроме того,  A₀ + A₁ + ... + A₄₄ = 45.
  Оценим общее число знакомств:   2S = A₁ + 2A₂ + ... + 44A₄₄ = A₄₄ + (A₄₄ + A₄₃) + ... + (A₄₄ + A₄₃ + ... + A₃₆) + ... + (A₄₄ + A₄₃ + ... + A₀) ≤
≤ 1 + (1 + 2) + ... + (1 + 2 + ... + 9) + 45 + 45 + ... + 45 = 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 36·45 = 1740.

Ответ

870 пар.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2003
Этап
Вариант	4
Класс
Класс	10
задача
Номер	03.4.10.3