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

[livelight]

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

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

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

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

Comments

[livelight]

Я фкурил. Мне понравилось :)

"Допустим, мой муж не изменял. Тогда соседка знает про 48 изменяющих и тоже думает: допустим, мой муж не изменил, тогда моя соседка думает: .....
А потом обратно: так, за этот день 49-ая соседка никого не убила, и все ТУТПОДУМАЛИ..."

[iris-the-fox.livejournal.com]

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

[livelight]

Фишка в том, что первая ПРЕДПОЛАГАЕТ про своего, что тот верный, и строит из этого предположения, что вторая В ЭТОМ СЛУЧАЕ предположит, что её муж тоже верный, и тогда исходя из этого предположит, что тогда третья предположит... Продолжив эту цепочку оптимистичных жён, дойдём до мира, который существует в воображении 49-ой жены, воображаемой 48-ой женой, воображаемой 47-ой женой ..... и всё это существует в воображении 1-ой жены, а рядом Лао Цзы видит сон, что он бабочка, которая видит сон, что она Лао Цзы, который видит сон...

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

[iris-the-fox.livejournal.com]

почему каждый день-то?
что, в один день может изменить только один муж? или узнать только одна жена? или убить только одна жена?

[livelight]

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

[iris-the-fox.livejournal.com]

так в задаче сказано, что каждый ИЗМЕНЯЛ когда-то в прошлом. а не то, что будет изменять и в будущем и именно ежедневно

[livelight]

Им не надо изменять в будущем. Они нагрешили в прошлом, а жена обязана убить мужа в тот день, когда узнала про его прошлые грехи.

[iris-the-fox.livejournal.com]

чот всё равно не улавливаю логики

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

[livelight]

"Она" - это 50-ая жена, воображаемая 49-ой оптимистичной женой, которую воображает 48-ая оптимистичная и т.д. рекурсивно до 1-ой оптимистичной. Нумерация произвольная, а 1-ой является та, которая реально всё это думает, рассчитывая ход мыслей своих соседок (а думает каждая и одинаково)

"Третья оптимистичная война" :))

[iris-the-fox.livejournal.com]

а почему не предположить, что первая знает про 49 измен, а каждая вторая - про 48 - кроме своего и мужа первой?

[livelight]

Это только первый уровень Теории Интеллекта, без рекурсии. Но воображаемая первой вторая знает про 48 измен, оптимистична и начинает конструировать ход мыслей воображаемой третьей, которая тогда знает только про 47 измен...

[iris-the-fox.livejournal.com]

я кажется начинаю понимать, но, пока не укладывается нифига

[canisterribilis.livejournal.com]

Блин, други, а можно я немножко дегтя капну, чисто из вредности, поскольку мой мозг эту логику уварить по-прежнему не может?
Так вот, не 50, а 25:))

[iris-the-fox.livejournal.com]

погоди, я еще про 50 не всё поняла, а мне бы ещё поработать не мешало)))

[livelight]

Что 25? Дней?
Не, гипотетическая оптимистичная жена 50-го уровня имела право убивать своего мужа весь первый день, до самой полуночи, её все ждали. А весь второй день до полуночи ждали гипотетическую оптимистичную жену 49-го левела :)

[canisterribilis.livejournal.com]

25 дней, 25 мужей. 50 супружеских пар же ж:))

[livelight]

Сколько-сколько мужей в 50 супружеских парах? :)

[canisterribilis.livejournal.com]

Все, блин, ппц:)))
Пойду самоликвидируюсь нафиг, приму смертельную дозу дегтя.
Бли-и-и-ин, "не надо столько думать, Харли" :)...

[sda.livejournal.com]

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

[livelight]

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