Три мудреца поспорили, кто из них самый мудрый. Чтобы выяснить правду, каждый надел на голову колпак случайного цвета. Каждый мудрец видит цвета колпаков своих оппонентов, но не видит свой собственный. Побеждает тот, кто сможет определить цвет своего колпака.Существует определенная последовательность рассуждений, которая привела нашего мудреца к верному ответу. Мы попытаемся смоделировать эти рассуждения.
Так получилось, что все трое вытянули колпаки белого цвета. Мимо проходящий прохожий сообщает им: «на одном из вас надет белый колпак». Через некоторое время самый умный из мудрецов воскликнул: «на мне белый колпак!!!».
Как он об этом догадался?
Как же он об этом догадался?
Эту задачу можно сформулировать для любого количества мудрецов. Давайте рассмотрим самый простой вариант.
Сидят два мудреца, на каждом надет белый колпак. Оба знают, что существует, как минимум, один колпак белого цвета. Тогда один из мудрецов рассуждает: «если бы на мне был колпак любого не белого цвета, то мой оппонент уже бы догадался, что белый колпак на нем. Но он молчит. Значит белый колпак на мне!»
Когда мудрецов трое, то один из них рассуждает так: «Если на мне колпак не белого цвета, то второй мудрец будет думать так. … (далее идут рассуждения из задачи про двух мудрецов) ... один из них бы догадался, что белый колпак на нем. Но они оба молчат. Значит мое первое предположение не верно, и на мне белый колпак!»
По индукции мы можем распространить данные рассуждения на любое количество мудрецов. Далее в статье, мы будем моделировать ситуацию с тремя мудрецами.
Формулировка задачи
В нашей изначальной формулировке задача не до конца корректна. Не понятно, сколько должно пройти времени, чтобы сделать вывод, что другой мудрец так и не догадался о цвете своего колпака. Давайте, я переформулирую задачу более корректно.
Имеется трое мудрецов. На каждом надет колпак либо черного, либо белого цвета. Каждый знает цвета своих оппонентов, но не знает свой собственный.
В первый день им сообщают, что существует, как минимум, один белый колпак. Они весь день думают и в конце дня независимо друг от друга голосуют. Они выдают один из двух возможных результатов: «я знаю свой цвет», «я не знаю свой цвет».
На второй день они знакомятся с «результатами голосования» каждого из оппонентов. Затем они снова весь день думают и в конце дня снова голосуют.
и так далее.
Вопрос. Как проголосует каждый из мудрецов в каждый из дней при различных начальных условиях?
Код
Для начала опишем наши основные типы, с которыми мы будем работать.
data Color = Black | White deriving (Show, Eq)
type State = [Color]
fullState :: [State]
fullState = do
c1 <- [Black, White]
c2 <- [Black, White]
c3 <- [Black, White]
return [c1, c2, c3]
type StateInfo a = State -> a
stateInfoColor :: Int -> StateInfo Color
stateInfoColor i state = state !! i
stateInfoAnyWhite :: StateInfo Bool
stateInfoAnyWhite state = or $ map (\c -> c == White) state
Состояние нашего мира (какой колпак на ком надет) описывается с помощью типа State. В переменной fullState мы храним список всех возможных состояний.
Тип StateInfo описывает некоторые сведения, которые мы можем вычислить из состояния мира. Например, с помощью stateInfoColor мы можем вычленить цвет колпака для конкретного мудреца. А с помощью stateInfoAnyWhite мы вычисляем, верно ли для данного состояния утверждение, что все колпаки белые.
Далее идут более сложные конструкции.
type Knowledge = State -> (State -> Bool)
knowledgeAbout :: (Eq a) => StateInfo a -> Knowledge
knowledgeAbout stateInfo state = let info = stateInfo state in \s -> stateInfo s == info
knowledgeIsTrue :: StateInfo Bool -> Knowledge
knowledgeIsTrue si _ state = si state
knowledgeAboutColor1 :: Knowledge
knowledgeAboutColor1 = knowledgeAbout $ stateInfoColor 0
knowledgeAboutColor2 :: Knowledge
knowledgeAboutColor2 = knowledgeAbout $ stateInfoColor 1
knowledgeAboutColor3 :: Knowledge
knowledgeAboutColor3 = knowledgeAbout $ stateInfoColor 2
Тип Knowledge описывает некоторое «знание» о мире. Как мы увидим дальше, тип Knowledge будет по-разному комбинироваться с типом StateInfo. Это очень важный тип. Остановлюсь на нем поподробнее.
Как видно из определения Knowledge, это функция, которая из состояния мира вычисляет некоторую фильтрующую функцию. Т.е. мы передаем «настоящее» состояние мира, а она выдает некоторое подмножество возможных состояний, которые не противоречат нашим знаниям.
Например, функция knowledgeAboutColor1 представляет собой знание о цвете первого мудреца. Если я передам состояние [White, Black, Black], в котором цвет первого мудреца белый, то она вернет функцию, которая отфильтрует все состояния, в котором первый мудрец имеет другой цвет.
У нас не будет специальных структур, обозначающих мудреца. Мы будем рассуждать в терминах «знаний». Вот пример таких рассуждений.
знания первого мудреца в первый день = знание о втором цвете + знание о третьем цвете + знание о том, что один из колпаков белый
знания мудреца на следующий день = знания мудреца в предыдущий день + новые знания
Вот еще несколько вспомогательных функций в терминах Knowledge и StateInfo.
knowledgeAnd :: [Knowledge] -> Knowledge
knowledgeAnd list stateTrue = \s -> and $ map (\f -> f stateTrue s) list
stateInfoList :: [StateInfo a] -> StateInfo [a]
stateInfoList sil state = map (\si-> si state) sil
knowledgeImply :: Knowledge -> Knowledge -> StateInfo Bool
knowledgeImply knowledge1 knowledge2 state = and $ map (\(b1, b2) -> not $ and [b1, not b2]) $ map (\s -> (knowledge1 state s, knowledge2 state s)) fullState
Функция knowledgeAnd просто комбинирует знания в одно.
Действие функции stateInfoList очевидно из её типа.
Третья функция knowledgeImply поинтересней. Это некоторое утверждение о том, что из первого знания вытекает второе знание.
Далее пойдет код, относящийся непосредственно к задаче.
type KnowledgeList = [(Knowledge, Knowledge)]
insightList :: KnowledgeList -> StateInfo [Bool]
insightList knowledgeList = stateInfoList $ map knowledgeInsight knowledgeList
knowledgeInsight :: (Knowledge, Knowledge) -> StateInfo Bool
knowledgeInsight (currentKnowledge, targetKnowledge) = knowledgeImply currentKnowledge targetKnowledge
manStart_1 = knowledgeAnd [knowledgeAboutColor2, knowledgeAboutColor3, knowledgeAbout stateInfoAnyWhite]
manStart_2 = knowledgeAnd [knowledgeAboutColor1, knowledgeAboutColor3, knowledgeAbout stateInfoAnyWhite]
manStart_3 = knowledgeAnd [knowledgeAboutColor1, knowledgeAboutColor2, knowledgeAbout stateInfoAnyWhite]
knowledgeList_1 :: KnowledgeList
knowledgeList_1 = [(manStart_1, knowledgeAboutColor1), (manStart_2, knowledgeAboutColor2), (manStart_3, knowledgeAboutColor3)]
insightList_1 :: StateInfo [Bool]
insightList_1 = insightList knowledgeList_1
Тип KnowledgeList — это что-то вроде списка мудрецов. Для каждого мудреца у нас определена пара знаний. Первый элемент — это его текущие знания. Второй элемент — это то, что он пытается выяснить, а именно, цвет своей шляпы.
Функция knowledgeInsight вычисляет, смог ли конкретный мудрец определить свой цвет. Другими словами, вытекают ли знания, к которым он стремится, из тех знаний, которыми он обладает. Используется наша волшебная функция knowledgeImply.
Переменные manStart_1, manStart_2, manStart_3 — это начальные знания соответствующих мудрецов.
Переменная knowledgeList_1 — это список всех мудрецов на первый день (их знания).
Переменная insightList_1 — это результаты голосования в первый день.
Имея результаты голосования, мы можем составить новый список знаний мудрецов.
addNewKnowledge :: Knowledge -> KnowledgeList -> KnowledgeList
addNewKnowledge newKnowledge knowledgeList = flip map knowledgeList $ \(oldKnowledge, targetKnowledge) -> (knowledgeAnd [oldKnowledge, newKnowledge], targetKnowledge)
knowledgeList_2 :: KnowledgeList
knowledgeList_2 = addNewKnowledge (knowledgeAbout insightList_1) knowledgeList_1
insightList_2 :: StateInfo [Bool]
insightList_2 = insightList knowledgeList_2
knowledgeList_3 :: KnowledgeList
knowledgeList_3 = addNewKnowledge (knowledgeAbout insightList_2) knowledgeList_2
insightList_3 :: StateInfo [Bool]
insightList_3 = insightList knowledgeList_3
С помощью функции addNewKnowledge мы пробегаемся по всем мудрецам и добавляем им новые знания (результаты голосования за предыдущий день).
Повторяя процедуру несколько раз, получаем переменные insightList_1, insightList_2 и insightList_3 — результаты голосований за три дня.
Последний штрих — это вывести результат для конкретного начального состояния.
startState = [White, White, White]
main = do
putStr $ "day 1 result: " ++ (show $ insightList_1 startState) ++ "\n"
putStr $ "day 2 result: " ++ (show $ insightList_2 startState) ++ "\n"
putStr $ "day 3 result: " ++ (show $ insightList_3 startState) ++ "\n"
Результат
Для начала рассмотрим самый сложный и интересный вариант, когда все колпаки белые.
startState = [White, White, White]
{- result:
day 1 result: [False,False,False]
day 2 result: [False,False,False]
day 3 result: [True,True,True]
-}
В первые два дня мудрецы думали. А на третий день они втроем заявили, что знают свой цвет.
К сожалению, выявить «самого умного» не удалось. Мы предполагаем, что все мудрецы максимально умные и используют всю имеющуюся информацию по полной. В своих рассуждениях они все используют тот факт, что другие мудрецы тоже максимально умные.
Что будет, если один из колпаков будет черным?
startState = [Black, White, White]
{- result:
day 1 result: [False,False,False]
day 2 result: [False,True,True]
day 3 result: [True,True,True]
-}
Мы видим, что два мудреца в белом уже на второй день смогли определить свой цвет. Не удивительно, ведь для них вся ситуация сводится к задаче про двух мудрецов. Глядя на их реакцию, оставшийся мудрец смог определить и свой цвет.
А вот пример с двумя черными колпаками.
startState = [Black, Black, White]
{- result:
day 1 result: [False,False,True]
day 2 result: [True,True,True]
day 3 result: [True,True,True]
-}
Как видим, мудрец в белом колпаке на первый же день смог определить свой цвет. И это четкий сигнал для остальных мудрецов, что у них черные колпаки.
data Color = Black | White deriving (Show, Eq)
type State = [Color]
fullState :: [State]
fullState = do
c1 <- [Black, White]
c2 <- [Black, White]
c3 <- [Black, White]
return [c1, c2, c3]
type StateInfo a = State -> a
stateInfoColor :: Int -> StateInfo Color
stateInfoColor i state = state !! i
stateInfoAnyWhite :: StateInfo Bool
stateInfoAnyWhite state = or $ map (\c -> c == White) state
-- ===================
type Knowledge = State -> (State -> Bool)
knowledgeAbout :: (Eq a) => StateInfo a -> Knowledge
knowledgeAbout stateInfo state = let info = stateInfo state in \s -> stateInfo s == info
knowledgeIsTrue :: StateInfo Bool -> Knowledge
knowledgeIsTrue si _ state = si state
knowledgeAboutColor1 :: Knowledge
knowledgeAboutColor1 = knowledgeAbout $ stateInfoColor 0
knowledgeAboutColor2 :: Knowledge
knowledgeAboutColor2 = knowledgeAbout $ stateInfoColor 1
knowledgeAboutColor3 :: Knowledge
knowledgeAboutColor3 = knowledgeAbout $ stateInfoColor 2
-- ===================
knowledgeAnd :: [Knowledge] -> Knowledge
knowledgeAnd list stateTrue = \s -> and $ map (\f -> f stateTrue s) list
stateInfoList :: [StateInfo a] -> StateInfo [a]
stateInfoList sil state = map (\si-> si state) sil
knowledgeImply :: Knowledge -> Knowledge -> StateInfo Bool
knowledgeImply knowledge1 knowledge2 state = and $ map (\(b1, b2) -> not $ and [b1, not b2]) $ map (\s -> (knowledge1 state s, knowledge2 state s)) fullState
-- ==================
type KnowledgeList = [(Knowledge, Knowledge)]
insightList :: KnowledgeList -> StateInfo [Bool]
insightList knowledgeList = stateInfoList $ map knowledgeInsight knowledgeList
knowledgeInsight :: (Knowledge, Knowledge) -> StateInfo Bool
knowledgeInsight (currentKnowledge, targetKnowledge) = knowledgeImply currentKnowledge targetKnowledge
manStart_1 = knowledgeAnd [knowledgeAboutColor2, knowledgeAboutColor3, knowledgeAbout stateInfoAnyWhite]
manStart_2 = knowledgeAnd [knowledgeAboutColor1, knowledgeAboutColor3, knowledgeAbout stateInfoAnyWhite]
manStart_3 = knowledgeAnd [knowledgeAboutColor1, knowledgeAboutColor2, knowledgeAbout stateInfoAnyWhite]
knowledgeList_1 :: KnowledgeList
knowledgeList_1 = [(manStart_1, knowledgeAboutColor1), (manStart_2, knowledgeAboutColor2), (manStart_3, knowledgeAboutColor3)]
insightList_1 :: StateInfo [Bool]
insightList_1 = insightList knowledgeList_1
-- ===============
addNewKnowledge :: Knowledge -> KnowledgeList -> KnowledgeList
addNewKnowledge newKnowledge knowledgeList = flip map knowledgeList $ \(oldKnowledge, targetKnowledge) -> (knowledgeAnd [oldKnowledge, newKnowledge], targetKnowledge)
knowledgeList_2 :: KnowledgeList
knowledgeList_2 = addNewKnowledge (knowledgeAbout insightList_1) knowledgeList_1
insightList_2 :: StateInfo [Bool]
insightList_2 = insightList knowledgeList_2
knowledgeList_3 :: KnowledgeList
knowledgeList_3 = addNewKnowledge (knowledgeAbout insightList_2) knowledgeList_2
insightList_3 :: StateInfo [Bool]
insightList_3 = insightList knowledgeList_3
-- =============
startState = [White, White, White]
main = do
putStr $ "day 1 result: " ++ (show $ insightList_1 startState) ++ "\n"
putStr $ "day 2 result: " ++ (show $ insightList_2 startState) ++ "\n"
putStr $ "day 3 result: " ++ (show $ insightList_3 startState) ++ "\n"
Заключение
Полученный пример является хорошей отправной точкой для дальнейших исследований и экспериментов. С помощью него можно решать и другие задачи в стиле «я знаю, что он знает, что я знаю ..».
В моем коде количество мудрецов и дней захардкожено. Я специально не стал его обобщать на N мудрецов и N дней, чтобы было понятнее. Возможно, в следующей статье я перепишу его через комонады.
Комментарии (38)
neurocore
22.02.2018 09:37Я слышал вариант в котором 3 белых и 2 чёрных колпака и нет искусственно добавленного человека, который сообщает цвет одного из них. Мудрецы долго сидели и думали, пока один из них не заявил, что знает ответ, тогда и остальные узнали свой цвет.
Bonart
22.02.2018 19:46Это из старой советской книги "Хочу все знать". Кстати, там еще обосновано, почему все колпаки на мудрецах должны быть одного цвета.
Alexsandr_SE
22.02.2018 11:22Никогда не понимал таких задач. А если колпаки будут белый синий и розовый, а в ящике откуда они их брали еще три десятка возможных цветов?
Не вижу в упор логику решения. А вот решение подразумевает дополнительные ограничения задачи. Откуда эти ограничения взялись если в условии колпаки любого цвета и копаков соответственно много?CheY
22.02.2018 13:38«В условии» сказано, что колпаки могут быть разного цвета (и это известно мудрецам), но конкретно в этом случае были выбраны колпаки одинакового белого цвета. Это никакое не дополнительное ограничение, а часть условия, что и делает задачу решаемой.
playermet
23.02.2018 13:56Это часть условия, неизвестная самому мудрецу, а именно его мысли и предлагается угадать.
Kesha_kh
22.02.2018 12:39Если бы на нем был колпак другого цвета, то прохожий сказал бы что на одном из них колпак %цвет_нейм, ибо %цвет_нейм бросался бы в глаза. А так если на остальных белый значит и на мудреце колпак тоже белый
yul
22.02.2018 13:11второй мудрец будет думать так. … (далее идут рассуждения из задачи про двух мудрецов)
они не могут рассуждать также, как в задаче про двух мудрецов, потому что перед каждым из них два мудреца с двумя колпаками, а не один.Overlordff
22.02.2018 13:33У нас есть предположение, что на первом мудреце не белый колпак (мы должны это опровергнуть). Оба других мудреца видят, что у первого не белый колпак. В то же время, они оба знают, что белый колпак обязательно существует на одном из них. Другими словами, если предложение верно, то можно вычеркнуть первого мудреца из системы, так как его наличие не влияет на результат.
Если перед вами 100 мудрецов с небелыми колпаками и один с белым, и вы видите, что мудрец с белым колпаком не догадывается что он с белым, то вывод очевиден — вы с белым колпаком тоже.Alexsandr_SE
22.02.2018 14:43+1Если перед вами 100 мудрецов с не белыми колпаками и один белый, то откуда уверенность, что у вас не синий, красный зеленый???
Мы подошли к тому, что у нас всего два цвета возможно, а в условии любые цвета. Значить мы не можем допустить вольности того, что белый колпак обязательно надет на мудреца который видит у кого-то белый колпак и молчит. Может тот мудрец вообще белых колпаков нигде не видит, а у него вообще салатовый, а у всех свои цвета одеты.FreeNickname
22.02.2018 19:55Я вначале тоже не понял) Если перед вами 100 мудрецов с не белыми колпаками, и один с белым (вы, получается, 102-й мудрец, и на вас какой-то колпак), и все мудрецы знают, что есть как минимум один мудрец с белым колпаком, это означает, что возможны две ситуации:
1) Белый колпак на мудреце, на которого вы смотрите, и только на нём. Но в этом случае этот мудрец бы увидел, что у всех остальных колпаки не белые, А должен быть хотя бы один мудрец с белым колпаком. Значит, белый колпак у него, о чём он бы и объявил. Но он этого не делает. Следовательно, он не уверен, на нём белый колпак или нет. Значит,
2) Белый колпак на нём и на вас (цвета всех остальных известны вам обоим, и они не белые).
3) Белый колпак только на том самом мудреце, но он глупый ?\_(?)_/?
Следует отметить, что задача, как мы её видим, имеет решение. Однако, с задачей с точки зрения мудрецов – вытащить случайного цвета колпак и мистическим образом определить свой цвет – не всё так однозначно. Всё бы целиком зависело от того, что им скажут случайные прохожие. И условия для мудрецов вряд ли были бы равными, как тут.Alexsandr_SE
23.02.2018 09:15В условии нет ограничений по цветам. В условии задачи обязательные цвета не указаны.
В оригинальной задаче есть ограничивающие условия (всего два цвета). В задаче из материала ограничивающих условий никаких нет, есть только дополнение, что один колпак белый. Решения она как по мне просто не имеет.
этому просто не имеет.FreeNickname
23.02.2018 15:24Так у нас тоже, получается, два варианта: белый и не белый (любой другой). С такими начальными условиями мудрецы могут определить только два этих варианта. При этом если они понимают, что у них не белый, то они не знают, какой у них цвет, и им нужна дополнительная информация. Но если цвет белый, то они сразу могут это определить.
Alexsandr_SE
23.02.2018 16:09Как? Решение имеется только если остальные колпаки черные. т.е. задано условие всего 2-х цветов. Если кол-во цветов не ограничивается, то что-то сказать про свой цвет просто нельзя.
Получается задача. Из набора карандашей в 64 цвета и 300карандашей вытянули три карандаша. Один из них белый показали. Какого цвета остальные два карандаши?FreeNickname
23.02.2018 16:13Я же выше всё расписал. Карандаши, в отличие от мудрецов, не разговаривают. А если бы разговаривали, то белый карандаш увидел бы, что среди остальных карандашей ни одного белого нет, и понял бы, что он белый.
Если среди трёх два белых карандаша, то каждый карандаш бы посмотрел на другие карандаши и увидел бы среди них один белый. Но этот белый карандаш бы молчал. Но, как мы выяснили ранее, если бы он был единственным белым карандашом, он это сразу же понял. Значит, белых карандашей два. Значит второй – наш главный карандаш.
НЕ белые карандаши свой цвет на основе имеющейся информации определить действительно не смогут. Им бы потребовались дополнительные вопросы.Alexsandr_SE
23.02.2018 16:21По условию белые все были, а не все черные и прохожий сказал, что один белый. Поэтому белый не знает что он белый и при этом может видеть белый на другом. Но вариантов еще остается слишком много. Просто в условии пропущено ограничение по кол-ву цветов. Без этого задача не решаема как по мне. Ох уж эта логика.
FreeNickname
23.02.2018 16:39Любой из них может понять, что он белый безо всяких дополнительных ограничений. Цвета могут быть любыми. Вот смотрите.
Условия: трое мудрецов вытягивают три шляпы абсолютно любого цвета. Прохожий говорит, что как минимум один из них вытащил белую шляпу. Мудрецы могут видеть шляпы других, но не свою.
Возможные ситуации:
1) Первый вытащил красную, второй синюю, третий зелёную. Противоречие – прохожий солгал.
2) Первый вытащил крабовую, второй голубую, третий белую. Третий видит, что у остальных не белые, но они молчат. Значит, третий понимает, что у него белая шляпа. Остальные двое не знают свои цвета.
3) Первый вытащил фиолетовую шляпу, второй и третий – белые. Рассуждения второго: если бы белая шляпа была только у третьего, он бы сразу понял, что у него белая шляпа, но он молчит. Значит, белая шляпа и у меня тоже, потому что у первого фиолетовая. Второй и третий понимают, что у них белые шляпы, первый свой цвет не знает.
4) У всех белые шляпы. См. выше. Рассуждения первого: если бы на мне была не белая шляпа, то остальные бы поняли, что у них шляпы белые, следуя логике из шага 3. Но они этого не делают. Значит, у меня тоже белая шляпа. Значит, у всех шляпы белые.
Тут, конечно, в ситуации 4 делается предположение, что мудрецы 2 и 3 уже успели пройти все логические шаги. Т.е. неявно предполагается «синхронизация мудрецов».
Собственно, ниже об этом пишут: habrahabr.ru/post/349558/?reply_to=10684154#comment_10683766
Вариант загадки с неверными жёнами ниже в комментариях лишён этого недостатка путём введения искусственной синхронизации через дни.
Izulle
22.02.2018 13:45+1Давным-давно, когда мне первый раз рассказали эту байку, в таком варианте.
В некоем городе принято мужьям, узнавшим об неверности жены, до наступления следующего утра ее убивать. (Жестокие нравы ...). Так же в городе есть толкучка, где мужчины обсуждают чужих жен, но своих обсуждать запрещено.
В один прекрасный (скорее ужасный) день в город приежает странник. Послушав болтовню на толкучке, он во всеуслышанье объявляет «Не все жены в этом городе верны своим мужьям»
Можно доказать по индукции, что через N дней ( где N — количество неверных жен) все неверные жены будут утром найдены мертвыми.
Вопрос — что нового сообщел странник?lorc
22.02.2018 18:41Он запустил цепочку рассуждений.
Допустим в городе есть всего одна неверная жена. О ней говорят другие, но её муж ни о чем не догадывается, поэтому он считает что в городе неверных жен нету.
Когда странник опровергает его предположение, этот муж понимает что он — единственный кто ошибался и убивает свою жену в первый же день.
Допустим, в городе есть две неверных жены. Об этом знает весь город кроме двух мужей. Оба мужа неверных жен не знают о своих женах и думают что в городе всего одна неверная жена. Но убийства в первый день не происходит (каждый думает что его жена верна). Тогда понимают, что на самом деле неверных жен две и убивают их.
Ну и так далее, по индукции.
true_id1
22.02.2018 18:43Может я не правильно понимаю условие? но если все жены неверны. Мужья знают что все не верны, но думают что их верная. Новая информация ничего не дала они по прежнему думают что их верная.
lorc
22.02.2018 18:49Новая информация запустила счетчик. Они думают что в городе N-1 неверных жен (тогда как весь город кроме них знает что таких жен N) и ожидают убийств в день N-1. Когда этого не происходит, они понимают что их жена тоже неверна. Начните с N=1 и поймете.
FreeNickname
22.02.2018 22:27Объясните, пожалуйста, почему N дней? Вероятно, я неверно понимаю условие. В городе каждый мужчина знает всех чужих неверных жён. Но не знает, верна его жена или нет. Соответственно, если мужчина узнаёт, что в городе N неверных жён, а ему известны лишь N-1, значит последняя – его жена. Она единственная, о ком у него нет информации. При чём все обманутые мужья поймут это сразу же, и всех неверных жён убьют сразу же.
Это, кстати, вот ещё почему логично: если бы жён убивали по очереди, то тогда кто-то должен был бы убить свою жену первым. А условия для всех одинаковы. Значит, либо все убьют, либо никто не убьёт.
Или я что-то не так понял?
P.S. Хотя, с другой стороны, в задаче с колпаками условия тоже одинаковы, по идее. Просто как бы кто-то более сообразительный, кто-то менее. Но ничто не мешает всем мужьям додуматься одновременно. Индукция не нужна.lorc
22.02.2018 22:38Дело в то что жен не убивают по очереди. Их убивают одновременно в день N (если считать что странник произнес фразу в первый, а не в нулевой день).
Мужчина не знает что в городе N неверных жен. Это знание (в некотором роде) принес как раз странник. Жителю города известны либо N либо N-1 неверных жен поименно, но общего количества он не знает.
Дальше, мужчина пользуется индукцией. Если ему не изменяли, то он ожидает массовых убийств в день N (именно так и происходит). Если же ему изменяют, то он ожидает массовых убийств в день N-1, чего не случается. И тогда в день N (рано утром, по условию задачи) он понимает что он был среди рогоносцев и устраивает казнь.FreeNickname
22.02.2018 23:29Я всё равно не понимаю, почему их убьют в день N. Их можно всех убить сразу как только странник сказал, что в городе N неверных жён, ничего этому не препятствует. Ведь уже в первый день на толкучке все мужья уже знают либо N, либо N-1 неверную жену. В первый же день странник говорит, что в городе N неверных жён. Все мужья, знающие N-1 неверную жену, понимают, что их жена им неверна. На второй день N жён найдут мёртвыми. Зачем ждать N дней?
lorc
22.02.2018 23:43Нет, странник не говорит что в городе N неверных жен. Странник просто говорит что они там есть. И это запускает отсчет дней.
Представьте, что в городе всего одна неверная жена. Весь город знает о ней, кроме ее мужа. Муж думает что в городе нет неверных жен, ибо ему никто не может об этом сообщить по условиям задачи. Все счастливы. Потом приходит странник и говорит что в городе есть неверные жены. Муж той неверной понимает что он ошибался (а остальной город и так это знал) и идет убивать свою жену.
Теперь представим что таких женщин две. Их мужья думают что в городе одна неверная жена и они ожидают что второй убьет свою жену. Но этого не происходит в первый день, потому что каждый из них думает что рогоносец другой. На второй же день они поймут что они оба — рогоносцы и убьют свои жен.
Если в городе три неверных жены, то ни на первый, ни на второй день никто не умрет, зато на третий умрут все трое. И так далее.lorc
22.02.2018 23:58+2Кстати, переход к N=3 оказался сложнее, чем я думал.
И так, если рогоносцев трое, то каждый из них не знает о себе и думает что рогонсцев всего двое. Так же он считает что каждый из этих двух рогоносцев не знает про себя, но знает о другом, как я уже описал для случая N=2. Поэтому каждый из трех рогоносцев ожидает что два других убьют своих жен на второй день. Но этого не происходит. И тогда для них открывается страшная правда на третий день.
(Самое забавное, что если в городе всего одна неверная жена, но ее муж об этом не сообразит в первый день (или решит потроллить всех), то на второй день весь город убьет своих женщин).
Mingun
23.02.2018 00:04+1Вы неправильно понимаете то, что говорит странник. В том то и дело, что странник не говорит, что в городе
Nневерных жён. Он говорит только, что не все жёны верны. Это сообщение просто запускает счётчик дней до дня «икс». Все обманутые мужья думают, что в городеN-1неверная жена и, соответственно (по цепочке рассуждений из комментария lorc) ожидают, что днём «икс» станетN-1-й день после сообщения. Но убийств в этот день не происходит. Тогда каждый из них понимает, что изменяющих жён на одну больше и эта «дополнительная» жена может быть только его собственной (потому что про всех остальных жён они и так уже всё знают), поэтому день «икс» перемещается на деньN.
PS. Пока писал комментарий, немного опоздал, lorc уже ответил.
youngmysteriouslight
23.02.2018 01:32В жизни бывает, что рогоносец — олень.
Если в ночь на день N он не сделает умозаключение, то остальные не смогут правильно сделать свои умозаключения.
Вот, скажем, N=1. Некий муж считает, что N=1, но в первый день не случается убийства. Он рогоносец или единственный рогоносец — олень, который не догнал, что его жена неверная?
Это, конечно, не относится к исходной логической задачи, но тема устойчивости распределённых систем тоже весьма интересна.
upd. lorc уже написал про возможный троллинга для N=1.
true_id1
22.02.2018 18:49Делл. Там Н дней. При любом количистве в/н для каждого человека может быть только 2 схемы где его жена неверная или верная. Собственно на н день он узнает в каком он положении.
xGromMx
22.02.2018 14:50По идее ваш `fullState` можно заменить на `replicateM 3 [Black, White]`
По задаче, много математических и логических подходов (схожих как статье) освещается тут
www.youtube.com/watch?v=chGbsxG0VvU&list=PLQyMGME-L41OMrBSleF9HHzMb3urNXX96&index=1
ispcto
22.02.2018 18:44-1Осталось только строго обосновать фразу " я переформулирую задачу более корректно." И все будет в порядке. Ну и 4-й параграф про двух мудрецов тоже прекрасен.
Tsvetik
22.02.2018 20:07Вообще-то в этой задаче должен быть султан, который ведет счет. Иначе задача не решается.
al707
22.02.2018 20:18По-моему, исходная задача некорректно сформулирована, и не имеет решения. Если я прав, дайте кто-нибудь решаемую формулировку, интересно…
sasha1024
22.02.2018 23:21Вывод мудреца, воскликнувшего «на мне белый колпак!!!», основывается на неявном предположении, что оставшиеся (N-1) мудрецов достаточно «мудры», чтобы успеть решить к тому моменту задачу (N-1)-го порядка (но не «мудрее», чем он).
Aetet
Отличная статья, спасибо! Самое то для новичков.