Комбинаторика на ММО: графы, турниры, логика, конструктивы
Ошибка.
Попробуйте повторить позже
За круглым вращающимся столом, на котором стоят 
белых и 
чёрных чашек, сидят 
гномов. Они надели 
белых и 
чёрных колпачков. Каждый гном берёт себе чашку, цвет которой совпадает с цветом его колпачка, и ставит
напротив себя, после этого стол поворачивается случайным образом. Какое наибольшее число совпадений цвета чашки
и колпачка можно гарантировать после поворота стола (гномы сами выбирают, как сесть, но не знают, как повернётся
стол)?
Источники:
Подсказка 1
Рассмотрим произвольную расстановку чашек и выпишем в строчку их цвета. Это задача про циклические сдвиги, давайте их выпишем ниже.
Подсказка 2
Мы получим 14 циклических сдвигов. Попробуйте посчитать, сколько будет совпадений по цвету на произвольной позиции в исходной расстановке, и в расстановках, полученных сдвигами.
Подсказка 3
Черных чашек — 7, следовательно, совпадение будет в 6 сдвигах. Аналогично, для белых чашек будет совпадение в 7 сдвигах. Сколько всего будет совпадений по цветам для 14 сдвигов?
Подсказка 4
7·6 + 8·7 = 98. Как можно оценить число совпадений в некотором сдвиге?
Подсказка 5
98/14 = 7, следовательно, найдется сдвиг, в котором не более 7 совпадений с исходной расстановкой. Это оценка, теперь надо подобрать пример.
Рассмотрим произвольную расстановку чашек и выпишем в строчку их цвета. Под этой строчкой выпишем также все её различные
циклические сдвиги — всего 
штук. Подсчитаем, сколько всего будет совпадений по цвету на одной и той же позиции в исходной
расстановке и в расстановках, полученных сдвигами. Для чёрных чашек совпадения по цвету будут ровно в 
сдвигах, а для белых — в 
сдвигах. Следовательно, всего совпадений по цветам для 
сдвигов будет
Значит, существует сдвиг, в котором будет не более 
совпадений с исходной расстановкой.
Рассмотрим такую расстановку чашек:
Непосредственной проверкой можно убедиться, что все её циклические сдвиги имеют с ней ровно 
совпадений.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
