Загадка белые черные колпаки



Загадка белые черные колпаки

Институт логики, Smi@logic.ru

Задача о мудрецах и колпаках.

Задача о трех мудрецах широко известна. Я встретился с ней еще в детстве и был очарован изяществом решения, но еще с тех пор осталось ощущение ловкого фокуса, когда понимаешь, что кролик не мог сам появиться в шляпе, но не успеваешь проследить за рукой фокусника. Недавно я решил попробовать записать решение в виде формального логического вывода, столкнулся с серьезными затруднениями и вынужден был заново ее обдумать. Напомню условие задачи.

Задача. Три мудреца поспорили, кто из них самый умный и обратились к четвертому, чтобы он их рассудил. Судья сообщил мудрецам, что у него есть три белых колпака и два черных, после чего надел каждому колпак на голову так, чтобы каждый видел только колпаки двух других мудрецов. Мудрецам требовалось угадать цвет колпака на собственной голове. Через некоторое время один из мудрецов сообщил, что у него на голове белый колпак и выиграл состязание. Как он смог догадаться?

Классическое решение. Если мудрец видит, что у его соперников черные колпаки (Ситуация 1), то он может смело утверждать, что у него — белый колпак, поскольку оба черных уже заняты.

Если мудрец видит на головах соперников черный и белый колпаки (ситуация 2), то он может рассудить так: «Если у меня на голове колпак черный, то мудрец в белом колпаке видит перед собой два черных колпака (находится в ситуации 1), и должен сообразить, что на нем колпак белый. Но он молчит, значит на мне белый колпак».

Наконец, увидев перед собой обоих соперников в белых колпаках (ситуация 3), мудрец мог рассудить: «если у меня черный колпак, то любой из моих соперников видит перед собой черный и белый колпаки (ситуация 2), и должен понять, что на нем колпак белый. Но он молчит, значит на мне белый колпак».

Решение это захватывает рекурсивным погружением, где на каждом шаге добавляется информация о рассуждениях противников, и это щекочущее гипнотическое погружение разрешается ощущением изящества и ясной целостности решения. Но давайте отвлечемся от поэзии решения и попробуем проанализировать использованную в нем математическую модель и ее адекватность условиям задачи. Прежде всего, давайте проверим ее на граничных условиях, например, определим, в каких случаях мудрец должен сделать вывод, что на нем черный колпак.

Всего случаев могло быть ровно три:

— на соперниках колпаки черные;

— на одном сопернике черный колпак, на другом – белый;

— на обоих соперниках колпаки белые.

Это как раз описанные выше Ситуации 1, 2 и 3. В каждой из этих ситуаций, в соответствии с приведенным выше решением, мудрец должен прийти к заключению, что у него на голове белый колпак.

Наша стройная конструкция рушится, как только мы осознаем, что перечисленные выше ситуация 1, ситуация 2 и ситуация 3 являются исчерпывающим списком возможных вариантов, то есть, действуя по описанному выше методу, мудрец в любом случае должен прийти к заключению, что колпак на нем белый. Значит, мудрец должен после начала испытания посмотреть на своих соперников и, независимо от увиденного, через некоторое время объявить, что на нем белый колпак. Правда, совершенно непонятно, через какой именно промежуток времени надо делать заявление.

В классическом решении неявно использованы очень сильные допущения, которые никак не вытекают из условий задачи:

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

2. Предполагается, что мудрецы думают с примерно одинаковой, или, по крайней мере, с предсказуемой скоростью. Без такого допущения невозможно установить время, необходимое для соответствующей цепочки рассуждений. Считается, что если мудрец дошел в своих рассуждениях до некоторого вывода, то и остальные сделали то же. Предположение это очень сильное, но с ним кое-как можно смириться, — раз уж эти трое никак не могли решить, кто из них умнее.

3. Предполагается, что мудрецы приступают к решению задачи только после того, как на них надели колпаки, и не пытаются продумать варианты решения до начала испытания. Это очень странно, поскольку при испытании возможны только три описанные выше варианта, и представляется естественным продумать варианты ответа заранее. Но такая возможность радикально противоречит замыслу автора задачи, поскольку, стоит мудрецам заранее задуматься, как они отвергнут навязываемый им метод рассуждения.

4. Предполагается, что мудрец, догадавшись, какой колпак у него на голове, поспешит немедленно об этом сообщить. Если мудрец молчит, то считается, что он не догадался о цвете своего колпака. Но ведь его задача — не определить цвет колпака, а доказать свое умственное превосходство. Велика ли заслуга, увидев перед собой обоих соперников в черных колпаках, догадаться, что у тебя на голове — белый колпак? Этот мудрец просто оказался в лучших условиях по сравнению с другими, и быстрый ответ не докажет превосходства. Вот если в такой ситуации промолчать, то один из соперников может воспользоваться методом, предложенным автором задачи, и ошибочно решит, что он находится в ситуации 3, даст неверный ответ и продемонстрирует свою глупость.

Еще:  Загадки про воздушный шар с корзиной для полетов

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

Осмелюсь предложить несколько вариантов объяснения.

Решение 1. Победителю повезло (ситуация б). Но это ставит под сомнение добросовестность судьи (он должен был поставить всех в равное положение), а во-вторых, не свидетельствует о наличии мудрости у победителя, — ведь ему повезло, поэтому Решение 1 нельзя признать удовлетворительным.

Решение 2. Обдумав заблаговременно ситуации 1-3-г, победитель мог заметить, что в любом случае, вскоре после начала состязания, он должен заявить, что на нем белый колпак. И тут важно было произнести это раньше других, иначе он все равно проиграет. Поэтому лучшим решением было сразу же после начала состязания заявить, что он в белом колпаке, чтобы успеть сделать это раньше других.

Заметим, что это решение предполагает «одинаковомыслие» мудрецов (но большую предусмотрительность победителя).

Кроме того, такой победитель способен на разумный риск, что только подтверждает его мудрость.

Решение 3. Как это бывает свойственно мудрецам, победитель мог посмотреть на ситуацию со стороны. Судья — если он мудр и справедлив — должен был поставить состязающихся в равные условия, а это возможно только в том случае, когда все они в одинаковых белых колпаках.

Мне это решение кажется самым мудрым и справедливым.

Решение 4. Победитель определил цвет колпака по расположению звезд.

Такая способность несомненно доказывает его мудрость, но для меня остается непостижимой.

Источник

Остаться в живых

В одной деспотичной стране король созвал всех придворных мудрецов (количество их не принципиально, поэтом без ограничения общности будем считать, что их 20 человек) и объявил им следующее:
Завтра их всех построят в одну колонну и завяжут глаза, затем каждому на голову наденут колпак черного или белого цвета и снимут повязки. Каждый сможет видеть цвет колпака стоящих впереди него, но не может видеть свой колпак и колпаки тех, кто сзади. Каждому в колонне зададут вопрос: Какого цвета на тебе колпак? Если мудрец ответит правильно, его оставят в живых. Если неправильно, значит он недостоин быть мудрецом и его казнят.

Какую стратегию надо избрать мудрецам, чтобы как можно больше из них остались в живых? На размышления и совещания им дается ровно одна ночь.

Ответ: Вот стратегия, которой надо придерживаться мудрецам: последний в колонне мудрец считает количество черных колпаков впереди себя. Если это количество четное, то он говорит, что на нем черный колпак, если нечетное, то говорит, что колпак белый. Точного ответа он все равно не знает, поэтому отвечает именно так (такая была выработана стратегия). Допустим, число было четным, и он сказал, что колпак черный. Если угадал — остался в живых, не угадал — значит, не повезло.

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

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

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

Источник

Haskell. Задача о мудрецах и колпаках

Три мудреца поспорили, кто из них самый мудрый. Чтобы выяснить правду, каждый надел на голову колпак случайного цвета. Каждый мудрец видит цвета колпаков своих оппонентов, но не видит свой собственный. Побеждает тот, кто сможет определить цвет своего колпака.

Так получилось, что все трое вытянули колпаки белого цвета. Мимо проходящий прохожий сообщает им: «на одном из вас надет белый колпак». Через некоторое время самый умный из мудрецов воскликнул: «на мне белый колпак. ».

Как он об этом догадался?

Как же он об этом догадался?

Эту задачу можно сформулировать для любого количества мудрецов. Давайте рассмотрим самый простой вариант.

Сидят два мудреца, на каждом надет белый колпак. Оба знают, что существует, как минимум, один колпак белого цвета. Тогда один из мудрецов рассуждает: «если бы на мне был колпак любого не белого цвета, то мой оппонент уже бы догадался, что белый колпак на нем. Но он молчит. Значит белый колпак на мне!»

Еще:  Загадка с ответом полицейский

Когда мудрецов трое, то один из них рассуждает так: «Если на мне колпак не белого цвета, то второй мудрец будет думать так. … (далее идут рассуждения из задачи про двух мудрецов) . один из них бы догадался, что белый колпак на нем. Но они оба молчат. Значит мое первое предположение не верно, и на мне белый колпак!»

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

Формулировка задачи

Имеется трое мудрецов. На каждом надет колпак либо черного, либо белого цвета. Каждый знает цвета своих оппонентов, но не знает свой собственный.

В первый день им сообщают, что существует, как минимум, один белый колпак. Они весь день думают и в конце дня независимо друг от друга голосуют. Они выдают один из двух возможных результатов: «я знаю свой цвет», «я не знаю свой цвет».

На второй день они знакомятся с «результатами голосования» каждого из оппонентов. Затем они снова весь день думают и в конце дня снова голосуют.

Вопрос. Как проголосует каждый из мудрецов в каждый из дней при различных начальных условиях?

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

Состояние нашего мира (какой колпак на ком надет) описывается с помощью типа State. В переменной fullState мы храним список всех возможных состояний.

Тип StateInfo описывает некоторые сведения, которые мы можем вычислить из состояния мира. Например, с помощью stateInfoColor мы можем вычленить цвет колпака для конкретного мудреца. А с помощью stateInfoAnyWhite мы вычисляем, верно ли для данного состояния утверждение, что все колпаки белые.

Далее идут более сложные конструкции.

Тип Knowledge описывает некоторое «знание» о мире. Как мы увидим дальше, тип Knowledge будет по-разному комбинироваться с типом StateInfo. Это очень важный тип. Остановлюсь на нем поподробнее.

Как видно из определения Knowledge, это функция, которая из состояния мира вычисляет некоторую фильтрующую функцию. Т.е. мы передаем «настоящее» состояние мира, а она выдает некоторое подмножество возможных состояний, которые не противоречат нашим знаниям.

Например, функция knowledgeAboutColor1 представляет собой знание о цвете первого мудреца. Если я передам состояние [White, Black, Black], в котором цвет первого мудреца белый, то она вернет функцию, которая отфильтрует все состояния, в котором первый мудрец имеет другой цвет.

У нас не будет специальных структур, обозначающих мудреца. Мы будем рассуждать в терминах «знаний». Вот пример таких рассуждений.

знания первого мудреца в первый день = знание о втором цвете + знание о третьем цвете + знание о том, что один из колпаков белый

знания мудреца на следующий день = знания мудреца в предыдущий день + новые знания

Вот еще несколько вспомогательных функций в терминах Knowledge и StateInfo.

Функция knowledgeAnd просто комбинирует знания в одно.

Действие функции stateInfoList очевидно из её типа.

Третья функция knowledgeImply поинтересней. Это некоторое утверждение о том, что из первого знания вытекает второе знание.

Далее пойдет код, относящийся непосредственно к задаче.

Тип KnowledgeList — это что-то вроде списка мудрецов. Для каждого мудреца у нас определена пара знаний. Первый элемент — это его текущие знания. Второй элемент — это то, что он пытается выяснить, а именно, цвет своей шляпы.

Функция knowledgeInsight вычисляет, смог ли конкретный мудрец определить свой цвет. Другими словами, вытекают ли знания, к которым он стремится, из тех знаний, которыми он обладает. Используется наша волшебная функция knowledgeImply.

Переменные manStart_1, manStart_2, manStart_3 — это начальные знания соответствующих мудрецов.

Переменная knowledgeList_1 — это список всех мудрецов на первый день (их знания).

Переменная insightList_1 — это результаты голосования в первый день.

Имея результаты голосования, мы можем составить новый список знаний мудрецов.

С помощью функции addNewKnowledge мы пробегаемся по всем мудрецам и добавляем им новые знания (результаты голосования за предыдущий день).

Повторяя процедуру несколько раз, получаем переменные insightList_1, insightList_2 и insightList_3 — результаты голосований за три дня.

Последний штрих — это вывести результат для конкретного начального состояния.

Результат

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

В первые два дня мудрецы думали. А на третий день они втроем заявили, что знают свой цвет.

К сожалению, выявить «самого умного» не удалось. Мы предполагаем, что все мудрецы максимально умные и используют всю имеющуюся информацию по полной. В своих рассуждениях они все используют тот факт, что другие мудрецы тоже максимально умные.

Что будет, если один из колпаков будет черным?

Еще:  Загадки века вождь и провидцы 2020

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

А вот пример с двумя черными колпаками.

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

Заключение

Полученный пример является хорошей отправной точкой для дальнейших исследований и экспериментов. С помощью него можно решать и другие задачи в стиле «я знаю, что он знает, что я знаю ..».

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

Источник

Загадка про колпаки

Profile PM

Жил-был в одном царстве-государстве Король.
И как то созвал он 30 мудрецов и сказал им, что завтра он всех их хитро казнит.
Оденет в колпаки белого и черного цвета и поставит в линию
(Ка-ждый мудрец будет видеть колпаки всех, кто стоит впереди него, но не будет видеть свой колпак).
Затем каждому по очереди, начиная с конца, будут задаваться вопрос: «Какого цвета на тебе колпак?».
Если мудрец отвечает неправильно — ему сразу же отрубают голову
(Остальные мудрецы слышат, что он сказал и знают, отрубили ли ему голову).
Скольким мудрецам точно удастся выжить и как это им сделать?

кто знает разгадку?

Profile PM

Profile PM

все колпаки раздаются случайным образом.

могут быть все черный и один белый, либо 50/50 либо ваще рандомайзом.
стоят не поочереди а тоже рандомайзом (вразброс от балды)

Profile PM

Profile PM

C55.Sniper писал : Вот стратегия, которой надо придерживаться мудрецам: последний в шеренге мудрец считает количество черных колпаков впереди себя.
Цитата : могут быть все черный и один белый, либо 50/50 либо ваще рандомайзом.

Profile PM

Profile PM

Цитата : Ответы мудрецов будут меняться в зависимости от того, что они видят.

Вернее от того, что они слышат.

Profile PM

30: говорит цвет впереди стоящего ГРОМКО (например БЕЛЫЙ. ) — совпал с его выжил (зашибись. ) нет. селяви..

29: знает что у него БЕЛЫЙ 100% (но он должен оповестить следующего какой у того цвет). Поэтому если цвет совпадает с его (в данном случае белый — так же громко говорит БЕЛЫЙ. ) Он жив.
Если нет (впереди черный) он говорит белый, но тииихо.

ТО есть смысл в том что если цвет впередистоящего совпадает с его он называет этот цвет громко, если же цвета разные он говорит свой цвет (а он его знает 100%) но тихо. Таком образом информирует впередистоящего что у него цвет другой.

Потери: максимум 1. минимум 0 (зависит от того совпадут цвета 30 и 29).

Profile PM

Profile PM

Мячиков писал(а) : Nezlobin , Вы решаете задачу отличную от той, что Вы сформулировали. Скажите, почему так случилось?

почему другую. ее и решил

Profile PM

Потому что в условиях задачи написано одно, а решение Вы представляете для другой задачи.

Profile PM

Потому что в условиях задачи написано одно, а решение Вы представляете для другой задачи.

В чем разные то.

Вот решение: (конкретно чем оно противоречит условиям).

30: говорит цвет впереди стоящего ГРОМКО (например БЕЛЫЙ. ) — совпал с его выжил (зашибись. ) нет. селяви..

29: знает что у него БЕЛЫЙ 100% (но он должен оповестить следующего какой у того цвет). Поэтому если цвет совпадает с его (в данном случае белый — так же громко говорит БЕЛЫЙ. ) Он жив.
Если нет (впереди черный) он говорит белый, но тииихо.

ТО есть смысл в том что если цвет впередистоящего совпадает с его он называет этот цвет громко, если же цвета разные он говорит свой цвет (а он его знает 100%) но тихо. Таком образом информирует впередистоящего что у него цвет другой.

вот смотри (пример на кошках):

30 (черный) говорит БЕЛЫЙ (ГРОМКО) не совпал с его (ему шандец. ну и ладно. в раю лучше будет..аминь)

29 (белый) говорит БЕЛЫЙ (ГРОМКО) так как его цвет совпал с 28

28 (белый) говорит белый (тииихо) так как впереди у него черный. и он информирует впереди стоящего об этом произнося свой цвет тихо.

27 (черный) говорит ЧЕРНЫЙ (ГРОМКО) так как 28 сказал (белый тихо он знает что у него черный, но перед ним тоже черный и он говорит ЧЕРНЫЙ ГРОМКО)

26 (черный) говорит черный (тихо)

25 (белый) знает что у него белый (так как 26 сказал свой цвет черный тихо). и так далее.

Источник