Комбинаторика на Иннополисе
Ошибка.
Попробуйте повторить позже
Проводится шахматный турнир, в котором участвуют 
человек 
Из-за эпидемической обстановки партии проходят в отдельных
помещениях, причем в каждом помещении шахматист может играть только фигурами одного цвета.
Например, если Иван играл черными фигурами в помещении №1, то он уже не сможет сыграть белыми фигурами в этом помещении. Аналогично, если участник играл белыми фигурами в помещении №5, то в этом же помещении он уже не сможет играть черными фигурами. При этом он может снова играть белыми фигурами в помещении №5.
Известно, что каждый участник турнира должен сыграть с любым другим участником ровно одну партию. Организаторы хотят
составить такое расписание, чтобы задействовать минимально возможное число помещений. Докажите, что это число равно
Источники:
Подсказка 1
Давайте попробуем доказать, что нам понадобиться не менее, чем [log_2(n)] (под [x] подразумевается целочисленное x округление вверх) комнат и что именно [log_2(n)] достаточно. Для док-ва первого утверждения давайте для удобства заведём функцию f(n) - искомое кол-во помещений от кол-ва участников. И построим док-во по сильной индукции.
Подсказка 2
Рассмотрите какое-то помещение и разбейте множество игроков на тех, которые играли и не играли белыми фигурами. Что мы можем сказать про кол-во участников в одном из получившихся множеств?
Подсказка 3
В каком-то из множеств не более n/2 элементов, пусть в том, которые играли белыми фигурами, тогда не играли ими не менее n/2 элементов и им хватило на 1 помещение меньше, чем n игрокам, какую оценку мы тогда можем получить на f?
Подсказка 4
f(n) - 1 >= f([n/2]), применяя ПИ индукции получим f(n) - 1 >= [log_2([n/2])] <=> f(n) >= [log_2(n)], теперь осталось придумать пример рассадки.
Подсказка 5
Давайте попробуем переформулировать задачу в терминах ориентированного графа, пусть вершины - шахматисты, ориентируем ребро ij, если i > j (i играет белыми, а j - чёрными). Поставим каждому ребру число k - наибольшее такое число, что в двоичной записи числа i на k-м месте стоит 1, а у j - 0. Осталось только доказать, почему такой пример - верный.
Подсказка 6
Посмотрите, сколько всего может быть цифр в числах i, j и почему рёбрам ij, jl соответствуют разные номера, и задача решена!
Пусть 
— искомое число помещении в зависимости от количества 
участников турнира. Сначала докажем индукцией по 
,
что 
База 
для 
и 
очевидна.
Зафиксируем помещение (например, №1) и обозначим через 
множество шахматистов (вершин графа, каждое ребро которого
соответствует определенной партии), которые играли в этом помещении белыми фигурами. Аналогично, обозначим за 
множество
шахматистов, которые не играли в этом помещении белыми фигурами. Множества 
и 
не пересекаются — значит, хотя
бы одно из них 
без ограничения общности будем считать, что это 
содержит не более 
элементов, остальные
шахматисты (их не менее 
) не играли белыми фигурами в помещении №1 — значит, им для этого хватило 
помещений:
Покажем, как сделать "правильное"(т.е. соответствующее условию задачи) расписание с 
Для этого занумеруем
вершины графа (т.е. шахматистов) числами от 
до 
и ориентируем ребра графа (т.е. партии) 
если 
(шахматист 
играет
белыми, а 
— черными), а помещения занумеруем числами от 
до 
Ребру 
поставим в соответствие номер 
который определяется как наибольшее 
такое, что в двоичной записи числа 
на 
-м месте стоит 1, а у числа 
—
Такое 
существует, поскольку 
Кроме того, в двоичных разложениях 
не более 
цифр, откуда
Осталось проверить, что ребрам 
и 
соответствуют разные номера. Действительно, если бы им соответствовал общий номер 
то у
числа 
в 
-м разряде двоичной записи стояла бы и цифра 
из-за ребра 
и цифра 
из-за ребра 
что
невозможно.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
