Олимпиадная задача: Наибольшее число пар знакомых на встрече выпускников (8–10 класс)

  Поскольку  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.