Областная олимпиада по математике, 2004 год, 11 класс

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

Комментарий/решение

Докажем что максимальное кол-во школьников с n знакомых, где n<45 равно 45-n.

Пусть существует ровно k школьников у которых n знакомых. Так как они не могут дружить с другими школьниками с кол-вом знакомых равным n.

Значит $n\leq45-k$

$k\leq45-n$

Очевидно что если на олимпиаде будет 1 школьник с 44 знакомыми и 2 школьника с 43 и 3 с 42 и тд. кол-во знакомых пар будет максимальным.

Значит максимальное кол-во равно $\sum \limits_{i=1}^{9}{i*(45-i)}$