МОШ 2020, 11 класс, задача 3
За круглым вращающимся столом, на котором стоят белых и чёрных чашек, сидят гномов. Они надели белых и чёрных колпачков. Каждый гном берёт себе чашку, цвет которой совпадает с цветом его колпачка и ставит напротив себя, после этого стол поворачивается случайным образом. Какое наибольшее число совпадений цвета чашки и колпачка можно гарантировать после поворота стола (гномы сами выбирают, как сесть, но не знают, как повернётся стол)?
Ответ
Ответ. .
Решение. Рассмотрим произвольную расстановку чашек и выпишем в строчку их цвета. Под этой строчкой выпишем также все её различные циклические сдвиги — всего штук. Подсчитаем, сколько всего будет совпадений по цвету на одной и той же позиции в исходной расстановке и в расстановках, полученных сдвигами. Для чёрных чашек совпадения по цвету будут ровно в сдвигах, а для белых — в сдвигах. Следовательно, всего совпадений по цветам для сдвигов будет . Значит, существует сдвиг, в котором будет не более совпадений с исходной расстановкой.
Рассмотрим такую расстановку чашек: . Непосредственной проверкой можно убедиться, что все её циклические сдвиги имеют с ней ровно совпадений.