Задача 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