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