решение задачи про мудрецов
Mar. 6th, 2018 06:18 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЗадача здесь.
Я сначала объясню, что делает каждый мудрец, и почему это почти работает, но не совсем, а потом - как мудрецы пользуются помощью стражника, чтобы это точно работало.
Мудрец входит в комнату и видит 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-м году эта ссылка была на слуху у всех любителей задач такого рода.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2018-03-06 04:32 pm (UTC)А если там пять циклов но маленьких?
no subject
Date: 2018-03-06 04:33 pm (UTC)no subject
Date: 2018-03-06 04:39 pm (UTC)Хм, а ведь если я правильно помню и понимаю - это примерно тот же прием, которым поляки до войны расчекрыжили "Энигму" - пока это еще получалось сделать аналитически. "Цикломер" и это вот все...
Перешли к исчислению циклов - и чудовищный объем перебора съежился до выполнимого вручную.
P.S. Так и представляю себе олимпиадную задачу "Для шифровки военных сообщений используется трехроторная шифровальная машина следующей конструкции..." и далее описание по факту. "...Необходимо разработать метод аналитической дешифрации сообщений."
И вбросить в Интернет - вот интересно:
а) решат ли?
б) опознают ли оригинал?
no subject
Date: 2018-03-06 04:40 pm (UTC)Ну и кому помешает цикл, меньший 12-ти?
Ничего не меняем и все.
no subject
Date: 2018-03-06 04:40 pm (UTC)no subject
Date: 2018-03-06 04:48 pm (UTC)1->2->3->....->15->
станет
3->4->...->15->
2->2
no subject
Date: 2018-03-06 05:01 pm (UTC)И решение тогда чисто случайное.
no subject
Date: 2018-03-06 05:02 pm (UTC)no subject
Date: 2018-03-06 05:05 pm (UTC)Это тоже решение.
no subject
Date: 2018-03-06 05:12 pm (UTC)no subject
Date: 2018-03-06 05:16 pm (UTC)no subject
Date: 2018-03-06 05:18 pm (UTC)Хм, а ведь наверное да. Никогда не смотрел на Энигмовские циклы с этой точки зрения. А это похоже они и есть.
no subject
Date: 2018-03-06 05:19 pm (UTC)Просто автор журнала для экономии места пропустил этап "двудольного" графа. С ним, возможно, было бы проще понять.
no subject
Date: 2018-03-06 05:23 pm (UTC)В начале тридцатых ее решили три достаточно случайным образом выбранных поляка.
Правда талантливых и сильно мотивированных.
Но очень молодых - все трое до 30 лет.
no subject
Date: 2018-03-06 05:24 pm (UTC)no subject
Date: 2018-03-06 05:25 pm (UTC)На мой взгляд знание теории графов довольно сильно помогает эту задачку решить (равно как и опыт, скажем, олимпиадного программирования).
no subject
Date: 2018-03-06 05:29 pm (UTC)1 - 2ф
2 - 3ф
3 - 4ф
4 - 5ф
5 - 6ф
6 - 1ф
Меняем две подряд идущие (для простоты 1 и 6):
1 - 2ф
2 - 3ф
3 - 4ф -- ЦИКЛ из 5
4 - 5ф
5 - 1ф
6 - 6ф -- ЦИКЛ из 1
Мы просто увеличили вероятность. Если же мы поменяем фотки 1 и 4 -- то разобьём на 2 цикла. Т.е. гарантированно решим задачу
no subject
Date: 2018-03-06 05:31 pm (UTC)Вероятность решения изначальной задачи.
Date: 2018-03-06 05:34 pm (UTC)А то решение "в лоб" мне не даётся (утонул в комбинаторике).
no subject
Date: 2018-03-06 05:36 pm (UTC)В новой формулировке, мне кажется, легче добраться до идеи решения (действия стражника подсказывают идею перестановок итд.).
Re: Вероятность решения изначальной задачи.
Date: 2018-03-06 05:36 pm (UTC)no subject
Date: 2018-03-06 06:09 pm (UTC)Может быть, он откуда-то знал, что существует решение лучше, но не мог его найти?
Иначе это получается абсурдная даже не задача, а просто история, не представляющая интереса, таких нагенерировать можно сходу много.
Ещё это напомнило задачу с двумя мудрецами в разных башнях, каждому из которых стражник подбрасывает монету, после чего мудрец, глядя на результат, говорит "орёл" или "решка". Если хотя бы один мудрец угадывает, что выпало другому мудрецу, их отпускают, иначе казнят. (Они могут общаться после того, как им сообщили условия, но до того, как развели по башням). Вариант с монетами, конечно, намного проще, хотя на первый взгляд выглядит не менее магическим, чем с 50 ящиками.
no subject
Date: 2018-03-06 06:13 pm (UTC)no subject
Date: 2018-03-06 06:16 pm (UTC)Точнее даже - с какого перепугу вообще описывать такую задачу ?
no subject
Date: 2018-03-06 06:21 pm (UTC)