решение задачи про мудрецов
Задача здесь.
Я сначала объясню, что делает каждый мудрец, и почему это почти работает, но не совсем, а потом - как мудрецы пользуются помощью стражника, чтобы это точно работало.
Мудрец входит в комнату и видит 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 "неправильных" фотографий для каждого мудреца каким-то хитрым указанием для стражника.
P.P.S. В первоначальной формулировке этой задачи не было никакого стражника, вместо фотографий были имена мудрецов в закрытых ящиках, и каждый из 100 мудрецов мог открыть не более 50 ящиков. Более того, мудрецы "побеждают" только если каждый из них находит свое имя; иначе всех казнят. В такой формулировке мудрецы не всегда могут "победить", потому что если есть "длинный цикл", то ничего не поделаешь; вероятность существования "длинного цикла" чуть меньше 70%, так что мудрецы спасаются с вероятностью примерно 30%.
Это не так красиво, как полная победа с помощью стражника; с другой стороны, поскольку нет стражника и поэтому нет никакой возможности передать мудрецам хоть какую-то информацию о ящиках, вообще непонятно, как они могут добиться шансов лучше, чем 50% случайного успеха для каждого, и тогда (1/2)^100 - абсурдно низкий шанс - успеха для всех вместе. Стратегия "смотреть по циклу" кажется каким-то чудом, возникающим абсолютно ниоткуда.
У этой задачи интересная история; ее впервые описал датский ученый Петер Мильтерсен в 2003-м году, но он сам не нашел решения лучше, чем "абсурдно низкий шанс" случайного перебора каждым мудрецом. Хитрое решение нашел его коллега Свен Скиум во время обсуждения за обедом. Популяризовал эту задачу американский ученый и коллекционер хитрых задачек Питер Винклер. Он опубликовал ее в этой подборке из 7 сложных задач с решениями, и примерно в 2008-м году эта ссылка была на слуху у всех любителей задач такого рода.
Я сначала объясню, что делает каждый мудрец, и почему это почти работает, но не совсем, а потом - как мудрецы пользуются помощью стражника, чтобы это точно работало.
Мудрец входит в комнату и видит 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 "неправильных" фотографий для каждого мудреца каким-то хитрым указанием для стражника.
P.P.S. В первоначальной формулировке этой задачи не было никакого стражника, вместо фотографий были имена мудрецов в закрытых ящиках, и каждый из 100 мудрецов мог открыть не более 50 ящиков. Более того, мудрецы "побеждают" только если каждый из них находит свое имя; иначе всех казнят. В такой формулировке мудрецы не всегда могут "победить", потому что если есть "длинный цикл", то ничего не поделаешь; вероятность существования "длинного цикла" чуть меньше 70%, так что мудрецы спасаются с вероятностью примерно 30%.
Это не так красиво, как полная победа с помощью стражника; с другой стороны, поскольку нет стражника и поэтому нет никакой возможности передать мудрецам хоть какую-то информацию о ящиках, вообще непонятно, как они могут добиться шансов лучше, чем 50% случайного успеха для каждого, и тогда (1/2)^100 - абсурдно низкий шанс - успеха для всех вместе. Стратегия "смотреть по циклу" кажется каким-то чудом, возникающим абсолютно ниоткуда.
У этой задачи интересная история; ее впервые описал датский ученый Петер Мильтерсен в 2003-м году, но он сам не нашел решения лучше, чем "абсурдно низкий шанс" случайного перебора каждым мудрецом. Хитрое решение нашел его коллега Свен Скиум во время обсуждения за обедом. Популяризовал эту задачу американский ученый и коллекционер хитрых задачек Питер Винклер. Он опубликовал ее в этой подборке из 7 сложных задач с решениями, и примерно в 2008-м году эта ссылка была на слуху у всех любителей задач такого рода.