Мудрецы в тюрьме
Оригинал взят у avva
Лет 10 назад эта задачка была на слуху, удивляла и поражала.
С тех пор прошло время, многие, наверное, ее не знают - а я к тому же прочитал формулировку, в которой она выглядит, пожалуй, привлекательнее:
Итак, король решил, что придворные мудрецы зря проедают его деньги, и повелел всех 20 мудрецов бросить в тюрьму.
Чтобы проверить, кто из них действительно мудрец, советники короля придумали следующий тест.
На длинном столе в тронной комнате разложены в ряд фотографии всех 20 мудрецов, лицевой стороной вниз. Стража приводит мудрецов по одному из тюремной камеры и ставят перед столом. Каждый мудрец может перевернуть не более 12 фотографий, и среди перевернутых обязана быть его собственная фотография. Если нашел свою фотографию - его тут же выпускают на свободу (он не может передать никаких сведений тем мудрецам, что еще не прошли проверку).
Если не нашел - его тут же казнят.
В любом случае все раскрытые фотографии переворачивают обратно - их порядок остается таким же, как раньше - и вызывают следующего мудреца.
Когда надзиратели пришли в камеру, где вместе сидели все мудрецы, и сообщили им, что на следующее утро им предстоит эта проверка, мудрецы поначалу приуныли. Но потом решили провести оставшееся время с пользой, и придумать какой-нибудь хитрый трюк, который поможет им избежать казни. После долгих уговоров мудрецам удалось подкупить одного из стражников, который согласился пробраться в тронную комнату перед рассветом, когда все уже будет приготовлено заранее к проверке и фотографии будут разложены. Стражник может перевернуть все фотографии, изучить их, и, действуя по инструкциям мудрецов, обменять местами какие-то две из них (и все перевернуть обратно, конечно). Ничего больше стражник не согласился сделать - только поменять местами две фотографии - он боится, что иначе церемонимейстер может заметить. Кроме того, он уже не успеет вернуться к мудрецам перед проверкой и что-либо им рассказать.
Придумайте, как ВСЕ мудрецы могут избежать казни.
Я сначала объясню, что делает каждый мудрец, и почему это почти работает, но не совсем, а потом - как мудрецы пользуются помощью стражника, чтобы это точно работало.
Мудрец входит в комнату и видит 20 перевернутых фотографий, расположенных в ряд. Ему разрешается переворачивать и смотреть не более чем на 12 из них. Как он будет искать свою?
Пусть мудрецы заранее перенумеруют себя в каком-то порядке. Сам порядок неважен, главное, что каждый мудрец знает свой номер и номера всех остальных мудрецов. Предположим, я мудрец номер 10. Я подхожу к столу и переворачиваю фотографию номер 10 (10-ю слева в ряду). Если на ней я, хорошо. Если нет, то это какой-то другой мудрец, скажем номер 5. Теперь я переворачиваю фотографию номер 5 и смотрю кто там. Там мудрец номер 12. Теперь переворачиваю фотографию номер 12, и так далее.
Как этот процесс может завершиться?
Каждая фотография показывает стрелкой на следующую: 10 -> 5 -> 12 -> ...
Рано или поздно какое-то число должно повториться (у нас их всего 20), и тогда замкнется цикл. Причем цикл обязан завершиться числом 10, с которого он начался. Не может быть, скажем, в примере выше, что следующий шаг будет 12->12, или 12->5, потому что фотографии 12-го и 5-го мудрецов мы уже открыли, они не могут снова встретиться. Цикл обязан завершиться открытием 10-го мудреца, т.е. меня, и так я найду свою фотографию. Есть только одна крохотная проблема: это может занять больше, чем 12 попыток.
Назовем такую проблему "длинный цикл".
Необязательно эта проблема есть; может, у всех мудрецов "короткие циклы": например, 1->2->1, 3->4->3, 5->6->5 и так далее, каждый за две попытки находит свою фотографию. Но это должно сильно повезти. На самом деле если фотографии разбросаны в случайном порядке, то с вероятностью больше 50% будет "длинный цикл", хотя входить в подробности этого вычисления я не буду.
Если есть "длинный цикл", проход по которому занимает больше 12 фотографий, то у ВСЕХ мудрецов в этом цикле будет та же самая проблема.
Если начать 10 -> 5 -> 12 -> 7 ->... и потом придешь обратно к 10 за 15 шагов, например, то точно так же мудрец номер 5, когда он войдет, будет идти 5 -> 12 -> 7 ->... и найдет свою фотографию за те же 15 шагов. С другой стороны, те мудрецы, которые ВНЕ этого цикла - у них проблемы не будет, потому что их осталось меньше 8 (раз "мой" цикл длиннее 12, а всего мудрецов 20). Все эти другие мудрецы тоже "зациклятся" в каких-то своих циклах, но они все будут короткие, и быстро найдут свои фотографии.
И тут мы пользуемся помощью стражника.
Пусть например есть "длинный цикл" длиной в 15 мудрецов. Оказывается, если поменять местами фотографии 7-го и 15-го мудрецов по номерам внутри цикла (начиная считать с любого из них), то это разобьет цикл на два, длиной в 7 и 8. Для простоты давайте возьмем случай, когда мудрецы идут в цикле по возрастающим номерам фотографий: 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->1. В этом примере на 15-м месте лежит фотография мудреца номер 1, на 7-м месте фотография мудреца номер 8. Если стражник поменяет их местами, то теперь на 7-м месте будет фотография первого, и цикл замкнется: 1->2->3->4->5->6->7->1. А на 15-м будет фотография восьмого, и цикл замкнется: 8->9->...->15->8. В общем случае это не будут строго растущие числа, но "разбивание" цикла происходит ровно так же - можете проверить самостоятельно. Любой цикл можно легко разбить попопам или почти пополам (если в нем нечетное число мудрецов), поменяв местами две фотографии.
Так что окончательное решение такое: мудрецы обучают стражника выбранной им схеме нумеровки. Стражник переворачивает все фотографии и проверяет, какие есть циклы, и есть ли среди них "длинный цикл". Если есть, он разбивает его пополам, меняя местами две фотографии из середины и конца длинного цикла. Теперь, когда каждый мудрец открывает фотографии по своему циклу, он гарантированно дойдет до его конца, т.е. до своей фотографии, за меньше чем 12 попыток.
P.S. Как справедливо заметили многие, на самом деле достаточно 10 попыток, а 12 указано просто чтобы запутать и дать ложную надежду, что может быть можно придумать хитрый способ идентифицировать 8 "неправильных" фотографий для каждого мудреца каким-то хитрым указанием для стражника.
/Питер Винклер | 7 сложных задач с решениями/
Лет 10 назад эта задачка была на слуху, удивляла и поражала.
С тех пор прошло время, многие, наверное, ее не знают - а я к тому же прочитал формулировку, в которой она выглядит, пожалуй, привлекательнее:
Итак, король решил, что придворные мудрецы зря проедают его деньги, и повелел всех 20 мудрецов бросить в тюрьму.
Чтобы проверить, кто из них действительно мудрец, советники короля придумали следующий тест.
На длинном столе в тронной комнате разложены в ряд фотографии всех 20 мудрецов, лицевой стороной вниз. Стража приводит мудрецов по одному из тюремной камеры и ставят перед столом. Каждый мудрец может перевернуть не более 12 фотографий, и среди перевернутых обязана быть его собственная фотография. Если нашел свою фотографию - его тут же выпускают на свободу (он не может передать никаких сведений тем мудрецам, что еще не прошли проверку).
Если не нашел - его тут же казнят.
В любом случае все раскрытые фотографии переворачивают обратно - их порядок остается таким же, как раньше - и вызывают следующего мудреца.
Когда надзиратели пришли в камеру, где вместе сидели все мудрецы, и сообщили им, что на следующее утро им предстоит эта проверка, мудрецы поначалу приуныли. Но потом решили провести оставшееся время с пользой, и придумать какой-нибудь хитрый трюк, который поможет им избежать казни. После долгих уговоров мудрецам удалось подкупить одного из стражников, который согласился пробраться в тронную комнату перед рассветом, когда все уже будет приготовлено заранее к проверке и фотографии будут разложены. Стражник может перевернуть все фотографии, изучить их, и, действуя по инструкциям мудрецов, обменять местами какие-то две из них (и все перевернуть обратно, конечно). Ничего больше стражник не согласился сделать - только поменять местами две фотографии - он боится, что иначе церемонимейстер может заметить. Кроме того, он уже не успеет вернуться к мудрецам перед проверкой и что-либо им рассказать.
Придумайте, как ВСЕ мудрецы могут избежать казни.
Я сначала объясню, что делает каждый мудрец, и почему это почти работает, но не совсем, а потом - как мудрецы пользуются помощью стражника, чтобы это точно работало.
Мудрец входит в комнату и видит 20 перевернутых фотографий, расположенных в ряд. Ему разрешается переворачивать и смотреть не более чем на 12 из них. Как он будет искать свою?
Пусть мудрецы заранее перенумеруют себя в каком-то порядке. Сам порядок неважен, главное, что каждый мудрец знает свой номер и номера всех остальных мудрецов. Предположим, я мудрец номер 10. Я подхожу к столу и переворачиваю фотографию номер 10 (10-ю слева в ряду). Если на ней я, хорошо. Если нет, то это какой-то другой мудрец, скажем номер 5. Теперь я переворачиваю фотографию номер 5 и смотрю кто там. Там мудрец номер 12. Теперь переворачиваю фотографию номер 12, и так далее.
Как этот процесс может завершиться?
Каждая фотография показывает стрелкой на следующую: 10 -> 5 -> 12 -> ...
Рано или поздно какое-то число должно повториться (у нас их всего 20), и тогда замкнется цикл. Причем цикл обязан завершиться числом 10, с которого он начался. Не может быть, скажем, в примере выше, что следующий шаг будет 12->12, или 12->5, потому что фотографии 12-го и 5-го мудрецов мы уже открыли, они не могут снова встретиться. Цикл обязан завершиться открытием 10-го мудреца, т.е. меня, и так я найду свою фотографию. Есть только одна крохотная проблема: это может занять больше, чем 12 попыток.
Назовем такую проблему "длинный цикл".
Необязательно эта проблема есть; может, у всех мудрецов "короткие циклы": например, 1->2->1, 3->4->3, 5->6->5 и так далее, каждый за две попытки находит свою фотографию. Но это должно сильно повезти. На самом деле если фотографии разбросаны в случайном порядке, то с вероятностью больше 50% будет "длинный цикл", хотя входить в подробности этого вычисления я не буду.
Если есть "длинный цикл", проход по которому занимает больше 12 фотографий, то у ВСЕХ мудрецов в этом цикле будет та же самая проблема.
Если начать 10 -> 5 -> 12 -> 7 ->... и потом придешь обратно к 10 за 15 шагов, например, то точно так же мудрец номер 5, когда он войдет, будет идти 5 -> 12 -> 7 ->... и найдет свою фотографию за те же 15 шагов. С другой стороны, те мудрецы, которые ВНЕ этого цикла - у них проблемы не будет, потому что их осталось меньше 8 (раз "мой" цикл длиннее 12, а всего мудрецов 20). Все эти другие мудрецы тоже "зациклятся" в каких-то своих циклах, но они все будут короткие, и быстро найдут свои фотографии.
И тут мы пользуемся помощью стражника.
Пусть например есть "длинный цикл" длиной в 15 мудрецов. Оказывается, если поменять местами фотографии 7-го и 15-го мудрецов по номерам внутри цикла (начиная считать с любого из них), то это разобьет цикл на два, длиной в 7 и 8. Для простоты давайте возьмем случай, когда мудрецы идут в цикле по возрастающим номерам фотографий: 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->1. В этом примере на 15-м месте лежит фотография мудреца номер 1, на 7-м месте фотография мудреца номер 8. Если стражник поменяет их местами, то теперь на 7-м месте будет фотография первого, и цикл замкнется: 1->2->3->4->5->6->7->1. А на 15-м будет фотография восьмого, и цикл замкнется: 8->9->...->15->8. В общем случае это не будут строго растущие числа, но "разбивание" цикла происходит ровно так же - можете проверить самостоятельно. Любой цикл можно легко разбить попопам или почти пополам (если в нем нечетное число мудрецов), поменяв местами две фотографии.
Так что окончательное решение такое: мудрецы обучают стражника выбранной им схеме нумеровки. Стражник переворачивает все фотографии и проверяет, какие есть циклы, и есть ли среди них "длинный цикл". Если есть, он разбивает его пополам, меняя местами две фотографии из середины и конца длинного цикла. Теперь, когда каждый мудрец открывает фотографии по своему циклу, он гарантированно дойдет до его конца, т.е. до своей фотографии, за меньше чем 12 попыток.
P.S. Как справедливо заметили многие, на самом деле достаточно 10 попыток, а 12 указано просто чтобы запутать и дать ложную надежду, что может быть можно придумать хитрый способ идентифицировать 8 "неправильных" фотографий для каждого мудреца каким-то хитрым указанием для стражника.
/Питер Винклер | 7 сложных задач с решениями/