решение задачи про мудрецов

[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-м году эта ссылка была на слуху у всех любителей задач такого рода.

Comments

[levtsn.livejournal.com]

А если там пять циклов но маленьких?

[vishniakov.livejournal.com]

Ну и кому помешает цикл, меньший 12-ти?
Ничего не меняем и все.

[avva.livejournal.com]

Тогда каждый мудрец по своему циклу быстро приходит к своей фотографии. Тут важно понять, что каждый мудрец автоматически попадает в "свой" цикл из-за того, что начинает переворачивать со "своего" места.

[mitrichu.livejournal.com]

Первая с последней тоже решение - это Меняет цикл.

[livelight]

В цикле нет "последней", есть только "та, которая за один до первой", то есть, если начать считать с другого места, то вы поменяете не "первую с последней", а "первую со второй", и из
1->2->3->....->15->
станет
3->4->...->15->
2->2

[vishniakov.livejournal.com]

Хм, а ведь если я правильно помню и понимаю - это примерно тот же прием, которым поляки до войны расчекрыжили "Энигму" - пока это еще получалось сделать аналитически. "Цикломер" и это вот все...
Перешли к исчислению циклов - и чудовищный объем перебора съежился до выполнимого вручную.

P.S. Так и представляю себе олимпиадную задачу "Для шифровки военных сообщений используется трехроторная шифровальная машина следующей конструкции..." и далее описание по факту. "...Необходимо разработать метод аналитической дешифрации сообщений."
И вбросить в Интернет - вот интересно:
а) решат ли?
б) опознают ли оригинал?

[son-0f-morning.livejournal.com]

Радужные таблицы?

[blainemono.livejournal.com]

"а если шифр не разгадать - мудрецу отрубят голову проведут химическую кастрацию"

[dmytro-gil.livejournal.com]

Интересно, не зная ничего про такой тип задач вообще, сколько всего людей на земле смогли ее решить?

[vishniakov.livejournal.com]

В начале тридцатых ее решили три достаточно случайным образом выбранных поляка.
Правда талантливых и сильно мотивированных.
Но очень молодых - все трое до 30 лет.

Вероятность решения изначальной задачи.

[son-0f-morning.livejournal.com]

А вы не пробовали посчитать вероятность для изначальной задачи аналитически?

А то решение "в лоб" мне не даётся (утонул в комбинаторике).

Re: Вероятность решения изначальной задачи.

[avva.livejournal.com]

Расчет есть в решении Винклера (ссылка в конце записи).

[gul-kiev.livejournal.com]

Я не понимаю, как можно описать эту задачу, не зная решения лучше, чем "абсурдно низкий шанс". Хотя вполне себе представляю, как можно придумать условие под решение.
Может быть, он откуда-то знал, что существует решение лучше, но не мог его найти?
Иначе это получается абсурдная даже не задача, а просто история, не представляющая интереса, таких нагенерировать можно сходу много.

Ещё это напомнило задачу с двумя мудрецами в разных башнях, каждому из которых стражник подбрасывает монету, после чего мудрец, глядя на результат, говорит "орёл" или "решка". Если хотя бы один мудрец угадывает, что выпало другому мудрецу, их отпускают, иначе казнят. (Они могут общаться после того, как им сообщили условия, но до того, как развели по башням). Вариант с монетами, конечно, намного проще, хотя на первый взгляд выглядит не менее магическим, чем с 50 ящиками.

[dmpogo.livejournal.com]

Я не понимаю, как можно описать эту задачу, не зная решения лучше, чем "абсурдно низкий шанс".

Точнее даже - с какого перепугу вообще описывать такую задачу ?

[(Anonymous)]

Интересно попробовать доказать, что нельзя спасти n(K+1)+1 мудреца, если разрешено открывать n фотографий и сделать K транспозиций.

[son-0f-morning.livejournal.com]

а) Каждая транспозиция разбивает имеющийся цикл не более чем на 2 части (это в лучшем случае. А также могут объединить 2 цикла или оставить цикл неизменным).

Дальше очевидно:
1. Пусть есть цикл длиной n*(k+1)+1. K транспозиций превратят этот цикл в K+1 циклов (в лучшем случае).

2. Тогда минимум один цикл будет иметь длину больше, чем n.

В общем-то вы уже в постановке задачи дали ответ.

[pavelm123.livejournal.com]

огромное спасибо за задачу! жаль, что не решил - но несколько дней думал над ней, и какое элегантное решение! просто песня. Спасибо.

[(Anonymous)]

Дорогой Авва! Как вам работается в фашистской организации, ограничивающей прием на работу по цвету кожи?

https://www.wsj.com/articles/youtube-hiring-for-some-positions-excluded-white-and-asian-males-lawsuit-says-1519948013

[(Anonymous)]

Дорогой аноним! Для симметрии расскажите, пожалуйста, кто Вы такой и где работаете. А то неудобно получается, Вы можете хозяину журнала задавать неудобные вопросы, а он Вам нет.

[blainemono.livejournal.com]

Хех, прикольно быть тупым.

Я быстро дошёл до идеи с циклами, но почему-то вместо очевидной мысли разбить цикл сам зациклился на идее использовать перекладывание карт чтобы что-то сигнализировать мудрецам про расклад, который сигнал будет потом прочитан при помощи двух лишних открытий карт - интуитивно понятно, что для основной части решения требуется десять переворачиваний, значит две лишние явно нужны для получения метаданных, ну явно же!

аррр

[f137.livejournal.com]

Спасибо. Не решил, но получил удовольствие )

[relf.livejournal.com]

Оригинальная задача есть в википедии:

https://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundred_prisoners (https://en.wikipedia.org/wiki/Random_permutation_statistics#One_hundred_prisoners)

[migmit (from livejournal.com)]

Оригинал красивее.

А уж 12 вместо 10 — это вообще отвратительно.

[dark-overrider.livejournal.com]

Когда я додумался до стратегии хождения по указателям, всё остальное решение придумалось довольно быстро. Но вот как додуматься до этой стратегии, кроме как перебирая варианты стратегий, которые придут в голову?

[max630.livejournal.com]

> 50% случайного успеха для каждого, и тогда (1/2)^100 - абсурдно низкий шанс - успеха для всех вместе

Их совместный шанс выше - среди 2^200 комбинаций есть взаимоисключающие, и они могли бы договориться их избегать. Но с циклами это интереснее.

[mih-s-m.livejournal.com]

Хочу внести маленький вклад в чисто литературное оформление задачи. Участие "стражника" подталкивает читателя к поиску какого-то очень простого решения (такого, что запомнит и стражник), а настоящий ответ достаточно сложен и вряд ли по силам служивому.

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

На мой взгляд, так достоверней.

[inhm.livejournal.com]

чем-то напоминает теорию групп перестановок (разложение на циклы и т.п.). это оттуда?

[kbakkbak.livejournal.com]

Очень красиво!

[name-oleg.livejournal.com]

А что нужно загуглить, чтобы найти вычисления вероятности, какие циклы могут получиться? Почему только один длинный, а не два и прочее?