МОШ 2022, 11 класс, задача 6
Султан собрал придворных мудрецов и предложил им испытание. Имеются колпаки различных цветов, заранее известных мудрецам. Султан сообщил, что на каждого из мудрецов наденут один из этих колпаков, причём если для каждого цвета написать количество надетых колпаков, то все числа будут различны. Каждый мудрец будет видеть колпаки остальных мудрецов, а свой колпак нет. Затем все мудрецы одновременно огласят предполагаемый цвет своего колпака. Могут ли мудрецы заранее договориться действовать так, чтобы гарантированно хотя бы из них назвали цвет верно?
(А. В. Грибалко)
Ответ
Решение. Поскольку , количества колпаков различных цветов принимают все значения от до .
Далее, каждый мудрец считает количество колпаков каждого из цветов. Для двух цветов количества колпаков совпадают и мудрец понимает, что на нём колпак одного из этих двух цветов. Остаётся только сделать выбор, какой именно из этих двух цветов ему назвать.
Договориться (заранее!) о том, как каждому мудрецу делать этот выбор, можно различными способами. Например, можно построить регулярный двудольный граф и воспользоваться леммой Холла для арабских стран. Стратегия, приведённая ниже, основана на понятии чётности перестановки.
Пусть мудрецы заранее занумеровали цвета числами от до . Тогда истинному распределению колпаков соответствует перестановка
Если мудрец видит равное количество колпаков цвета и цвета (по штук каждого из этих двух цветов), то ему нужно принять решение, к какому из этих двух цветов отнести свой колпак, то есть выбрать между двумя перестановками
и
Одна из этих перестановок соответствует истинному распределению цветов, при этом указанные перестановки отличаются расположением ровно двух элементов, поэтому имеют разную чётность.
Мудрецы могут заранее договориться, чтобы ровно из них сделали свой выбор в пользу чётной перестановки, а остальные — в пользу нечётной перестановки.
Тогда ровно половина мудрецов верно назовут цвет своего колпака.
Замечание. Стратегия, согласно которой мудрецы заранее договариваются так, что из них выбирают цвет с большим номером (из двух, между которыми нужно сделать выбор), а остальные выбирают цвет с меньшим номером, не гарантирует верных ответов.
Действительно, пусть истинному распределению колпаков соответствует перестановка
и пусть мудрецы, которым достались колпаки цветов - (их ровно человек), должны выбрать цвет с меньшим номером, а остальные мудрецов — с большим номером. Тогда все мудрецы, кроме мудрецов с колпаками цветов , и , назовут цвет ошибочно.