Математикадан облыстық олимпиада, 2003-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)}$