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

[livelight]

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

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

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

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

Comments

[sda.livejournal.com]

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

[livelight]

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

[sda.livejournal.com]

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

[canisterribilis.livejournal.com]

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

[livelight]

Что вообще когда-то

[livelight]

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

[sda.livejournal.com]

Тогда для каждой женщины никакой новой информации нет, так как каждая уже знает про 49 измен минимум. Ничего не произойдёт.

[chip33.livejournal.com]

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

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

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

[justy-tylor.livejournal.com]

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

[livelight]

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

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

[livelight]

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

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

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

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

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

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

[livelight]

Не совсем, иначе было бы неинтересно :)

[sda.livejournal.com]

Согласен, так слишком неинтересно получается. Но в чём моё упущение? Разве у женщин появляется какая-то новая информация, которая побуждает их к новым действиям?

[canisterribilis.livejournal.com]

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

[justy-tylor.livejournal.com]

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

[livelight]

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

[livelight]

Не на следующий :)

[livelight]

http://livelight.livejournal.com/492091.html?thread=5054523#t5054523

[karachee.livejournal.com]

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

[livelight]

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

[canisterribilis.livejournal.com]

Тады не пОняла...

[livejournal.livejournal.com]

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

[chip33.livejournal.com]

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

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

[livelight]

Я ж говорю: там всё очень красиво. Особенно мне понравилось формулировка "в тот же день" :)

[cyaness.livejournal.com]

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

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