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

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

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

    Как он об этом догадался?
    Существует определенная последовательность рассуждений, которая привела нашего мудреца к верному ответу. Мы попытаемся смоделировать эти рассуждения.

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

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

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

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

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

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

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

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

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

    и так далее.

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

    Код

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

    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
    • +1
      Отличная статья, спасибо! Самое то для новичков.
      • 0
        Я слышал вариант в котором 3 белых и 2 чёрных колпака и нет искусственно добавленного человека, который сообщает цвет одного из них. Мудрецы долго сидели и думали, пока один из них не заявил, что знает ответ, тогда и остальные узнали свой цвет.
        • 0

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

        • +2

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

          • +1
            «В условии» сказано, что колпаки могут быть разного цвета (и это известно мудрецам), но конкретно в этом случае были выбраны колпаки одинакового белого цвета. Это никакое не дополнительное ограничение, а часть условия, что и делает задачу решаемой.
            • +1
              Это часть условия, неизвестная самому мудрецу, а именно его мысли и предлагается угадать.
          • –1
            Если бы на нем был колпак другого цвета, то прохожий сказал бы что на одном из них колпак %цвет_нейм, ибо %цвет_нейм бросался бы в глаза. А так если на остальных белый значит и на мудреце колпак тоже белый
            • 0
              второй мудрец будет думать так. … (далее идут рассуждения из задачи про двух мудрецов)
              они не могут рассуждать также, как в задаче про двух мудрецов, потому что перед каждым из них два мудреца с двумя колпаками, а не один.
              • –1
                понял свою ошибку, забудьте
                • 0
                  У нас есть предположение, что на первом мудреце не белый колпак (мы должны это опровергнуть). Оба других мудреца видят, что у первого не белый колпак. В то же время, они оба знают, что белый колпак обязательно существует на одном из них. Другими словами, если предложение верно, то можно вычеркнуть первого мудреца из системы, так как его наличие не влияет на результат.

                  Если перед вами 100 мудрецов с небелыми колпаками и один с белым, и вы видите, что мудрец с белым колпаком не догадывается что он с белым, то вывод очевиден — вы с белым колпаком тоже.
                  • +1

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

                    • 0
                      Я вначале тоже не понял) Если перед вами 100 мудрецов с не белыми колпаками, и один с белым (вы, получается, 102-й мудрец, и на вас какой-то колпак), и все мудрецы знают, что есть как минимум один мудрец с белым колпаком, это означает, что возможны две ситуации:
                      1) Белый колпак на мудреце, на которого вы смотрите, и только на нём. Но в этом случае этот мудрец бы увидел, что у всех остальных колпаки не белые, А должен быть хотя бы один мудрец с белым колпаком. Значит, белый колпак у него, о чём он бы и объявил. Но он этого не делает. Следовательно, он не уверен, на нём белый колпак или нет. Значит,
                      2) Белый колпак на нём и на вас (цвета всех остальных известны вам обоим, и они не белые).
                      3) Белый колпак только на том самом мудреце, но он глупый ¯\_(ツ)_/¯

                      Следует отметить, что задача, как мы её видим, имеет решение. Однако, с задачей с точки зрения мудрецов – вытащить случайного цвета колпак и мистическим образом определить свой цвет – не всё так однозначно. Всё бы целиком зависело от того, что им скажут случайные прохожие. И условия для мудрецов вряд ли были бы равными, как тут.
                      • 0

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

                        • 0
                          Так у нас тоже, получается, два варианта: белый и не белый (любой другой). С такими начальными условиями мудрецы могут определить только два этих варианта. При этом если они понимают, что у них не белый, то они не знают, какой у них цвет, и им нужна дополнительная информация. Но если цвет белый, то они сразу могут это определить.
                          • –1

                            Как? Решение имеется только если остальные колпаки черные. т.е. задано условие всего 2-х цветов. Если кол-во цветов не ограничивается, то что-то сказать про свой цвет просто нельзя.
                            Получается задача. Из набора карандашей в 64 цвета и 300карандашей вытянули три карандаша. Один из них белый показали. Какого цвета остальные два карандаши?

                            • +1
                              Я же выше всё расписал. Карандаши, в отличие от мудрецов, не разговаривают. А если бы разговаривали, то белый карандаш увидел бы, что среди остальных карандашей ни одного белого нет, и понял бы, что он белый.
                              Если среди трёх два белых карандаша, то каждый карандаш бы посмотрел на другие карандаши и увидел бы среди них один белый. Но этот белый карандаш бы молчал. Но, как мы выяснили ранее, если бы он был единственным белым карандашом, он это сразу же понял. Значит, белых карандашей два. Значит второй – наш главный карандаш.
                              НЕ белые карандаши свой цвет на основе имеющейся информации определить действительно не смогут. Им бы потребовались дополнительные вопросы.
                              • –1

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

                                • +1
                                  Любой из них может понять, что он белый безо всяких дополнительных ограничений. Цвета могут быть любыми. Вот смотрите.
                                  Условия: трое мудрецов вытягивают три шляпы абсолютно любого цвета. Прохожий говорит, что как минимум один из них вытащил белую шляпу. Мудрецы могут видеть шляпы других, но не свою.
                                  Возможные ситуации:
                                  1) Первый вытащил красную, второй синюю, третий зелёную. Противоречие – прохожий солгал.
                                  2) Первый вытащил крабовую, второй голубую, третий белую. Третий видит, что у остальных не белые, но они молчат. Значит, третий понимает, что у него белая шляпа. Остальные двое не знают свои цвета.
                                  3) Первый вытащил фиолетовую шляпу, второй и третий – белые. Рассуждения второго: если бы белая шляпа была только у третьего, он бы сразу понял, что у него белая шляпа, но он молчит. Значит, белая шляпа и у меня тоже, потому что у первого фиолетовая. Второй и третий понимают, что у них белые шляпы, первый свой цвет не знает.
                                  4) У всех белые шляпы. См. выше. Рассуждения первого: если бы на мне была не белая шляпа, то остальные бы поняли, что у них шляпы белые, следуя логике из шага 3. Но они этого не делают. Значит, у меня тоже белая шляпа. Значит, у всех шляпы белые.

                                  Тут, конечно, в ситуации 4 делается предположение, что мудрецы 2 и 3 уже успели пройти все логические шаги. Т.е. неявно предполагается «синхронизация мудрецов».
                                  Собственно, ниже об этом пишут: habrahabr.ru/post/349558/?reply_to=10684154#comment_10683766

                                  Вариант загадки с неверными жёнами ниже в комментариях лишён этого недостатка путём введения искусственной синхронизации через дни.
                • +3
                  Давным-давно, когда мне первый раз рассказали эту байку, в таком варианте.

                  В некоем городе принято мужьям, узнавшим об неверности жены, до наступления следующего утра ее убивать. (Жестокие нравы ...). Так же в городе есть толкучка, где мужчины обсуждают чужих жен, но своих обсуждать запрещено.
                  В один прекрасный (скорее ужасный) день в город приежает странник. Послушав болтовню на толкучке, он во всеуслышанье объявляет «Не все жены в этом городе верны своим мужьям»
                  Можно доказать по индукции, что через N дней ( где N — количество неверных жен) все неверные жены будут утром найдены мертвыми.
                  Вопрос — что нового сообщел странник?
                  • +2
                    Он запустил цепочку рассуждений.
                    Допустим в городе есть всего одна неверная жена. О ней говорят другие, но её муж ни о чем не догадывается, поэтому он считает что в городе неверных жен нету.
                    Когда странник опровергает его предположение, этот муж понимает что он — единственный кто ошибался и убивает свою жену в первый же день.
                    Допустим, в городе есть две неверных жены. Об этом знает весь город кроме двух мужей. Оба мужа неверных жен не знают о своих женах и думают что в городе всего одна неверная жена. Но убийства в первый день не происходит (каждый думает что его жена верна). Тогда понимают, что на самом деле неверных жен две и убивают их.
                    Ну и так далее, по индукции.
                    • 0
                      Может я не правильно понимаю условие? но если все жены неверны. Мужья знают что все не верны, но думают что их верная. Новая информация ничего не дала они по прежнему думают что их верная.
                      • 0
                        Новая информация запустила счетчик. Они думают что в городе N-1 неверных жен (тогда как весь город кроме них знает что таких жен N) и ожидают убийств в день N-1. Когда этого не происходит, они понимают что их жена тоже неверна. Начните с N=1 и поймете.
                        • 0
                          Объясните, пожалуйста, почему N дней? Вероятно, я неверно понимаю условие. В городе каждый мужчина знает всех чужих неверных жён. Но не знает, верна его жена или нет. Соответственно, если мужчина узнаёт, что в городе N неверных жён, а ему известны лишь N-1, значит последняя – его жена. Она единственная, о ком у него нет информации. При чём все обманутые мужья поймут это сразу же, и всех неверных жён убьют сразу же.
                          Это, кстати, вот ещё почему логично: если бы жён убивали по очереди, то тогда кто-то должен был бы убить свою жену первым. А условия для всех одинаковы. Значит, либо все убьют, либо никто не убьёт.
                          Или я что-то не так понял?

                          P.S. Хотя, с другой стороны, в задаче с колпаками условия тоже одинаковы, по идее. Просто как бы кто-то более сообразительный, кто-то менее. Но ничто не мешает всем мужьям додуматься одновременно. Индукция не нужна.
                          • +1
                            Дело в то что жен не убивают по очереди. Их убивают одновременно в день N (если считать что странник произнес фразу в первый, а не в нулевой день).
                            Мужчина не знает что в городе N неверных жен. Это знание (в некотором роде) принес как раз странник. Жителю города известны либо N либо N-1 неверных жен поименно, но общего количества он не знает.
                            Дальше, мужчина пользуется индукцией. Если ему не изменяли, то он ожидает массовых убийств в день N (именно так и происходит). Если же ему изменяют, то он ожидает массовых убийств в день N-1, чего не случается. И тогда в день N (рано утром, по условию задачи) он понимает что он был среди рогоносцев и устраивает казнь.
                            • 0
                              Я всё равно не понимаю, почему их убьют в день N. Их можно всех убить сразу как только странник сказал, что в городе N неверных жён, ничего этому не препятствует. Ведь уже в первый день на толкучке все мужья уже знают либо N, либо N-1 неверную жену. В первый же день странник говорит, что в городе N неверных жён. Все мужья, знающие N-1 неверную жену, понимают, что их жена им неверна. На второй день N жён найдут мёртвыми. Зачем ждать N дней?
                              • +2
                                Нет, странник не говорит что в городе N неверных жен. Странник просто говорит что они там есть. И это запускает отсчет дней.
                                Представьте, что в городе всего одна неверная жена. Весь город знает о ней, кроме ее мужа. Муж думает что в городе нет неверных жен, ибо ему никто не может об этом сообщить по условиям задачи. Все счастливы. Потом приходит странник и говорит что в городе есть неверные жены. Муж той неверной понимает что он ошибался (а остальной город и так это знал) и идет убивать свою жену.
                                Теперь представим что таких женщин две. Их мужья думают что в городе одна неверная жена и они ожидают что второй убьет свою жену. Но этого не происходит в первый день, потому что каждый из них думает что рогоносец другой. На второй же день они поймут что они оба — рогоносцы и убьют свои жен.
                                Если в городе три неверных жены, то ни на первый, ни на второй день никто не умрет, зато на третий умрут все трое. И так далее.
                                • +3
                                  Кстати, переход к N=3 оказался сложнее, чем я думал.
                                  И так, если рогоносцев трое, то каждый из них не знает о себе и думает что рогонсцев всего двое. Так же он считает что каждый из этих двух рогоносцев не знает про себя, но знает о другом, как я уже описал для случая N=2. Поэтому каждый из трех рогоносцев ожидает что два других убьют своих жен на второй день. Но этого не происходит. И тогда для них открывается страшная правда на третий день.

                                  (Самое забавное, что если в городе всего одна неверная жена, но ее муж об этом не сообразит в первый день (или решит потроллить всех), то на второй день весь город убьет своих женщин).
                                  • 0
                                    del
                                    • 0
                                      А, вот тот самый кусок условия, который я прочитал неверно. Спасибо)
                                  • +1

                                    Вы неправильно понимаете то, что говорит странник. В том то и дело, что странник не говорит, что в городе N неверных жён. Он говорит только, что не все жёны верны. Это сообщение просто запускает счётчик дней до дня «икс». Все обманутые мужья думают, что в городе N-1 неверная жена и, соответственно (по цепочке рассуждений из комментария lorc) ожидают, что днём «икс» станет N-1-й день после сообщения. Но убийств в этот день не происходит. Тогда каждый из них понимает, что изменяющих жён на одну больше и эта «дополнительная» жена может быть только его собственной (потому что про всех остальных жён они и так уже всё знают), поэтому день «икс» перемещается на день N.


                                    PS. Пока писал комментарий, немного опоздал, lorc уже ответил.

                                    • 0
                                      Всё равно спасибо) Да, действительно, я неверно прочитал условие.
                                  • В жизни бывает, что рогоносец — олень.
                                    Если в ночь на день N он не сделает умозаключение, то остальные не смогут правильно сделать свои умозаключения.
                                    Вот, скажем, N=1. Некий муж считает, что N=1, но в первый день не случается убийства. Он рогоносец или единственный рогоносец — олень, который не догнал, что его жена неверная?

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

                                    upd. lorc уже написал про возможный троллинга для N=1.
                              • 0

                                Делл. Там Н дней. При любом количистве в/н для каждого человека может быть только 2 схемы где его жена неверная или верная. Собственно на н день он узнает в каком он положении.

                            • 0
                              По идее ваш `fullState` можно заменить на `replicateM 3 [Black, White]`
                              По задаче, много математических и логических подходов (схожих как статье) освещается тут
                              www.youtube.com/watch?v=chGbsxG0VvU&list=PLQyMGME-L41OMrBSleF9HHzMb3urNXX96&index=1
                              • –1
                                Осталось только строго обосновать фразу " я переформулирую задачу более корректно." И все будет в порядке. Ну и 4-й параграф про двух мудрецов тоже прекрасен.
                                • –1
                                  Вообще-то в этой задаче должен быть султан, который ведет счет. Иначе задача не решается.
                                  • –1
                                    По-моему, исходная задача некорректно сформулирована, и не имеет решения. Если я прав, дайте кто-нибудь решаемую формулировку, интересно…
                                    • +1
                                      Вывод мудреца, воскликнувшего «на мне белый колпак!!!», основывается на неявном предположении, что оставшиеся (N-1) мудрецов достаточно «мудры», чтобы успеть решить к тому моменту задачу (N-1)-го порядка (но не «мудрее», чем он).

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

                                      Самое читаемое