Комментарии 38
Отличная статья, спасибо! Самое то для новичков.
Я слышал вариант в котором 3 белых и 2 чёрных колпака и нет искусственно добавленного человека, который сообщает цвет одного из них. Мудрецы долго сидели и думали, пока один из них не заявил, что знает ответ, тогда и остальные узнали свой цвет.
Никогда не понимал таких задач. А если колпаки будут белый синий и розовый, а в ящике откуда они их брали еще три десятка возможных цветов?
Не вижу в упор логику решения. А вот решение подразумевает дополнительные ограничения задачи. Откуда эти ограничения взялись если в условии колпаки любого цвета и копаков соответственно много?
Если бы на нем был колпак другого цвета, то прохожий сказал бы что на одном из них колпак %цвет_нейм, ибо %цвет_нейм бросался бы в глаза. А так если на остальных белый значит и на мудреце колпак тоже белый
второй мудрец будет думать так. … (далее идут рассуждения из задачи про двух мудрецов)они не могут рассуждать также, как в задаче про двух мудрецов, потому что перед каждым из них два мудреца с двумя колпаками, а не один.
понял свою ошибку, забудьте
У нас есть предположение, что на первом мудреце не белый колпак (мы должны это опровергнуть). Оба других мудреца видят, что у первого не белый колпак. В то же время, они оба знают, что белый колпак обязательно существует на одном из них. Другими словами, если предложение верно, то можно вычеркнуть первого мудреца из системы, так как его наличие не влияет на результат.
Если перед вами 100 мудрецов с небелыми колпаками и один с белым, и вы видите, что мудрец с белым колпаком не догадывается что он с белым, то вывод очевиден — вы с белым колпаком тоже.
Если перед вами 100 мудрецов с небелыми колпаками и один с белым, и вы видите, что мудрец с белым колпаком не догадывается что он с белым, то вывод очевиден — вы с белым колпаком тоже.
Если перед вами 100 мудрецов с не белыми колпаками и один белый, то откуда уверенность, что у вас не синий, красный зеленый???
Мы подошли к тому, что у нас всего два цвета возможно, а в условии любые цвета. Значить мы не можем допустить вольности того, что белый колпак обязательно надет на мудреца который видит у кого-то белый колпак и молчит. Может тот мудрец вообще белых колпаков нигде не видит, а у него вообще салатовый, а у всех свои цвета одеты.
Я вначале тоже не понял) Если перед вами 100 мудрецов с не белыми колпаками, и один с белым (вы, получается, 102-й мудрец, и на вас какой-то колпак), и все мудрецы знают, что есть как минимум один мудрец с белым колпаком, это означает, что возможны две ситуации:
1) Белый колпак на мудреце, на которого вы смотрите, и только на нём. Но в этом случае этот мудрец бы увидел, что у всех остальных колпаки не белые, А должен быть хотя бы один мудрец с белым колпаком. Значит, белый колпак у него, о чём он бы и объявил. Но он этого не делает. Следовательно, он не уверен, на нём белый колпак или нет. Значит,
2) Белый колпак на нём и на вас (цвета всех остальных известны вам обоим, и они не белые).
3) Белый колпак только на том самом мудреце, но он глупый ¯\_(ツ)_/¯
Следует отметить, что задача, как мы её видим, имеет решение. Однако, с задачей с точки зрения мудрецов – вытащить случайного цвета колпак и мистическим образом определить свой цвет – не всё так однозначно. Всё бы целиком зависело от того, что им скажут случайные прохожие. И условия для мудрецов вряд ли были бы равными, как тут.
1) Белый колпак на мудреце, на которого вы смотрите, и только на нём. Но в этом случае этот мудрец бы увидел, что у всех остальных колпаки не белые, А должен быть хотя бы один мудрец с белым колпаком. Значит, белый колпак у него, о чём он бы и объявил. Но он этого не делает. Следовательно, он не уверен, на нём белый колпак или нет. Значит,
2) Белый колпак на нём и на вас (цвета всех остальных известны вам обоим, и они не белые).
Следует отметить, что задача, как мы её видим, имеет решение. Однако, с задачей с точки зрения мудрецов – вытащить случайного цвета колпак и мистическим образом определить свой цвет – не всё так однозначно. Всё бы целиком зависело от того, что им скажут случайные прохожие. И условия для мудрецов вряд ли были бы равными, как тут.
В условии нет ограничений по цветам. В условии задачи обязательные цвета не указаны.
В оригинальной задаче есть ограничивающие условия (всего два цвета). В задаче из материала ограничивающих условий никаких нет, есть только дополнение, что один колпак белый. Решения она как по мне просто не имеет.
этому просто не имеет.
Так у нас тоже, получается, два варианта: белый и не белый (любой другой). С такими начальными условиями мудрецы могут определить только два этих варианта. При этом если они понимают, что у них не белый, то они не знают, какой у них цвет, и им нужна дополнительная информация. Но если цвет белый, то они сразу могут это определить.
Как? Решение имеется только если остальные колпаки черные. т.е. задано условие всего 2-х цветов. Если кол-во цветов не ограничивается, то что-то сказать про свой цвет просто нельзя.
Получается задача. Из набора карандашей в 64 цвета и 300карандашей вытянули три карандаша. Один из них белый показали. Какого цвета остальные два карандаши?
Я же выше всё расписал. Карандаши, в отличие от мудрецов, не разговаривают. А если бы разговаривали, то белый карандаш увидел бы, что среди остальных карандашей ни одного белого нет, и понял бы, что он белый.
Если среди трёх два белых карандаша, то каждый карандаш бы посмотрел на другие карандаши и увидел бы среди них один белый. Но этот белый карандаш бы молчал. Но, как мы выяснили ранее, если бы он был единственным белым карандашом, он это сразу же понял. Значит, белых карандашей два. Значит второй – наш главный карандаш.
НЕ белые карандаши свой цвет на основе имеющейся информации определить действительно не смогут. Им бы потребовались дополнительные вопросы.
Если среди трёх два белых карандаша, то каждый карандаш бы посмотрел на другие карандаши и увидел бы среди них один белый. Но этот белый карандаш бы молчал. Но, как мы выяснили ранее, если бы он был единственным белым карандашом, он это сразу же понял. Значит, белых карандашей два. Значит второй – наш главный карандаш.
НЕ белые карандаши свой цвет на основе имеющейся информации определить действительно не смогут. Им бы потребовались дополнительные вопросы.
По условию белые все были, а не все черные и прохожий сказал, что один белый. Поэтому белый не знает что он белый и при этом может видеть белый на другом. Но вариантов еще остается слишком много. Просто в условии пропущено ограничение по кол-ву цветов. Без этого задача не решаема как по мне. Ох уж эта логика.
Любой из них может понять, что он белый безо всяких дополнительных ограничений. Цвета могут быть любыми. Вот смотрите.
Условия: трое мудрецов вытягивают три шляпы абсолютно любого цвета. Прохожий говорит, что как минимум один из них вытащил белую шляпу. Мудрецы могут видеть шляпы других, но не свою.
Возможные ситуации:
1) Первый вытащил красную, второй синюю, третий зелёную. Противоречие – прохожий солгал.
2) Первый вытащил крабовую, второй голубую, третий белую. Третий видит, что у остальных не белые, но они молчат. Значит, третий понимает, что у него белая шляпа. Остальные двое не знают свои цвета.
3) Первый вытащил фиолетовую шляпу, второй и третий – белые. Рассуждения второго: если бы белая шляпа была только у третьего, он бы сразу понял, что у него белая шляпа, но он молчит. Значит, белая шляпа и у меня тоже, потому что у первого фиолетовая. Второй и третий понимают, что у них белые шляпы, первый свой цвет не знает.
4) У всех белые шляпы. См. выше. Рассуждения первого: если бы на мне была не белая шляпа, то остальные бы поняли, что у них шляпы белые, следуя логике из шага 3. Но они этого не делают. Значит, у меня тоже белая шляпа. Значит, у всех шляпы белые.
Тут, конечно, в ситуации 4 делается предположение, что мудрецы 2 и 3 уже успели пройти все логические шаги. Т.е. неявно предполагается «синхронизация мудрецов».
Собственно, ниже об этом пишут: habrahabr.ru/post/349558/?reply_to=10684154#comment_10683766
Вариант загадки с неверными жёнами ниже в комментариях лишён этого недостатка путём введения искусственной синхронизации через дни.
Условия: трое мудрецов вытягивают три шляпы абсолютно любого цвета. Прохожий говорит, что как минимум один из них вытащил белую шляпу. Мудрецы могут видеть шляпы других, но не свою.
Возможные ситуации:
1) Первый вытащил красную, второй синюю, третий зелёную. Противоречие – прохожий солгал.
2) Первый вытащил крабовую, второй голубую, третий белую. Третий видит, что у остальных не белые, но они молчат. Значит, третий понимает, что у него белая шляпа. Остальные двое не знают свои цвета.
3) Первый вытащил фиолетовую шляпу, второй и третий – белые. Рассуждения второго: если бы белая шляпа была только у третьего, он бы сразу понял, что у него белая шляпа, но он молчит. Значит, белая шляпа и у меня тоже, потому что у первого фиолетовая. Второй и третий понимают, что у них белые шляпы, первый свой цвет не знает.
4) У всех белые шляпы. См. выше. Рассуждения первого: если бы на мне была не белая шляпа, то остальные бы поняли, что у них шляпы белые, следуя логике из шага 3. Но они этого не делают. Значит, у меня тоже белая шляпа. Значит, у всех шляпы белые.
Тут, конечно, в ситуации 4 делается предположение, что мудрецы 2 и 3 уже успели пройти все логические шаги. Т.е. неявно предполагается «синхронизация мудрецов».
Собственно, ниже об этом пишут: habrahabr.ru/post/349558/?reply_to=10684154#comment_10683766
Вариант загадки с неверными жёнами ниже в комментариях лишён этого недостатка путём введения искусственной синхронизации через дни.
Давным-давно, когда мне первый раз рассказали эту байку, в таком варианте.
В некоем городе принято мужьям, узнавшим об неверности жены, до наступления следующего утра ее убивать. (Жестокие нравы ...). Так же в городе есть толкучка, где мужчины обсуждают чужих жен, но своих обсуждать запрещено.
В один прекрасный (скорее ужасный) день в город приежает странник. Послушав болтовню на толкучке, он во всеуслышанье объявляет «Не все жены в этом городе верны своим мужьям»
Можно доказать по индукции, что через N дней ( где N — количество неверных жен) все неверные жены будут утром найдены мертвыми.
Вопрос — что нового сообщел странник?
В некоем городе принято мужьям, узнавшим об неверности жены, до наступления следующего утра ее убивать. (Жестокие нравы ...). Так же в городе есть толкучка, где мужчины обсуждают чужих жен, но своих обсуждать запрещено.
В один прекрасный (скорее ужасный) день в город приежает странник. Послушав болтовню на толкучке, он во всеуслышанье объявляет «Не все жены в этом городе верны своим мужьям»
Можно доказать по индукции, что через N дней ( где N — количество неверных жен) все неверные жены будут утром найдены мертвыми.
Вопрос — что нового сообщел странник?
Он запустил цепочку рассуждений.
Допустим в городе есть всего одна неверная жена. О ней говорят другие, но её муж ни о чем не догадывается, поэтому он считает что в городе неверных жен нету.
Когда странник опровергает его предположение, этот муж понимает что он — единственный кто ошибался и убивает свою жену в первый же день.
Допустим, в городе есть две неверных жены. Об этом знает весь город кроме двух мужей. Оба мужа неверных жен не знают о своих женах и думают что в городе всего одна неверная жена. Но убийства в первый день не происходит (каждый думает что его жена верна). Тогда понимают, что на самом деле неверных жен две и убивают их.
Ну и так далее, по индукции.
Допустим в городе есть всего одна неверная жена. О ней говорят другие, но её муж ни о чем не догадывается, поэтому он считает что в городе неверных жен нету.
Когда странник опровергает его предположение, этот муж понимает что он — единственный кто ошибался и убивает свою жену в первый же день.
Допустим, в городе есть две неверных жены. Об этом знает весь город кроме двух мужей. Оба мужа неверных жен не знают о своих женах и думают что в городе всего одна неверная жена. Но убийства в первый день не происходит (каждый думает что его жена верна). Тогда понимают, что на самом деле неверных жен две и убивают их.
Ну и так далее, по индукции.
Может я не правильно понимаю условие? но если все жены неверны. Мужья знают что все не верны, но думают что их верная. Новая информация ничего не дала они по прежнему думают что их верная.
Новая информация запустила счетчик. Они думают что в городе N-1 неверных жен (тогда как весь город кроме них знает что таких жен N) и ожидают убийств в день N-1. Когда этого не происходит, они понимают что их жена тоже неверна. Начните с N=1 и поймете.
Объясните, пожалуйста, почему N дней? Вероятно, я неверно понимаю условие. В городе каждый мужчина знает всех чужих неверных жён. Но не знает, верна его жена или нет. Соответственно, если мужчина узнаёт, что в городе N неверных жён, а ему известны лишь N-1, значит последняя – его жена. Она единственная, о ком у него нет информации. При чём все обманутые мужья поймут это сразу же, и всех неверных жён убьют сразу же.
Это, кстати, вот ещё почему логично: если бы жён убивали по очереди, то тогда кто-то должен был бы убить свою жену первым. А условия для всех одинаковы. Значит, либо все убьют, либо никто не убьёт.
Или я что-то не так понял?
P.S. Хотя, с другой стороны, в задаче с колпаками условия тоже одинаковы, по идее. Просто как бы кто-то более сообразительный, кто-то менее. Но ничто не мешает всем мужьям додуматься одновременно. Индукция не нужна.
Это, кстати, вот ещё почему логично: если бы жён убивали по очереди, то тогда кто-то должен был бы убить свою жену первым. А условия для всех одинаковы. Значит, либо все убьют, либо никто не убьёт.
Или я что-то не так понял?
P.S. Хотя, с другой стороны, в задаче с колпаками условия тоже одинаковы, по идее. Просто как бы кто-то более сообразительный, кто-то менее. Но ничто не мешает всем мужьям додуматься одновременно. Индукция не нужна.
Дело в то что жен не убивают по очереди. Их убивают одновременно в день N (если считать что странник произнес фразу в первый, а не в нулевой день).
Мужчина не знает что в городе N неверных жен. Это знание (в некотором роде) принес как раз странник. Жителю города известны либо N либо N-1 неверных жен поименно, но общего количества он не знает.
Дальше, мужчина пользуется индукцией. Если ему не изменяли, то он ожидает массовых убийств в день N (именно так и происходит). Если же ему изменяют, то он ожидает массовых убийств в день N-1, чего не случается. И тогда в день N (рано утром, по условию задачи) он понимает что он был среди рогоносцев и устраивает казнь.
Мужчина не знает что в городе N неверных жен. Это знание (в некотором роде) принес как раз странник. Жителю города известны либо N либо N-1 неверных жен поименно, но общего количества он не знает.
Дальше, мужчина пользуется индукцией. Если ему не изменяли, то он ожидает массовых убийств в день N (именно так и происходит). Если же ему изменяют, то он ожидает массовых убийств в день N-1, чего не случается. И тогда в день N (рано утром, по условию задачи) он понимает что он был среди рогоносцев и устраивает казнь.
Я всё равно не понимаю, почему их убьют в день N. Их можно всех убить сразу как только странник сказал, что в городе N неверных жён, ничего этому не препятствует. Ведь уже в первый день на толкучке все мужья уже знают либо N, либо N-1 неверную жену. В первый же день странник говорит, что в городе N неверных жён. Все мужья, знающие N-1 неверную жену, понимают, что их жена им неверна. На второй день N жён найдут мёртвыми. Зачем ждать N дней?
Нет, странник не говорит что в городе N неверных жен. Странник просто говорит что они там есть. И это запускает отсчет дней.
Представьте, что в городе всего одна неверная жена. Весь город знает о ней, кроме ее мужа. Муж думает что в городе нет неверных жен, ибо ему никто не может об этом сообщить по условиям задачи. Все счастливы. Потом приходит странник и говорит что в городе есть неверные жены. Муж той неверной понимает что он ошибался (а остальной город и так это знал) и идет убивать свою жену.
Теперь представим что таких женщин две. Их мужья думают что в городе одна неверная жена и они ожидают что второй убьет свою жену. Но этого не происходит в первый день, потому что каждый из них думает что рогоносец другой. На второй же день они поймут что они оба — рогоносцы и убьют свои жен.
Если в городе три неверных жены, то ни на первый, ни на второй день никто не умрет, зато на третий умрут все трое. И так далее.
Представьте, что в городе всего одна неверная жена. Весь город знает о ней, кроме ее мужа. Муж думает что в городе нет неверных жен, ибо ему никто не может об этом сообщить по условиям задачи. Все счастливы. Потом приходит странник и говорит что в городе есть неверные жены. Муж той неверной понимает что он ошибался (а остальной город и так это знал) и идет убивать свою жену.
Теперь представим что таких женщин две. Их мужья думают что в городе одна неверная жена и они ожидают что второй убьет свою жену. Но этого не происходит в первый день, потому что каждый из них думает что рогоносец другой. На второй же день они поймут что они оба — рогоносцы и убьют свои жен.
Если в городе три неверных жены, то ни на первый, ни на второй день никто не умрет, зато на третий умрут все трое. И так далее.
Кстати, переход к N=3 оказался сложнее, чем я думал.
И так, если рогоносцев трое, то каждый из них не знает о себе и думает что рогонсцев всего двое. Так же он считает что каждый из этих двух рогоносцев не знает про себя, но знает о другом, как я уже описал для случая N=2. Поэтому каждый из трех рогоносцев ожидает что два других убьют своих жен на второй день. Но этого не происходит. И тогда для них открывается страшная правда на третий день.
(Самое забавное, что если в городе всего одна неверная жена, но ее муж об этом не сообразит в первый день (или решит потроллить всех), то на второй день весь город убьет своих женщин).
И так, если рогоносцев трое, то каждый из них не знает о себе и думает что рогонсцев всего двое. Так же он считает что каждый из этих двух рогоносцев не знает про себя, но знает о другом, как я уже описал для случая N=2. Поэтому каждый из трех рогоносцев ожидает что два других убьют своих жен на второй день. Но этого не происходит. И тогда для них открывается страшная правда на третий день.
(Самое забавное, что если в городе всего одна неверная жена, но ее муж об этом не сообразит в первый день (или решит потроллить всех), то на второй день весь город убьет своих женщин).
Вы неправильно понимаете то, что говорит странник. В том то и дело, что странник не говорит, что в городе N неверных жён. Он говорит только, что не все жёны верны. Это сообщение просто запускает счётчик дней до дня «икс». Все обманутые мужья думают, что в городе N-1 неверная жена и, соответственно (по цепочке рассуждений из комментария lorc) ожидают, что днём «икс» станет N-1-й день после сообщения. Но убийств в этот день не происходит. Тогда каждый из них понимает, что изменяющих жён на одну больше и эта «дополнительная» жена может быть только его собственной (потому что про всех остальных жён они и так уже всё знают), поэтому день «икс» перемещается на день N.
PS. Пока писал комментарий, немного опоздал, lorc уже ответил.
В жизни бывает, что рогоносец — олень.
Если в ночь на день N он не сделает умозаключение, то остальные не смогут правильно сделать свои умозаключения.
Вот, скажем, N=1. Некий муж считает, что N=1, но в первый день не случается убийства. Он рогоносец или единственный рогоносец — олень, который не догнал, что его жена неверная?
Это, конечно, не относится к исходной логической задачи, но тема устойчивости распределённых систем тоже весьма интересна.
upd. lorc уже написал про возможный троллинга для N=1.
Если в ночь на день N он не сделает умозаключение, то остальные не смогут правильно сделать свои умозаключения.
Вот, скажем, N=1. Некий муж считает, что N=1, но в первый день не случается убийства. Он рогоносец или единственный рогоносец — олень, который не догнал, что его жена неверная?
Это, конечно, не относится к исходной логической задачи, но тема устойчивости распределённых систем тоже весьма интересна.
upd. lorc уже написал про возможный троллинга для N=1.
Делл. Там Н дней. При любом количистве в/н для каждого человека может быть только 2 схемы где его жена неверная или верная. Собственно на н день он узнает в каком он положении.
По идее ваш `fullState` можно заменить на `replicateM 3 [Black, White]`
По задаче, много математических и логических подходов (схожих как статье) освещается тут
www.youtube.com/watch?v=chGbsxG0VvU&list=PLQyMGME-L41OMrBSleF9HHzMb3urNXX96&index=1
По задаче, много математических и логических подходов (схожих как статье) освещается тут
www.youtube.com/watch?v=chGbsxG0VvU&list=PLQyMGME-L41OMrBSleF9HHzMb3urNXX96&index=1
Осталось только строго обосновать фразу " я переформулирую задачу более корректно." И все будет в порядке. Ну и 4-й параграф про двух мудрецов тоже прекрасен.
Вообще-то в этой задаче должен быть султан, который ведет счет. Иначе задача не решается.
По-моему, исходная задача некорректно сформулирована, и не имеет решения. Если я прав, дайте кто-нибудь решаемую формулировку, интересно…
Вывод мудреца, воскликнувшего «на мне белый колпак!!!», основывается на неявном предположении, что оставшиеся (N-1) мудрецов достаточно «мудры», чтобы успеть решить к тому моменту задачу (N-1)-го порядка (но не «мудрее», чем он).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Haskell. Задача о мудрецах и колпаках