Ассоциативные алгебры

kukina_eg


Задачи и незадачи


Previous Entry Share Next Entry
Смерть изменникам
Ассоциативные алгебры
kukina_eg
В жж математического факультета недавно была задача.
Задача известная и не новая, что не делает ее менее интересной и даже немного парадоксальной.

Задача.
В некотором королевстве, жители которого обладают безупречным логическим мышлением, живет некоторое количество семейных пар. Некоторые мужчины в королевстве изменяют своим женам, остальные честные. Информация и слухи в городе распространяются мгновенно и об этих изменщиках всем хорошо известно, кроме их жен: правила этикета горожан не позволяют закладывать мужей женам. То есть те жены, которым изменяют, знают об изменах других мужей, но не знают об измене собственного мужа.

И тут вдруг королева делает объявление:
— В нашем королевстве были зафиксированы случаи измен. Приказываю каждой женщине, как только она узнает о том, что ее муж ей не верен, в ближайшую же ночь его пристрелить.

Вопрос: сколько осталось жить мерзавцам?

Решение.
Предположим, что в стране всего N изменщиков.
Индукцией по числу N докажем, что на N-ую ночь обманутые жены узнают об измене.

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

Предположение индукции. Пусть мы уже доказали, что если в стране k изменников, то на k-ую ночь все они умирают.

Шаг индукции. Предположим, в стране (k+1) неверных мужей. Их жены сначала полагают, что неверных мужей всего k, и ожидают (по предположению индукции) на k-ую ночь услышать о смерти тех мужчин. Естественно, до этого момента никто никого не трогает.
Но убийств не происходит. Что же это такое? Да понятно, изменников ведь не k, а (k+1) и изменником может быть только муж той женщины. Она его и застрелит в (k+1)-ю ночь.
Что и требовалось доказать.

Парадоксальность ситуации заключается в том, что если в задаче N>1, все жители страны и без заявления королевы знали, что в стране есть изменники, т.е. королева никому ничего нового вроде как не сказала... А какие серьезные последствия!

?

Log in