Индукция в графах и теорема Турана

Решим задача для произвольного Докажем утверждение, известное в олимпиадных кругах как теорема Турана.

Оценка: Докажем по индукции, что число ничьих не превосходит

База индукции: При это очевидно. При все три игры не могли закончиться вничью, иначе у всех команд было бы одинаковое число очков.

Шаг индукции: Рассмотрим две команды и сыгравшие вничью. С каждой из остальных команд хотя бы одна из них сыграла не вничью, иначе образуется запрещенная тройка команд. Значит, общее число ничьих в играх с участием этих двух команд не больше По предположению индукции в играх между остальными командами было не более ничьих. Следовательно, общее число ничьих не превосходит

Пример: Пронумеруем команды числами от до Пусть каждые две команды с номерами разной чётности сыграли вничью, а в играх между командами с номерами одной чётности победила команда в меньшим номером. Если то команд имеют нечётный номер и команда - чётный, поэтому количество ничьих равно При получаем по команд с номерами каждой чётности и ничьих. В обоих случаях полученное число равно При этом каждые три команды в играх между собой набрали либо 0, 2 или 4 очка, если имеют номера одной чётности, либо очка, если две из них имеют номера одной чётности, а третья - другой.

Замечание. Заметим, что идея примера приходит из двудольного графа, где разная чётность номеров отвечает разным компонентам.

Подставим и получим ответ.