?

Log in

No account? Create an account
решение задачи про мудрецов - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

решение задачи про мудрецов [мар. 6, 2018|06:18 pm]
Anatoly Vorobey
[Tags|, ]

Задача здесь.

Я сначала объясню, что делает каждый мудрец, и почему это почти работает, но не совсем, а потом - как мудрецы пользуются помощью стражника, чтобы это точно работало.

Мудрец входит в комнату и видит 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:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: levtsn
2018-03-06 04:32 pm

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

(Ответить) (Thread)
[User Picture]From: vishniakov
2018-03-06 04:40 pm

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

(Ответить) (Parent) (Thread)
[User Picture]From: mitrichu
2018-03-06 04:33 pm
Первая с последней тоже решение - это Меняет цикл.
(Ответить) (Thread)
[User Picture]From: livelight
2018-03-06 04:48 pm
В цикле нет "последней", есть только "та, которая за один до первой", то есть, если начать считать с другого места, то вы поменяете не "первую с последней", а "первую со второй", и из
1->2->3->....->15->
станет
3->4->...->15->
2->2

(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vishniakov
2018-03-06 04:39 pm

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


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

(Ответить) (Thread)
[User Picture]From: son_0f_morning
2018-03-06 05:12 pm
Радужные таблицы?
(Ответить) (Parent) (Thread) (Развернуть)
From: dmytro_gil
2018-03-06 05:16 pm
Интересно, не зная ничего про такой тип задач вообще, сколько всего людей на земле смогли ее решить?
(Ответить) (Thread)
[User Picture]From: vishniakov
2018-03-06 05:23 pm

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



Edited at 2018-03-06 17:24 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: son_0f_morning
2018-03-06 05:34 pm

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

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

А то решение "в лоб" мне не даётся (утонул в комбинаторике).
(Ответить) (Thread)
[User Picture]From: avva
2018-03-06 05:36 pm

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

Расчет есть в решении Винклера (ссылка в конце записи).
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2018-03-06 06:09 pm
Я не понимаю, как можно описать эту задачу, не зная решения лучше, чем "абсурдно низкий шанс". Хотя вполне себе представляю, как можно придумать условие под решение.
Может быть, он откуда-то знал, что существует решение лучше, но не мог его найти?
Иначе это получается абсурдная даже не задача, а просто история, не представляющая интереса, таких нагенерировать можно сходу много.

Ещё это напомнило задачу с двумя мудрецами в разных башнях, каждому из которых стражник подбрасывает монету, после чего мудрец, глядя на результат, говорит "орёл" или "решка". Если хотя бы один мудрец угадывает, что выпало другому мудрецу, их отпускают, иначе казнят. (Они могут общаться после того, как им сообщили условия, но до того, как развели по башням). Вариант с монетами, конечно, намного проще, хотя на первый взгляд выглядит не менее магическим, чем с 50 ящиками.
(Ответить) (Thread)
From: dmpogo
2018-03-06 06:16 pm
Я не понимаю, как можно описать эту задачу, не зная решения лучше, чем "абсурдно низкий шанс".

Точнее даже - с какого перепугу вообще описывать такую задачу ?
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2018-03-06 06:21 pm
Интересно попробовать доказать, что нельзя спасти n(K+1)+1 мудреца, если разрешено открывать n фотографий и сделать K транспозиций.
(Ответить) (Thread)
[User Picture]From: son_0f_morning
2018-03-06 06:35 pm
а) Каждая транспозиция разбивает имеющийся цикл не более чем на 2 части (это в лучшем случае. А также могут объединить 2 цикла или оставить цикл неизменным).

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

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

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



Edited at 2018-03-06 18:36 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: pavelm123
2018-03-06 07:01 pm
огромное спасибо за задачу! жаль, что не решил - но несколько дней думал над ней, и какое элегантное решение! просто песня. Спасибо.
(Ответить) (Thread)
From: (Anonymous)
2018-03-06 07:41 pm
Дорогой Авва! Как вам работается в фашистской организации, ограничивающей прием на работу по цвету кожи?

https://www.wsj.com/articles/youtube-hiring-for-some-positions-excluded-white-and-asian-males-lawsuit-says-1519948013
(Ответить) (Thread)
From: (Anonymous)
2018-03-06 09:40 pm
Дорогой аноним! Для симметрии расскажите, пожалуйста, кто Вы такой и где работаете. А то неудобно получается, Вы можете хозяину журнала задавать неудобные вопросы, а он Вам нет.
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: blainemono
2018-03-06 09:06 pm
Хех, прикольно быть тупым.

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

аррр
(Ответить) (Thread)
[User Picture]From: f137
2018-03-06 09:32 pm
Спасибо. Не решил, но получил удовольствие )
(Ответить) (Thread)
[User Picture]From: relf
2018-03-06 11:17 pm

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

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

(Ответить) (Thread)
[User Picture]From: migmit.dreamwidth.org
2018-03-06 11:22 pm
Оригинал красивее.

А уж 12 вместо 10 — это вообще отвратительно.
(Ответить) (Thread)
[User Picture]From: dark_overrider
2018-03-07 04:36 am
Когда я додумался до стратегии хождения по указателям, всё остальное решение придумалось довольно быстро. Но вот как додуматься до этой стратегии, кроме как перебирая варианты стратегий, которые придут в голову?
(Ответить) (Thread)
[User Picture]From: max630
2018-03-07 05:36 am
> 50% случайного успеха для каждого, и тогда (1/2)^100 - абсурдно низкий шанс - успеха для всех вместе

Их совместный шанс выше - среди 2^200 комбинаций есть взаимоисключающие, и они могли бы договориться их избегать. Но с циклами это интереснее.
(Ответить) (Thread)
Страница 1 из 2
<<[1] [2] >>