Задача 009 — Задачи на Графы

В день Св. Валентина $n$ влюбленных пар провели два однокруговых турнира по пинг-понгу — один для юношей, другой для девушек. Юноша и девушка из каждой пары вместе выиграли $n-1$ игру. Докажите, что количество троек юношей ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ , равно количеству таких троек девушек.

Подсказка

Попробуйте сравнить не количество циклических троек, а количество оставшихся троек.

Решение

Занумеруем все пары числами от 1 до $n$ . Пусть в паре с номером $k$ юноша выиграл $a_{k}$ , а девушка $-n-1-a_{k}$ партий. Заметим, что тогда девушка из этой пары проиграла $a_{k}$ партий.

Заметим, что общие количества троек юношей и девушек равны. Поэтому, чтобы сравнить количества троек юношей и девушек ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ (далее будем называть такие тройки циклическими) достаточно сравнить количества оставшихся (нециклических) троек. Заметим, что в каждой нециклической тройке есть ровно один человек, выигравший обе свои партии и ровно один человек, обе партии проигравший.

Рассмотрим теперь пару номер $k$ . Легко видеть, что количество троек юношей, в которых юноша из $k$ -й пары выиграл обе партии равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ . Поскольку в каждой нециклической тройке юношей есть ровно один юноша, одержавший две победы, количество таких троек равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ . Аналогично, количество троек девушек, в которых девушка из $k$ -й пары обе партии проиграла, также равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ и, следовательно, количество нециклических троек девушек также равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ .