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