|
|
 |
Условие
Султан собрал 300 придворных мудрецов и предложил им испытание. Имеются колпаки 25 различных цветов, заранее известных мудрецам. Султан сообщил, что на каждого из мудрецов наденут один из этих колпаков, причём если для каждого цвета написать количество надетых колпаков, то все числа будут различны. Каждый мудрец будет видеть колпаки остальных мудрецов, а свой колпак нет. Затем все мудрецы одновременно огласят предполагаемый цвет своего колпака. Могут ли мудрецы заранее договориться действовать так, чтобы гарантированно хотя бы 150 из них назвали цвет верно?Решение
Поскольку $0+1+2+\ldots+24=300$, количества колпаков различных цветов принимают все значения от $0$ до $24$.Далее, каждый мудрец считает количество колпаков каждого из цветов. Для двух цветов количества колпаков совпадают и мудрец понимает, что на нём колпак одного из этих двух цветов. Остаётся только сделать выбор, какой именно из этих двух цветов ему назвать.
Договориться (заранее!) о том, как каждому мудрецу делать этот выбор, можно различными способами. Например, можно воспользоваться обобщением леммы Холла (см. по этому поводу статью М. Шевцовой «Многократная лемма Холла в задачах про мудрецов» в Кванте №7 за 2019 год). Стратегия, приведённая ниже, основана на понятии чётности перестановки.
Пусть мудрецы заранее занумеровали цвета числами от 0 до 24. Тогда истинному распределению колпаков соответствует перестановка $${\begin{array}{r} \text{номер цвета}\\ \text{кол-во колпаков} \end{array} \left( \begin{array}{ccccccccc} 0 & 1 & 2 & \ldots & i & \ldots & j & \ldots & 24\\ a_0 & a_1 & a_2 & \ldots & a_i & \ldots & a_j & \ldots & a_{24} \end{array} \right)} . $$ Если мудрец видит равное количество колпаков цвета $i$ и цвета $j$ (по $k$ штук каждого из этих двух цветов), то ему нужно принять решение, к какому из этих двух цветов отнести свой колпак, то есть выбрать между двумя перестановками \begin{align*} &{\left( \begin{array}{ccccccccc} 0 & 1 & 2 & \ldots & i & \ldots & j & \ldots & 24\\ a_0 & a_1 & a_2 & \ldots & k & \ldots & k+1 & \ldots & a_{24} \end{array} \right)}, &{\left( \begin{array}{ccccccccc} 0 & 1 & 2 & \ldots & i & \ldots & j & \ldots & 24\\ a_0 & a_1 & a_2 & \ldots & k+1 & \ldots & k & \ldots & a_{24} \end{array} \right)}. \end{align*} Одна из этих перестановок соответствует истинному распределению цветов, при этом указанные перестановки отличаются расположением ровно двух элементов, поэтому имеют разную чётность.
Мудрецы могут заранее договориться, чтобы ровно 150 из них сделали свой выбор в пользу чётной перестановки, а остальные 150 – в пользу нечётной перестановки.
Тогда ровно 150 мудрецов верно назовут цвет своего колпака.
Ответ
Да, могут.Замечания
Стратегия, согласно которой мудрецы заранее договариваются так, что 150 из них выбирают цвет с большим номером (из двух, между которыми нужно сделать выбор), а остальные 150 выбирают цвет с меньшим номером, не гарантирует 150 верных ответов.
Действительно, пусть истинному распределению колпаков соответствует перестановка $$ {\begin{array}{@{}r} \text{номер цвета}\\ \text{кол-во колпаков} \end{array} \left( \begin{array}{cccccccccccccc} 0 & 1 & 2 & \ldots & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\ 0 & 1 & 2 & \ldots & 15 & 16 & 17 & 24 & 23 & 22 & 21 & 20 & 19 & 18 \end{array} \right)} $$ и пусть мудрецы, которым достались колпаки цветов 3-17 (их ровно 150 человек), должны выбрать цвет с меньшим номером, а остальные 150 мудрецов – с большим номером. Тогда все мудрецы, кроме мудрецов с колпаками цветов 1, 2 и 24, назовут цвет ошибочно.
