Интересное свойство турниров

В однокруговом турнире (т.е. любые две команды сыграли друг с другом ровно один раз) участвовали 15 команд. Докажите, что хотя бы в одной игре встретились команды, которые перед этой игрой участвовали в сумме в нечётном числе игр этого турнира.

Задача была предложена на Турнире городов 2002/03 года на основном варианте весеннего тура для 8-9 классов. Автор задачи - А.В. Шаповалов.

Приведу два решения задачи. Оба раза буду предполагать противное, т.е. что сумма, о которой говорится в условии задачи, для каждого матча чётна.

Решение 1. Будем перед каждой игрой считать сумму матчей, которые команды сыграли до этой игры. Тогда, если мы сложим все такие суммы, то получится целое число.

С другой стороны, для каждой команды будет сначала посчитано число 0, потом число 1, потом число 2 и т.д. до числа 13.
Т.е. в сумме 15 команд дадут после окончания турнира сумму
15*(0+1+2+...+13)=15*91=1365.
Но это число нечётное! А мы много раз складывали чётные числа и, таким образом, в сумме должны были получить чётное число. Получили противоречие!

Решение 2. Рассмотрим граф, вершиной которого будут команды, участвующие в турнире. Так как сумма игр, сыгранных до матча, для каждой пары команд была чётной, то они до этого сыграли либо по нечётному числу игру, либо обе по чётному числу игр. Так вот, будем соединять вершины графа ребром, если обе команды участвовали до этого в чётном числе игр (0, или 2, или 4, ..., или 12). Таких моментов у каждой команды было 7, т.е. из каждой вершины выходит по 7 рёбер. Но тогда у нас получилось нечётное количестве нечётных вершин (из 15 вершин выходит по 7 рёбер), что противоречит лемме о рукопожатиях!

Замечание. Можно так организовать расписание игр турнира, что только один раз встретится пара команды, сыгравших до этого в сумме в нечётном количестве встреч. Построение этого примера - задача интересная, но не очень сложная. И решение этой задачи я оставляю читателю.