Азиатско-Тихоокеанская математическая олимпиада, 2010 год

На олимпиаде участвуют $n$ школьников ($n$ — натуральное число). Любые два участника либо знакомы друг с другом, либо не знакомы. Каково наибольшее возможное количество пар участников, которые не знакомы друг с другом, но имеют общего знакомого среди других участников олимпиады?

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

Пусть $a_{1},a_{2},...,a_{n}$ есть участники, расположим пары как $(a_{i},a_{j})$ где $1 \leq i < j \leq n$ пусть будут знакомы только пары $(a_{i},a_{n})$ где $1 \leq i \leq n$ тогда получим что число общих знакомых равно арифметической сумме $S=1+2+...+n-1 = \dfrac{(n-1)(n-2)}{2}$.

Докажем что это максимальное количество, число незнакомых не должно убывать, так как при этом общие знакомые пар будут меньше этого числа, если знакомые будут меньше чем $n-1$ то число общих знакомых по построению будут убывать.