Мудрецы и фокусы
Ошибка.
Попробуйте повторить позже
Султан собрал 300 придворных мудрецов и предложил им испытание. Имеются колпаки 25 различных цветов, заранее известных мудрецам. Султан сообщил, что на каждого из мудрецов наденут один из этих колпаков, причём если для каждого цвета написать количество надетых колпаков, то все числа будут различны. Каждый мудрец будет видеть колпаки остальных мудрецов, а свой колпак нет. Затем все мудрецы одновременно огласят предполагаемый цвет своего колпака. Могут ли мудрецы заранее договориться действовать так, чтобы гарантированно хотя бы 150 из них назвали цвет верно?
Источники:
Подсказка 1
Несложно понять, в каких количествах у нас присутствуют все цвета. Теперь задумаемся, а какой выбор стоит перед мудрецом, когда ему нужно ответить на вопрос?
Подсказка 2
Т.к. количества цветов принимают все значения от 0 до 24, значит перед каждым мудрецом при ответе стоит выбор ровно между двумя цветами. Если мудрецы не договорятся, то они могут не попасть ни в один цвет. А как сделать так, чтобы в какой-то группе хотя бы один точно попал?
Подсказка 3
Обратим внимание на то, что один и тот же цвет стоит под сомнением ровно у двух мудрецов
Подсказка 4
Как сделать так, чтобы хотя бы половина мудрецов попали в нужный цвет?
Поскольку 
количества колпаков различных цветов принимают все значения от 0 до 24.
Далее, каждый мудрец считает количество колпаков каждого из цветов. Для двух цветов количества колпаков совпадают и мудрец понимает, что на нём колпак одного из этих двух цветов. Остаётся только сделать выбор, какой именно из этих двух цветов ему назвать.
Инверсией в перестановке 
называется всякая пара индексов 
такая, что
и 
Чётность числа инверсий в перестановке определяет чётность перестановки. Стратегия, приведённая ниже,
основана на понятии чётности перестановки.
Пусть мудрецы заранее занумеровали цвета числами от 0 до 24. Тогда истинному распределению колпаков соответствует перестановка
Если мудрец видит равное количество колпаков цвета 
и цвета 
(по 
штук каждого из этих двух цветов), то ему нужно принять
решение, к какому из этих двух цветов отнести свой колпак, то есть выбрать между двумя перестановками
Одна из этих перестановок соответствует истинному распределению цветов, при этом указанные перестановки отличаются расположением ровно двух элементов, поэтому имеют разную чётность.
Мудрецы могут заранее договориться, чтобы ровно 150 из них сделали свой выбор в пользу чётной перестановки, а остальные 150 — в пользу нечётной перестановки.
Тогда ровно 150 мудрецов верно назовут цвет своего колпака.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
