Азия-тынық мұхит математикалық олимпиадасы, 2010 жыл

Олимпиадаға $n$ оқушы қатысады ($n$ — натурал сан). Кез келген екi қатысушы бiрiн-бiрi таниды немесе танымайды. Бiрiн-бiрi танымайтын, бiрақ ортақ таныстары бар қатысушылардың парлары ең көп дегенде қаншаға тең болуы мүмкiн?

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

Пусть $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$ то число общих знакомых по построению будут убывать.