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