[NiHeraNeSsu]

Вот эта задача была в свое время очень популярна, сейчас не знаю.
Видимо, из всех задач, что я слыхал, она имеет самое красивое решение.
Любопытно, что я не слышал, чтобы кто-то заранее не знающий решение, ее решил, хотя само решение доступно школьнику где-то 5-го класса.

Тех, кто решение знает, прошу воздержаться от его выкладки - для остальных она может стать real challenge.

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

Задача имеет еденственное и строгое решение.

[NiHeraNeSsu]

УУУУУпс - неправильный раздел. Модератор, пожалуйста, перенесите куда следует.

[pokerchatko]

Сообщение от NiHeraNeSsu писал пт, 31 марта 2006 21:20

УУУУУпс - неправильный раздел. Модератор, пожалуйста, перенесите куда следует.

Кстати, а какой раздел правильный? Я что-то подходящего на 100% не вижу.

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

[CorwinXX]

Слышал эту задачу на первом курсе. Сам решить не смог.

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

[NiHeraNeSsu]

Сообщение от Gump писал пт, 31 марта 2006 13:43

NHNS, маленькое уточнение требуется-может я не так понял. Допустим в городе 100 семей и все 100 подруг развлекаются на стороне. Я так понимаю, что бл-во в этом городе будет длиться вечно или я не прав?

Неправ. Это просто частный случай, который покрывается общим решением.

[NiHeraNeSsu]

Сообщение от pokerchatko писал пт, 31 марта 2006 13:50

Кстати, а какой раздел правильный? Я что-то подходящего на 100% не вижу.

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

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

[Makedonskiy]

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

[NiHeraNeSsu]

Сообщение от Makedonskiy писал пт, 31 марта 2006 14:08

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

Ну, это уже пропаганда блядства какая-то. Ответ тем не менее неверный.

[pokerchatko]

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

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

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

[Gump]

Сообщение от pokerchatko писал пт, 31 марта 2006 23:42

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

С этим пунктом не согласен

[pokerchatko]

Сообщение от Gump писал пт, 31 марта 2006 23:00

С этим пунктом не согласен

Почему?

[Gump]

Сообщение от pokerchatko писал сб, 01 апреля 2006 00:04

Почему?

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

[Makedonskiy]

Возражения по пунктам.

Общее количество неверных жен неизвестно, и если их больше чем одна, то с твоей логикой - с какой начать ?

Если одна, то все понятно, тот кто не знает ни одной неверной жены, тот и "потерпевший"... А вот если их больше одной, то оба потерпевших будут знать как минимум по одной неверной жене, и будут за себя спокойны.

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

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

[pokerchatko]

Сообщение от Makedonskiy писал пт, 31 марта 2006 23:48

Возражения по пунктам.

Общее количество неверных жен неизвестно, и если их больше чем одна, то с твоей логикой - с какой начать ?

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

Сообщение от Цитата:

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

Ну, на пальцах понятно, но можно попробовать и по индукции.

1. Для одной - понятно, мочат в первую же ночь.
2. Допустим, что если в городе N-1 неверных жен, то их мочат на (N-1)-ую ночь.
3. Докажем, что если их N, то их можно мочить на N-ую ночь. Сейчас в городе одни мужья полагают, что в городе N гулящих, другие - что (N-1). Но поскольку (2) заведомо верно, то (N-1) мочили бы вчера. Следовательно, вторые ошибаются, и им пора убивать.

[Makedonskiy]

Это то понятно, но как им узнать что именно их жена неверна. По твоей логике можно и в одну ночь их всех замочить, все N.

Живой пример. Допустим неверных жен 10. Рогоносцы знают только девять, а остальные по 10 - не очень сильная помощь. Как ему (рогоносцу) вычислить что его жена ему изменяет, если он не знает того, что он знает N-1 неверных женщин... ? И кто будет по твоей логике устанавливать очередь для устранения изменниц в каждую из N ночей... ? А почему-бы их сразу не "того", в одну ночь ...?

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

Мне кажется ответ именно в логике (методе) вычисления неверных жен, а не в их количестве (если оно конечно не равно 1).

[ImmoralZi]

На пальцах:
1. если одна неверная жена - то ее муж сразу мочит ее в первый же день - он других не знает. Радио молчит
2. если две неверных - оба их мужа знают только по одной - но в первый день они не имеют оснований мочить свою жену - но как только выяснится, что и во второй день неверные остались, значит их 2 (так как одну замочили бы сразу) - и с полной уверенностью оба мочат своих жен
3. если три неверных - три мужа знаю только по две, которые исходя из пуркта 2 должны быть замочены на второй день. Если и после второго дня радио трещит, что неверные остались - то значит их не две а три - и все три мужа мочат своих жен.
N. если неверных N, тогда N мужей знают только N-1, которые должны быть замочены в N-1 день, и если радио на следующее утро не умолкает, то все они мочат своих в день N

[ImmoralZi]

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

[Likaen]

Сообщение от Цитата:

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

Нетушки, раз изменила - клеймо навеки. Мочить её! А с кем они изменяют-то? С залётными рыцарями?

В задаче сказано: "В некотором городе живут исключительно люди, умеющие мыслить логически." (Как я поняла под людями подразумеваются мужики.) Поэтому я согласна с решением ImmoralZi.

Предположим в городе N изменщиц.
Рогоносцы знают о N-1
Без рогов знают о N

Сообщение от Цитата:

1. если одна неверная жена - то ее муж сразу мочит ее в первый же день - он других не знает.

Если радио не молчит на второй день, значит их больше чем 1. Те мужики, которые знают только про одну изменщицу, получают основание мочить своих.
Если радио не молчит на третий день, то основание мочить своих получают те, кто знает о 2-х изменщицах. Т.е. на третий день убивают 3-х жён.
Если радио не молчит на N-ый день, то основание мочить своих жён получают те, кто знает о N-1 изменщице.

Сообщение от Цитата:

Таким образом все неверные умрут в один день.

Сообщение от Цитата:

Вопрос: На какой день неверных жен не останется ?

Неверных жён не останется на день, когда радио перестанет объявлять об этом, т.е. на день N+1.

Сообщение от Цитата:

хотя само решение доступно школьнику где-то 5-го класса.

Вот это меня смущает слегка и наводит на мысль, что ответом может быть: Неверных жён не останется на день, когда радио перестанет объявлять об этом.

[ImmoralZi]

А что, действительно, самое логичное решение ))

[NiHeraNeSsu]

Сообщение от Цитата:

Нетушки, раз изменила - клеймо навеки. Мочить её! А с кем они изменяют-то? С залётными рыцарями?

Разве для того, чтобы изменить, требуется кто-то со стороны? Устраивают, б-ди, междусобойчик, и всего делов.

Сообщение от Цитата:

В задаче сказано: "В некотором городе живут исключительно люди, умеющие мыслить логически." (Как я поняла под людями подразумеваются мужики.) Поэтому я согласна с решением ImmoralZi.

А что ж, мужики не люди, что ли? Они тоже умеют мыслить логически, не только бабы, между прочим.

Сообщение от Цитата:

Таким образом все неверные умрут в один день.

Верно. Только лучше говорить не "неверные" а "неверные жены", а то смахивает на мечту исламиста.

Сообщение от Цитата:

Неверных жён не останется на день, когда радио перестанет объявлять об этом, т.е. на день N+1.

И это верно. Но видимо только для данного конкретного города, а не во вселенском масштабе.

Сообщение от Цитата:

Цитата:
хотя само решение доступно школьнику где-то 5-го класса.

Вот это меня смущает слегка и наводит на мысль, что ответом может быть: Неверных жён не останется на день, когда радио перестанет объявлять об этом.

Нет, последнее решение школьника девятого класса, уже поднаторевшего в софистике.

Поздравления всем кто решил - меня например впечатлило. А один ученый дядька как-то сказал, что метод решения этой задачи называется "Метод полной индукции" (не знаю правда что это такое).