Максим Солохин (palaman) wrote,
Максим Солохин
palaman

Category:

Как русским не оказаться в Латинской Америке (математическая головоломка)

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

Желая показать свою справедливость, уважение к образованию и всецелую приверженность идеалам гуманизма, диктатор решил дать им призрачный шанс на спасение, предложив решить неразрешимую задачу.

А именно.

В испытательной комнате были поставлены сто ящиков, в каждый из которых вложена бумага с именем одного из студентов. Студенты по одному заходили в комнату, и каждый из них должен был угадать, в каком из ящиков находится ЕГО имя. Студентам было объявлено заранее, что если хотя бы один из них не справится с задачей, казнят ВСЕХ.

Побуждаемый особо изощренным садизмом, диктатор разрешает каждому студенту совершить пятьдесят попыток. Злобному тирану хочется своими глазами полюбоваться, как обреченные люди будут дрожащими руками открывать проклятые ящики в безумной надежде найти там спасение... но надежда тщетна!
Для каждого в отдельности вероятность угадать "свой" ящик - 0.5, то есть 50%, однако вероятность того, что повезет всем ста исчезающе мала: 0.5100 от нуля отличается чисто академически. Она равна вероятности того, что монетка выпадет одной стороной 100 раз подряд. Такое совпадение так же невероятно, как и любое другое невероятное событие. Этого просто не бывает. А если такое когда-то случалось в истории, значит, имело место самое настоящее чудо.

Студенты заходили в испытательную комнату под одному.
Вот первый зашел и начал открывать ящики один за другим. Ему повезло! Слуги сразу увели прошедшего испытание в изолированную комнату, комнату ожидания, чтобы исключить возможность обмена информацией. Ничего сообщать друг другу студенты не могли. Каждый должен был начинать поиск своего и общего спасения с абсолютного нуля.
Диктатор был спокоен. Сто раз подряд монетка на одну сторону не падает. Негодяи обречены. Нация спасена.

Невероятно, но факт - новые и новые студенты заходили в комнату, и каждому-каждому удавалось найти своё имя, обходя ящики с именами в каком-то особом магическом порядке. Все сто смогли справиться с задачей!
Потрясенный до глубины души диктатор потребовал, чтобы они открыли ему свой секрет. Студенты не стали таиться и вредничать: ведь если бы диктатор решил, что всему виною предательство слуг (может, кто-то из них снабдил студентов информацией о расположении записок), то он казнил бы всех - и слуг, и студентов...

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

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

Чуть позже я раскрою эту тайну здесь под спойлером. Но для начала - подсказка:

[Нажмите, чтобы получить подсказку!]
Представьте, что студента всего два и ящика всего два.
Если они будут действовать наугад, то вероятность везения для каждого - 0.5, а вероятность того, что повезёт обоим - 0.25.

Но нетрудно придумать стратегию, пользуясь которой можно добиться того, что вероятность успеха для обоих будет 0.5![Нажмите, чтобы прочитать следующую подсказку!]
Конечно же, студенты должны просто поделить между собой ящики. Первый будет "мой", а второй - "твой". Если мне не повезло, и в первом ящике окажется твоё имя, то тебе уже всё равно - мы оба обречены. Зато если мне повезёт и в первом ящике окажется моё имя - ура! - тогда во втором ящике наверняка находится твоё имя!

Что за чудо? Каким образом информация просочилась сквозь плотно запертые двери?
Очень просто: если я действую так, как мы договорились, то ты и сквозь закрытые двери знаешь, какой ящик я открыл. Ты не знаешь, увы, что я там нашел. Но это и не имеет значения. Если я нашел там смерть, то тебе уже все равно, что выбирать. Потому имеет смысл предположить, что я нашел там жизнь. И действовать исходя из этого предположения.

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

Теперь, когда Вы поняли главный принцип, можно попытаться обобщить его на случай большего числа студентов и большего числа ящиков.
[Нажмите, чтобы прочитать следующую подсказку!]
Сначала можно сделать просто: первый студент откроет сначала первый ящик, потому второй и так далее. Если ему повезло, значит, его имя находится где-то в первой половине. Следовательно, второму при такой стратегии лучше начинать с конца: 100, 99, 98 и так далее. Ведь имя первого для него бесполезно.

Но что тогда делать третьему?

Надо разделить сто ящиков и сто студентов на группы таким образом, чтобы у каждого студента в каждой группе наверняка нашелся бы "свой" ящик среди ящиков "их" группы.
Ну, начать надо с простого. Допустим, студентов сто, но каждому студенту можно открыть только один ящик. Тогда поступим так же просто, как и в случае с двумя ящиками. Пронумеруем ящики и студентов. Каждый из ста студентов откроет ящик, номер которого совпадает с его собственным номером. Шансы на успех при этом очень малы, но все-таки они больше, чем если бы они открывали ящики наугад.
Не 0.01100 всё-таки, а (1/100)*(1/99)*(1/98)*(1/97)..*(1/2)*1.
Итак, 1-й студент начинает с 1-го ящика, 2-й со второго и n-ый с n-ого.
"Разделили сферы влияния".
Теперь - барабанная дробь! - что делать n-ому студенту после того, как он открыл n-ый ящик и обнаружил там имя m-ого студента?
На этот вопрос есть безумно красивый ответ, единственно правильный спасительный ответ, который максимально повышает шансы на успех.
[Нажмите, чтобы наконец узнать правильное решение!]
Да, конечно! Теперь он должен открыть m-ый ящик. И далее действовать таким же образом. Найдя в m-ом ящике имя k-ого студента, нужно пойти и открыть k-ый ящик и так далее.
Невероятно, но факт! Этот удивительный алгоритм позволяет студентам спастись при описанных условиях. В России водятся умные студенты, способные находить такие решения. Вот здесь Вы можете прочитать обсуждение этой задачи на русскоязычном форуме математиков.
Но мне самому хочется объяснить всем желающим логику этого решения - насколько я смог в неё вникнуть.
[Если хотите подумайте сначала сами. А если недосуг заниматься этим, просто кликните этот спойлер!]
Во-первых, переходя от ящика к ящику согласно указанному алгоритму, n-ый студент рано или поздно непременно найдет своё имя. Почему?
Дело в том, что количество ящиков ограничено. И если бы слуги его не остановили, то он рано или поздно начал бы ходить по кругу. А что значит "ходить по кругу"? Это значит, что в каком-то ящике нашлось его собственное имя, ведь только его собственное имя может вернуть его (согласно алгоритму) к "его собственному" n-ому ящику, с которого он и начал обход. Итак, с вероятностью 50% n-ый студент завершит обход ящиков раньше, чем слуги схватят его и выведут из комнаты испытания в комнату ожидания.[Теперь уже можно полностью осмыслить, почему же эта стратегия ведет к успеху.]Когда в комнату испытания войдет m-ый студент, он начнет двигаться по тому же самому кругу и найдет своё имя спустя столько же шагов, что и первый студент. И таким образом спасется каждый, чьё имя находится внутри данного цикла!
Те студенты, которые не входят в данный цикл, станут ходить по другим циклам. Наш алгоритм, как мы и хотели, разбил их на непересекающиеся группы, каждая из которых движется по своему собственному спасительному циклу.
А значит, таким же образом спасутся и все, если только среди циклов не окажется одного, длина которого превышает 50!
Но вероятность того, что все циклы окажутся короче 50, не так уж мала. Она равна 0,3119...
[Обсуждение математической стороны дела для тех, кому это интересно]
Лично меня эта задача натолкнула на философские размышления.
Каким образом студентами удалось выкарабкаться из совершенно безнадежной на первый взгляд ямы?
Предлагаю обсудить философский аспект дела в комментариях.
Но сам я думаю вот что. Вера в победу и солидарность - вот что так фантастически повысило шансы студентов на успех. Конечно, им могло просто не повезти, так бывает. Но они верили в победу - и победили! А если бы не верили, то наверняка не победили бы.
Вот точно такая же ситуация у нас в России с русскими. Русские верят в то, что они существуют. А скептики (призываю в комменты уважаемого schegloff-а) наносят объективный вред своим скепсисом. И в этом причина того, что концепция krylov-а мне больше импонирует, хотя она и не такая умная, как у schegloff-а. Может, она немножко глупая, но зато конструктивная. А позиция, которую schegloff де-факто проводит в своем ЖЖ, сводится к тому, что "мы все умрём". И на этом фоне меня очень порадовала "Лестница в небо", потому что там, в этой книге, гораздо больше оптимизма, чем в ЖЖурнале schegloff-а.
Может быть, шансы русских на выживание невелики, но пока мы верим в то, что мы существуем, они все-таки не нулевые - Бог милостив. Если же мы отбросим эту надежду как "маловероятную", то эти шансы становятся равны нулю.
С другой стороны, мне импонирует стремление Щеглова подходить к вопросу максимально разумно и основательно. Позиция Крылова на этом фоне и правда выглядит чуть-чуть глуповато.
Но ведь и студент-математик из моей притчи - он не просто бил себя пяткой в грудь, крича "у нас есть шансы!". Он разработал разумную стратегию, основанную на предположении, что "нам повезет" и при этом максимально увеличивающую шансы на победу.
Итак, если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколько-нибудь развязности, какая у Балтазара Балтазарыча, да, пожалуй, прибавить к этому ещё дородности Ивана Павловича если каким-то образом совместить разумный и научный подход Щеглова с оптимизмом Крылова, терпеливо перенося при этом брюзгливое ворчание Щеглова и доброжелательно снисходя к немощам Крылова - то можно, вполне увеличить шансы на нашу общую победу.
Вот на какие размышления натолкнула меня сия латиноамериканская энигма.
Tags: Габсбурги, математика

callaby

June 5 2016, 23:04:48 UTC 3 years ago Edited:  June 5 2016, 23:09:27 UTC

Здравствуйте! Примерно 30% успеха. И мне кажется, что оптимальная стратегия может быть хорошей наглядной иллюстрацией к термину ассабийя, который я тоже узнал, прочитав книгу Щеглова
Спасибо!
Да, именно так! Мне тоже кажется, что это великолепный пример солидарности (так бы я перевел слово "асабийя" исходя из того, что прочитал об асабийе в "Лестнице в небо")!

dragon_ru

June 6 2016, 03:06:03 UTC 3 years ago Edited:  June 6 2016, 03:10:49 UTC

Вероятность успеха - 1/е :) Но задачка хорошая, просто я ее раньше знал, так что мне было легко :)

А вот еще задачка с похожим методом решения. Дан массив размера n+1 с целыми числами между 1 и n. Найти хотя бы одну пару одинаковых чисел за O(n) действий, используя О(1) элементов памяти.
> Вероятность успеха - 1/е :)

Нет, это случайное совпадение :)
Вероятность зависит от того, сколько ящиков разрешается открыть каждому студенту.

Если 90, то примерно 0.9
Если 80, то примерно 0.8
Если 70, то примерно 0.65
Если 60, то примерно 0.5
Если 50, то примерно 0.3
Если 30, то примерно 0.1

А e тут ни при чем.
Угу. Почему мне показалось, что 1/е - не знаю. Поискал, и нашел вот тут https://en.wikipedia.org/wiki/100_prisoners_problem неплохой анализ, откуда берется 1-ln(2). Кстати, заодно и автор(ы) задачи выяснились :)

А что касается общефилософских рассуждений - еще со времен моих успехов в шахматах у меня сложился свой подход к таким ситуациям. Констатировать, что позиция безнадежна - и интерпретировать это как указание на необходимость нестандартных действий. Сплошь и рядом после того, как противнику приходится принимать решения в нестандартной ситуации, позиция в итоге оказывается вовсе не безнадежной. А сколько ошибок с обоих сторон после этого выявится при компьютерном анализе - не так важно. Куда важнее, кто в итоге ошибся последним :)

palaman

June 6 2016, 08:34:57 UTC 3 years ago Edited:  June 6 2016, 08:37:11 UTC

> Кстати, заодно и автор(ы) задачи выяснились :)

Вот спасибо! Ценная информация. Там же, кстати, нашлось и решение задачи про три двери. Оказывается, это называется Парадокс Монти-Холла
А я и не знал!
Парадокс Монти-холла - жутко неинтересная вещь. Никогад не понима, почему егоназвали парадоксом. Ни разу не видел, чтобы для кого-то он был парадоксом
Намного более парадоксальна.. кажется этоназывается "задача о двух конвертах"
Это что ещё за "два конверта"?
Якубович дает тееб 2 конверта с деньгами. В одном денег ровно в 2 раза больше, чем в другом. Ты выбираешь один, может быть пересчитываешь деньги, а потом Якубович предлагает тебе выбрать другой. Вопрос знатокам: выгоден ли тебе этот обмен?
Разумеется правильный ответ "По барабану" Не выгодин и не невыгоден. Но вот какя зацепка:
Ты понимаешь, что в другом денег равновероятно или 2x или x/2 (Если в твоем конверте денег x) Матожидание этого 5x/4>x ....
(точное решение опирается в частности на невозможность равномерного распределения на всей числовой прямой, а это уже очень красиво, ибо при такой возможности это остается реальным парадоксом-софизмом без опровержения)

palaman

June 6 2016, 16:21:34 UTC 3 years ago Edited:  June 6 2016, 16:22:48 UTC

> Парадокс Монти-холла - жутко неинтересная вещь. Ни разу не видел, чтобы для кого-то он был парадоксом/

Вот на меня посмотри. Мне пришлось думать не меньше часа, пока я не осознал смысл правильного решения. Мне пришлось для этого представить, а что если дверей будет не три, а сто.
а по-моему, сразу было очевидно, что если в парадоксе М-Х Якубович открывает одну дверь, то он сразу изменяет вероятность выигрыша, а потому надо думать-считать и по рузультатам вычислений, скорее всего, смена приведет к большему выигрышу
А чели чть подумать, что становится быстро очевидно, что смена дверей меняет реоятность на противоположную 1/3->2/3 Это, разумеется, в случае, если Якубович всегда показывает дверь А если нет, то вот: http://sxakludant.livejournal.com/88987.html
Ты прав только в том случае, что если schegloff не найдет своего имени, погибнет вся Россия. Но при всем моем самомнении, мне это представляется серьезным преувеличением.

capcrocus

June 6 2016, 13:11:37 UTC 3 years ago Edited:  June 6 2016, 13:13:17 UTC

Отличная жизнеутверждающая задача.
Немного не согласен с иллюстрацией одной из подсказок, где каждому разрешено открывать только один ящик и они открывают ящики со своим номером.
Не 0.01^100 всё-таки, а 0.01*0,02*0.03*...*0.99*1.
Каждый следующий студент имеет ОДНУ попытку, а ящиков остается все меньше - 99, 98, 97...
То есть вероятность успеха равна 0.01*1/99*1/98*1/97..*1/2*1.





Ой, точно :)
Тут я дал маху. С Вашего разрешения, устраню эту ошибку из текста.
А меня она почти 10 лет назад шокировала
С тех пор помню ее как самую красивую головоломку, чтоя видел
Да, поразительный ход мысли.
Найти выход из совершенно безвыходной на первый взгляд ситуации - это ... просто нет слов, как красиво.