Турниры в терминах графов и не только (считаем игры и очки)

Рассмотрим табличку Пронумеруем строки и столбцы слева направо и сверху вниз от до соответственно. — клетка на пересечении ой строки и го столбца. В клетку где ставим число если пара ый шахматист и ый сыграли в ом раунде. В клетках стоят крестики (эти клетки нам не нужны). Клетки, которые ниже диагонали нам не нужны (их оставим пустыми).

Приведём пример разбиения на пары для первых -ти раундов.

Докажем, что раунд провести нельзя. -ый сыграл со всеми, кроме -го и -го. В клетки, пары которых выбрать на -м ходе нельзя, будем писать No. Разберём два случая:

1.

-ый сыграл со -ым. Тогда имеем следующую ситуацию:

	1	2	3	4	5	6	7	8
1	X	6	1	2	3	4	5	No
2		X	5	1	2	3	4	No
3			X	3			2	4
4				X	4			5
5					X	5		1
6						X	1	2
7							X	3
8								X

Осталось расставить шестёрки. Все они стоят в разных столбцах и разных строках. Но столбцов, где есть свободные клетки всего значит, в каждом из них ровно по одной шестёрке, тогда в клетке обязательно есть Но тогда в клетке точно нет шестёрки, и в столбце всего свободных клетки, значит, в точно шестёрка, но тогда в её нет, значит, она есть в так как в столбце всего свободных. Итого, есть шестёрка в и в — противоречие, так как -ый сыграл дважды за раунд.

	1	2	3	4	5	6	7	8
1	X	6	1	2	3	4	5	No
2		X	5	1	2	3	4	No
3			X	3	6	No	2	4
4				X	4	6	No	5
5					X	5	6	1
6						X	1	2
7							X	3
8								X

2.

-ый сыграл с -ым. Тогда имеем следующую ситуацию:

	1	2	3	4	5	6	7	8
1	X	No	1	2	3	4	5	6
2		X	5	1	2	3	4	No
3			X	3			2	4
4				X	4			5
5					X	5		1
6						X	1	2
7							X	3
8								X

Далее аналогичными рассуждениями из предыдущего пункта получаем противоречие.

В обоих случаях противоречие, следовательно, пример рабочий.