Условие длинное, но задача красивая, по-моему.

Дело было в стародавние времена, когда самолетами никто не летал, ну а на тройках солидному человеку ездить было не с руки. Поэтому все ездили на паровозах. И вот, так случилось что в одном купе вагона собралось N-e число пассажиров. И пассажиры эти были ну совсем не обычные, дело в том, что они были жуткими ленивцами, но при этом у них было развито абсолютно строгое логическое мышление. Поезд тронулся, но в купе было жарко. Один из пассажиров открыл окно и дым от паровоза испачкал лица некоторым из них. Когда пришел кондуктор проверять билеты, он тактично намекнул: "Господа, кое-кто из вас испачкал лицо". Через три остановки поезда на полустанках все пассажиры были умыты и чисты. Хоть это было и давно, но на полустанках могло умываться неограниченное число пассажиров. Так же, отмечю еще раз, что пассажиры были жутко ленивы и никто из них не пойдет умываться если не будет уверен на 100% что у него грязное лицо, все они мыслят строгой логикой. И так вопрос: Сколько было пассажиров с испачканными лицами и сколько было с чистыми лицами?

Еще не заходя почему то уже знал, какая будет задача. Действительно старая. С такой формулировкой встречался в самом начале 60-х. Потом встречал и другие формулировки. Вот одна из них.

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

Встанем на место одного из пассажиров. Предположим, у всех, кого он видит, лица чистые, а кондуктор сказал, что кое у кого лицо грязное. Следовательно, лицо грязное у него. Он идёт умываться на следующем полустанке.

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

Предположим, он видит, что лица грязны у двух других пассажиров. Если у него лицо чистое, то каждый из этих пассажиров применит предыдущий вывод и будет действовать соответственно, а если грязное - то останется на месте.

 

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

Мое сообщение наверное скорее относится к понятию женской логики, но все же ...

 

Лица могут быть только у тех, кто сидит по ходу движения :) При таком подходе метод optim не подходит.

 

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

Типа того... :)

Ну, что - молодцы. Формулировок очень много, ту которую назвал bot, про мудрецов и камни, много других.

Хотя Optimistique не ответил сколько было чистых. :p

Завтра еще какую-нибудь старую задачку вспомню.

Ну ты приведи точное решение.

А чего тут еще приводить - Optimistique все верно изложил. Не понял только смысла его последней фразы - сам не уверен или чтоб других с толку сбить ;)

Вот вспомнил старую задачу - 1961 г. рождения. Для 8-го класса задачка на всесоюзной олимпиаде. К сожалению рисовать я не умею, но тут описать нетрудно.

Возьмем прямоугольник и разделим его горизонтальной линией на два прямоугольника. Один из этих двух прямоугольников разделим пополам вертикальной линией, а другой - на три равные части тоже вертикальными линиями. Нарисовали эту фигуру с 12-ю вершинами? Спрашивается, можно ли провести такую непрерывную линию, которая пересекала бы все отрезки между вершинами ровно по разу. Разумеется, через вершины линия проходить не должна.

Спрашивается, можно ли провести такую непрерывную линию, которая пересекала бы все отрезки между вершинами ровно по разу. Разумеется, через вершины линия проходить не должна.

Задача Эйлера об обходе мостов в Кёнигсберге. Известно и легко доказывается, что задача разрешима только в случае, когда степени островов (количество мостов, ведущих на данный остров) все чётны (тогда путь замкнутый) или ровно два острова имеют нечётную степень (тогда концы пути лежат на нечётных островах). В данном же случае острова имеют степени 5, 5, 4, 5, 4, 9.

   ___   ___________________   ___  
 / __| |________   ________| |__ \
|_|             |_|             |_|
 _       5       _       5       _
| |_   _____   _| |_   _____   _| |
|  _| |_   _| |_____| |_   _| |_  |
|_|     |_|             |_|     |_|
 _   4   _       5       _   4   _
| |_   _| |_____   _____| |_   _| |
 \__| |_________| |_________| |__/

                 9

Задача Эйлера об обходе мостов в Кёнигсберге. Известно и легко доказывается...

;) Так уж и легко? Ну разве что на плечи Эйлера стать. И мостов здесь не 7, как в задаче Эйлера, которую он решил в 1736 г. :D Напоминаю, что это задача не для эрудитов, а для 8-го класса.

Встанем на место одного из пассажиров. Предположим, у всех, кого он видит, лица чистые, а кондуктор сказал, что кое у кого лицо грязное. Следовательно, лицо грязное у него. Он идёт умываться на следующем полустанке.

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

Предположим, он видит, что лица грязны у двух других пассажиров. Если у него лицо чистое, то каждый из этих пассажиров применит предыдущий вывод и будет действовать соответственно, а если грязное - то останется на месте.

 

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

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

Потому я и сказал, что легко запутаться ;)

Есть условие - на третьей остановке все были чистыми. Оно всё и определяет.

Ну ты приведи точное решение.

Приведить тут нечего - Optimistique все рассказал правильно. Количество остановок равно числу грязнуль. Если 100 остановок - 100 грязнуль.

"У некоего султана было несколько визирей (султанат был большой, и визирей, прямо скажем, было немало), а у каждого визиря была любимая жена. Был еще у султана шпион, который все про всех в султанате знал, и про жен всех визирей тоже. И сообщил он однажды султану, что среди любимых жен его визирей есть такие (ну хотя бы одна такая), которые изменяют своим мужьям с другими визирями. И мало того, поскольку женщины - существа любопытные, то раз изменив своему визирю, она не останавливалась пока не перепробует всех остальных.

 

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

Прошел первый день, прошла ночь. Утром шпион прошел в темницу, заглянул в замочную скаважину каждой камеры и объявил, так что все услышали: "Не все неверные жены еще покараны!". Прошел еще один день и еще одна ночь. Снова шпион пришел в темницу утром, заглянул в замочную скаважину каждой камеры и опять объявил, так что все услышали: "Не все неверные жены еще покараны!". И еще день и ночь прошли. И опять шпион пришел в темницу утром, заглянул в замочную скаважину каждой камеры и объявил на этот раз: "Теперь покараны все неверные жены!".

 

Вопрос: сколько любимых жен визирей были неверны своим мужьям?

 

Здесь только надо добавить, что все визири любили своих жен, и никто из них не стал бы убивать жену, если б не был уверен, что она ему изменяла. Но уж если он был уверен в этом, то непременно убил бы - восточные мужчины измен не прощают.

 

[Модератор (Misha): Это --- просто другая формулировка этой же задачи.]

Изменено 30 апреля, 200620 г. пользователем Гость

Уважаемый Миша, если Вы пр задачу с грязными лицами, то не вижу ничего общего, вернее есть существенная деталь - так, скажм в случае одного грязного, он точно шел мыться после 1 остановки. А здесь - как визири могли понять убили ли кого нибудь или нет ... Мне непонятно

QUOTE (Alex_fk @ Apr 28 2006, 18:06)

если Вы пр задачу с грязными лицами, то не вижу ничего общего, вернее есть существенная деталь - так, скажм в случае одного грязного, он точно шел мыться после 1 остановки. А здесь - как визири могли понять убили ли кого нибудь или нет

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

 

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

 

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