Задача о мудрецах и неверных жёнах
Эадача довольно широко известна (я бы даже сказал, знаменита) -- поэтому под кат.
В одном городе жили мудрецы. Каждое утро они собирались на базаре и обменивались новостями. А поскольку они любили сплетничать, каждый из них знал, у кого из мудрецов жена верная, а у кого -- нет. Но про собственных жён мудрецы этого не знали, ибо у них была благоразумная традиция: не обсуждать ни с кем его жену.
И вот однажды на базар явился кто-то посторонний, и заявил во всеуслышание: "А не у всех мудрецов жёны верные!"
Мудрецы задумались. Каждый день они ходили на базар и обменивались новостями. И вот, на N-тый день, N мудрецов выгнали своих неверных жён.
Как они догадались?
(Ответ повешу завтра)
UPD2: Пояснение к условию. Тут maksa заметил, что у верной жены всегда есть возможность стать неверной :-) Так вот, жёны мудрецов так не поступают. (Мир мудрецов, вообще, довольно статичен)
А вспомнилась мне эта задача, потому что в последнее время я часто вижу в ЖЖ заявления типа: "Подумаешь, кто-то прочтёт ваши подзамки. Кому надо, их и так давно читают". Эта задача -- пример того, что разглашение даже общеизвестной информации может иметь серьёзные последствия.
UPD: Ответ (выделите мышкой): Базис индукции: если N=1, единственный рогоносец, не видя ни одной неверной жены, поймёт, что неверная жена -- у него, и выгонит её в первый же день. Шаг индукции: пусть N неверных жён выгонят на N-тый день. Тогда, если неверных жён N+1, то в день N+1 каждый рогоносец узнает, что вчера никого не выгнали, и поймёт, что кроме N известных ему неверых жён есть ещё одна -- его собственная. Подробнее в комментах.
В одном городе жили мудрецы. Каждое утро они собирались на базаре и обменивались новостями. А поскольку они любили сплетничать, каждый из них знал, у кого из мудрецов жена верная, а у кого -- нет. Но про собственных жён мудрецы этого не знали, ибо у них была благоразумная традиция: не обсуждать ни с кем его жену.
И вот однажды на базар явился кто-то посторонний, и заявил во всеуслышание: "А не у всех мудрецов жёны верные!"
Мудрецы задумались. Каждый день они ходили на базар и обменивались новостями. И вот, на N-тый день, N мудрецов выгнали своих неверных жён.
Как они догадались?
(Ответ повешу завтра)
UPD2: Пояснение к условию. Тут maksa заметил, что у верной жены всегда есть возможность стать неверной :-) Так вот, жёны мудрецов так не поступают. (Мир мудрецов, вообще, довольно статичен)
А вспомнилась мне эта задача, потому что в последнее время я часто вижу в ЖЖ заявления типа: "Подумаешь, кто-то прочтёт ваши подзамки. Кому надо, их и так давно читают". Эта задача -- пример того, что разглашение даже общеизвестной информации может иметь серьёзные последствия.
UPD: Ответ (выделите мышкой): Базис индукции: если N=1, единственный рогоносец, не видя ни одной неверной жены, поймёт, что неверная жена -- у него, и выгонит её в первый же день. Шаг индукции: пусть N неверных жён выгонят на N-тый день. Тогда, если неверных жён N+1, то в день N+1 каждый рогоносец узнает, что вчера никого не выгнали, и поймёт, что кроме N известных ему неверых жён есть ещё одна -- его собственная. Подробнее в комментах.