Задача про мудрецов и разноцветные шляпы

[Unconnected]

Подскажите пожалуйста, в какую сторону думать, что-то вообще не выходит:

N мудрецов заходят в комнату, где на них надевают шляпы N разных цветов. Находясь в комнате, мудрецы не могут обмениваться информацией никаким образом. В какой-то момент все мудрецы одновременно называют предполагаемый цвет своей шляпы. Вопрос - могут ли мудрецы заранее (до входа в комнату) так договориться, чтобы хотя бы 1 мудрец угадывал свой цвет?

Для случая N=2 стратегия простая - один мудрец говорит цвет шляпы, который видит, а другой - противоположный тому, который видит.

[Dan B-Yallay]

Что-то не пойму, чего я не понимаю. Что мешает каждому из $N$ мудрецов назвать тот цвет, который он не видит?

[statistonline]

Если это иннополисовская задача, то условие Вы привели не совсем корректно. Может ли мудрец наблюдать шляпы всех прочих $N-1$ мудрецов?

[Dan B-Yallay]

statistonline в сообщении #1317778 писал(а):

Вот это и мешает.

Поясню: пусть в случае с двумя мудрецами, оба цвета шляп известны -- белый и чёрный. (Если неизвестны, то что такое "противоположный цвет"?). Тогда тот, кто видит на другом шляпу белого цвета, говорит что его шляпа чёрная. Второй соответственно видит чёрную шляпу на голове первого, поэтому называет цвет белый. Аналогично для произвольного количества.

[gris]

Вероятно, предполагается, что всего цветов может быть $N$ и цвета их известны, но на шляпах они могут повторяться (как в случае с двумя мудрецами).
Право, лучше бы писали натуральные числа на шляпах или предлагали перестановку. В случае $N=2$ их всего четыре штуки и алгоритм формирования перестановки с гарантированно совпадающим членом находится. Может быть, рассмотреть случай $N=3$? Там девять случаев раздать шляпы (учитывая порядок).

[Dan B-Yallay]

Да, видимо ТС-у надо уточнить условия.

[Unconnected]

Цитата:

Может быть, рассмотреть случай $N=3$? Там девять случаев раздать шляпы (учитывая порядок).

А разве не 3^3 = 27 раздач шляпы?

Цитата:

Поясню: пусть в случае с двумя мудрецами, оба цвета шляп известны -- белый и чёрный. (Если неизвестны, то что такое "противоположный цвет"?). Тогда тот, кто видит на другом шляпу белого цвета, говорит что его шляпа чёрная. Второй соответственно видит чёрную шляпу на голове первого, поэтому называет цвет белый. Аналогично для произвольного количества.

Если на обоих мудрецах белые шляпы, то никто не угадает

Да, наверное надо добавить, что цвета шляп могут повторяться, и что каждый мудрец видит шляпы всех остальных.

[Sender]

Сопоставим цветам числа от $0$ до $N-1$. Все вычисления ведутся в $\mathbb{Z}_N$. Пусть $S$ - сумма цветов всех шляп. Каждое из $N$ возможных значений $S$ берёт некоторый мудрец. Кто-нибудь да угадает.

[EUgeneUS]

Sender в сообщении #1317914 писал(а):

Сопоставим цветам числа от $0$ до $N-1$

Это возможно только если мудрецы знают, какие именно N цветов будут использованы для раскраски шляп.
Если же мудрецам известно только то, что цветов будет (или может быть?) N, но неизвестно каких именно, то беда.

Присоединяюсь к:

Dan B-Yallay в сообщении #1317790 писал(а):

Да, видимо ТС-у надо уточнить условия.

[Sender]

Судя по

Unconnected в сообщении #1317776 писал(а):

Для случая N=2 стратегия простая - один мудрец говорит цвет шляпы, который видит, а другой - противоположный тому, который видит.

,
используемый набор цветов известен заранее.

-- Чт июн 07, 2018 19:27:15 --

EUgeneUS в сообщении #1317967 писал(а):

Если же мудрецам известно только то, что цветов будет (или может быть?) N, но неизвестно каких именно, то беда.

Трудно не согласиться. Поди догадайся, что на тебе шляпа цвета бедра испуганной нимфы.

[EUgeneUS]

Sender в сообщении #1317977 писал(а):

используемый набор цветов известен заранее.

если для цвета можно назвать "противоположный" - это не значит, что используемый набор цветов известен заранее.

Для ч-б понятно, "ч" противоложен "б", и наоборот.
Однако, есть такое понятие, как дополнительный цвет. Который можно трактовать, как "противоположный". Ч-б в этом смысле "противоположны".

При этом может оказаться так, что цвет "противоположный", дополнительный какому-то из набора, окажется не в наборе.

Таки предлагаю запросить у ТС уточнение условий, а не восстанавливать их по вторичным, хмм, признакам.

[grizzly]

EUgeneUS
Вы что-то перемудрили. Как отметил выше Sender, Ваши требования примерно эквивалентны тому, что название цвета нужно угадать, например, на никому не известном языке. То, что набор цветов известен -- вполне естественное условие, если не оговорено обратное.

[EUgeneUS]

Sender в сообщении #1317977 писал(а):

Трудно не согласиться. Поди догадайся, что на тебе шляпа цвета бедра испуганной нимфы.

Тут интересный вопрос вырисовывается.
Если мудрецы,
а) могут ТОЧНО измерять цвет. Например, в RGB.
б) договорились, что значит "противоположный" цвет.

То можно ли догадаться, "что на тебе шляпа цвета бедра испуганной нимфы"?
Понятно, что предполагаем, что цвет бедра испуганной нимфы определен, например, в RGB.

-- 07.06.2018, 19:43 --

grizzly в сообщении #1317987 писал(а):

Ваши требования примерно эквивалентны тому, что название цвета нужно угадать, например, на никому не известном языке.

Нет. Не этому эквивалентны.
Пусть мудрецы ЛЮБОЙ цвет могут назвать словами. И все эти слова все мудрецы и судьи понимают одинаково.
Но какие именно N-цветов будут\могут использованы - неизвестно.

[grizzly]

EUgeneUS в сообщении #1317989 писал(а):

Но какие именно N-цветов будут\могут использованы - неизвестно.

И что? Неужели есть сомнения, что в такой формулировке задача не имеет решения?

[Dan B-Yallay]

(Оффтоп)

EUgeneUS в сообщении #1317989 писал(а):

Понятно, что предполагаем, что цвет бедра испуганной нимфы определен, например, в RGB.

На всякий случай, если вдруг понадобится:

Вложение:

nymphe_effrayee.png [ 23.13 Кб | Просмотров: 3138 ]