воскресенье, 28 февраля 2016 г.

Задача про визирей и жен

Было у султана N=12 визирей. Узнал он как-то, что у некоторых визирей неверные жены. Решил он им наказание устроить. Сделал так: каждого визиря с его женой посадили в полностью изолированные комнаты, и было им сказано, что сидеть им взаперти, пока все неверные жены не будут убиты своими супругами. Каждое утро все комнаты обходит слуга, проверяя выполнение этого условия. Как только выясняется, что все неверные жены мертвы, всех выпускают. На K=3-ий день всех выпустили, причем все верные жены остались живы. Как визири догадались? Уточнение. Все визири очень умны, и сплетней во дворце предостаточно, так что каждый визирь знает, верная или неверная жена у каждого другого визиря, но ничего не знает про свою. Никакого обмена информацией, пока они взаперти, нет.