В классе учится 23 человека. В течение года каждый ученик этого класса один раз праздновал день рождения, на который пришли некоторые (хотя бы один, но не все) его одноклассники. Могло ли оказаться, что каждые два ученика этого класса встретились на таких празднованиях одинаковое число раз? (Считается, что на каждом празднике встретились каждые два гостя, а также именинник встретился со всеми гостями.)

   Решение

Темы:    [ Текстовые задачи (прочее) ] [ Классическая комбинаторика (прочее) ]

Сложность: 3 Классы: 9,10,11

Прислать комментарий

Условие

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

Решение

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

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

Ответ

7.

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