avva | мудрецы в тюрьме

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

Итак, король решил, что придворные мудрецы зря проедают его деньги, и повелел всех 20 мудрецов бросить в тюрьму. Чтобы проверить, кто из них действительно мудрец, советники короля придумали следующий тест. На длинном столе в тронной комнате разложены в ряд фотографии всех 20 мудрецов, лицевой стороной вниз. Стража приводит мудрецов по одному из тюремной камеры и ставят перед столом. Каждый мудрец может перевернуть не более 12 фотографий, и среди перевернутых обязана быть его собственная фотография. Если нашел свою фотографию - его тут же выпускают на свободу (он не может передать никаких сведений тем мудрецам, что еще не прошли проверку). Если не нашел - его тут же казнят. В любом случае все раскрытые фотографии переворачивают обратно - их порядок остается таким же, как раньше - и вызывают следующего мудреца.

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

Придумайте, как ВСЕ мудрецы могут избежать казни.

Update: решение задачи.