Комбинаторика на Иннополисе

Пусть — искомое число помещении в зависимости от количества участников турнира. Сначала докажем индукцией по , что База для и очевидна.

Зафиксируем помещение (например, №1) и обозначим через множество шахматистов (вершин графа, каждое ребро которого соответствует определенной партии), которые играли в этом помещении белыми фигурами. Аналогично, обозначим за множество шахматистов, которые не играли в этом помещении белыми фигурами. Множества и не пересекаются — значит, хотя бы одно из них без ограничения общности будем считать, что это содержит не более элементов, остальные шахматисты (их не менее ) не играли белыми фигурами в помещении №1 — значит, им для этого хватило помещений:

Покажем, как сделать "правильное"(т.е. соответствующее условию задачи) расписание с Для этого занумеруем вершины графа (т.е. шахматистов) числами от до и ориентируем ребра графа (т.е. партии) если (шахматист играет белыми, а — черными), а помещения занумеруем числами от до Ребру поставим в соответствие номер который определяется как наибольшее такое, что в двоичной записи числа на -м месте стоит 1, а у числа — Такое существует, поскольку Кроме того, в двоичных разложениях не более цифр, откуда

Осталось проверить, что ребрам и соответствуют разные номера. Действительно, если бы им соответствовал общий номер то у числа в -м разряде двоичной записи стояла бы и цифра из-за ребра и цифра из-за ребра что невозможно.