ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66576
Темы:    [ Текстовые задачи (прочее) ]
[ Классическая комбинаторика (прочее) ]
Сложность: 3
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

За круглым вращающимся столом, на котором стоят 8 белых и 7 чёрных чашек, сидят 15 гномов. Они надели 8 белых и 7 чёрных колпачков. Каждый гном берёт себе чашку, цвет которой совпадает с цветом его колпачка, и ставит напротив себя, после этого стол поворачивается случайным образом. Какое наибольшее число совпадений цвета чашки и колпачка можно гарантировать после поворота стола (гномы сами выбирают, как сесть, но не знают, как повернётся стол)?

Решение

Рассмотрим произвольную расстановку чашек и выпишем в строчку их цвета. Под этой строчкой выпишем также все её различные циклические сдвиги — всего 14 штук. Подсчитаем, сколько всего будет совпадений по цвету на одной и той же позиции в исходной расстановке и в расстановках, полученных сдвигами. Для чёрных чашек совпадения по цвету будут ровно в 6 сдвигах, а для белых — в 7 сдвигах. Следовательно, всего совпадений по цветам для 14 сдвигов будет $7\cdot6+8\cdot7=98$. Значит, существует сдвиг, в котором будет не более $98/14=7$ совпадений с исходной расстановкой.

Рассмотрим такую расстановку чашек: ббббчбчббччбччч. Непосредственной проверкой можно убедиться, что все её циклические сдвиги имеют с ней ровно 7 совпадений.


Ответ

7.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 83
Год 2020
класс
Класс 11
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .