Рекурсивная теория интеллекта :)

[livelight]

Шикарная какая задача. Наткнулся на неё в книжке про собеседования в Microsoft. Точнее, сначала наткнулся на подборку задач из неё, да ещё и с искажениями в формулировках, так что временами приходилось сначала придумывать задачу, которая имела бы смысл и была притом интересной, и только потом решать. Потом нашёл саму книжку, уже без искажений, зато с байками. Одну из этих задач мне давали при приёме на нынешнее место работы. Ещё одну - при приёме на предыдущее :)

Задачи на оценку ("Сколько всего настройщиков пианино в мире?" и тому подобные) пропустил, остальные почти все за пол-вечера пощёлкал, но эту - нет, прочитал решение в книжке, и оно восхитительно красиво!

Суть примерно та же, как в задаче про трёх мудрецов и три колпака (эту я ещё в деццтве решил), но здесь - вообще шедевр рекурсивной Теории Интеллекта!

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

Comments

[sda.livejournal.com]

Каждая женщина, поняв, что изменил именно её собственный муж (так как, если был не её, она бы это знала) убивает своего мужа. Все мужи мертвы.
Так?

[livelight]

Каждая и так знает про 49 случаев, а королева сообщает, что изменил минимум 1 :)

[sda.livejournal.com]

Я тогда не понял. Она сообщает, что именно сегодня изменил или вообще когда-то имелась одна измена?

[canisterribilis.livejournal.com]

Рискну предположить, что ничего. Не?

[livelight]

Таки произойдёт. Но не сразу :)

[canisterribilis.livejournal.com]

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

[chip33.livejournal.com]

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

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

Но для соблюдения статус кво, надо, конечно, грохать королеву. Для профилактики.

[livelight]

> обязательно надо выяснить, кто это

Каждая обязана много думать и выяснять логически про своего. Про чужих она и так всё знает :)
Из допущений там только - что ни одна женщина не выясняет напрямую, что творится в голове у другой женщины, только чистый бихевиоризм :)

> то без дополнительных условий ничего не меняется

А вот поди ж ты :)

> надо, конечно, грохать королеву. Для профилактики

Годное предложение! Для блага всех остальных - надо. Но сами они уже опоздали, им она успела сказать пакость :))

[chip33.livejournal.com]

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

Ни фига себе допущение! ;) Вот честно, ни за что бы не предположил, что это входное условие в данном контексте. Тогда как время появится, еще раз подумаю.

[cyaness.livejournal.com]

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

Так женщины общаются между собой на предмет измен, или нет?

[justy-tylor.livejournal.com]

Проблемы либо с переводом, либо с исходным текстом. В одном месте "узнает" (одна бабка сказала), в другом "доказательство", а в третьем "объявляет". Для логической формализации модальности должны быть прописаны более чётко.

[livelight]

По-моему, всё чётко. "Узнаёт" - надёжно и гарантированно. Королева - неполживый и безошибочный источник информации. А доказательства могут быть и очень косвенными, но в такого рода задачах предполагается (а иногда и явно указывается), что все женщины шибко умные, и все это знают.

Лично мне больше всего понравилось формулировка "в тот же день" - она надёжно закрывает небольшую дырку в допущениях задачи про мудрецов и колпаки.

[justy-tylor.livejournal.com]

Условная истина "кто-то изменяет" никак не влияет на позицию "49 изменяют, а у меня верный". Для последствий должны быть другие модальности. Они могут быть в оригинале задачи или неявно приниматься читателями из "предлагаемого авторами правильного ответа", но в приведённой постановке их нет.

[karachee.livejournal.com]

Технически ничего не должно произойти, т. к. ни одна женщина не получает доказательств, что её муж ей изменил. И получить их не может. Скорее всего задача строиться вокруг того, что сплетня не является доказательством, таким образом знание о 49 изменах не является достоверным на момент появления королевы. Ведь женщины не безгрешны. С другой стороны по меньшей мере одна женщина доподлинно знает об измене одного мужчины, если принять, что мужчины изменяли с женщинами той же деревни, а не бегали в соседнюю. Многовато допущений, условие недостаточно строгое. Допустим каждая женщина спрашивает у других 49 изменял ли ей её муж с этой женщиной, вопрос как быстро она успеет провести это опрос за час, за два дня, за неделю. В последнем случае до 40 мужиков успеют убежать. )))

[livelight]

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

[karachee.livejournal.com]

Тут нет четкого выхода на решение. Каждая знает, что по закону должны умереть 49, но сама убить она может и должна убить только 1, который не идентифицируется как изменник. Чтобы снять возмущение от информации королевы, достаточно, чтобы умер один. Но один не умирает, ни сегодня, ни завтра. Все, дальше ничего сделать нельзя, поскольку возможности коммуникации или какой-то другой способ получения дополнительной информации в задаче не прописан. Анализ ситуации не позволяет ей вычислить о скольких изменах знают другие женщины, в отличии от мудрецов, где объем информации, которым владеют другие мудрецы в колпаках известен.

[livejournal.livejournal.com]

Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal центрального региона (http://www.livejournal.com/?rating=ru_central). Подробнее о рейтинге читайте в Справке (https://www.dreamwidth.org/support/faqbrowse?faqid=303).

[iris-the-fox.livejournal.com]

Нашла вариант ответа, верный по всей видимости, но смысла в нем не вижу...

[livelight]

И какой вариант? :)

[iris-the-fox.livejournal.com]

что убьют всех на 50 день

[chmyrnovich.livejournal.com]

Чего тут думать - неверные мужики тут же съебут из города.

Верные тоже - от греха подальше.

[livelight]

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

А верных там нет :)

[chmyrnovich.livejournal.com]

Задачка-то тривиальная - в первый день могут убить одного, во второй - двоих, и т.д.

[kotbezkrbishbi.livejournal.com]

Ссылкой на книжку поделитесь?

[livelight]

Уильям Паундстоун. Как сдвинуть гору Фудзи
http://www.logic-books.info/sites/default/files/paundstoun_u._kak_sdvinut_goru_fudzi.pdf -- там я тоже видел в задачах пару опечаток, но в целом вполне приличная версия книги.