Желая показать свою справедливость, уважение к образованию и всецелую приверженность идеалам гуманизма, диктатор решил дать им призрачный шанс на спасение, предложив решить неразрешимую задачу.
А именно.
В испытательной комнате были поставлены сто ящиков, в каждый из которых вложена бумага с именем одного из студентов. Студенты по одному заходили в комнату, и каждый из них должен был угадать, в каком из ящиков находится ЕГО имя. Студентам было объявлено заранее, что если хотя бы один из них не справится с задачей, казнят ВСЕХ.
Побуждаемый особо изощренным садизмом, диктатор разрешает каждому студенту совершить пятьдесят попыток. Злобному тирану хочется своими глазами полюбоваться, как обреченные люди будут дрожащими руками открывать проклятые ящики в безумной надежде найти там спасение... но надежда тщетна!
Для каждого в отдельности вероятность угадать "свой" ящик - 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-а.Может быть, шансы русских на выживание невелики, но пока мы верим в то, что мы существуем, они все-таки не нулевые - Бог милостив. Если же мы отбросим эту надежду как "маловероятную", то эти шансы становятся равны нулю.
С другой стороны, мне импонирует стремление Щеглова подходить к вопросу максимально разумно и основательно. Позиция Крылова на этом фоне и правда выглядит чуть-чуть глуповато.
Но ведь и студент-математик из моей притчи - он не просто бил себя пяткой в грудь, крича "у нас есть шансы!". Он разработал разумную стратегию, основанную на предположении, что "нам повезет" и при этом максимально увеличивающую шансы на победу.
Итак,
Вот на какие размышления натолкнула меня сия латиноамериканская энигма.
June 5 2016, 23:04:48 UTC 3 years ago Edited: June 5 2016, 23:09:27 UTC
June 6 2016, 02:59:39 UTC 3 years ago
Да, именно так! Мне тоже кажется, что это великолепный пример солидарности (так бы я перевел слово "асабийя" исходя из того, что прочитал об асабийе в "Лестнице в небо")!
June 6 2016, 03:06:03 UTC 3 years ago Edited: June 6 2016, 03:10:49 UTC
А вот еще задачка с похожим методом решения. Дан массив размера n+1 с целыми числами между 1 и n. Найти хотя бы одну пару одинаковых чисел за O(n) действий, используя О(1) элементов памяти.
June 6 2016, 03:15:04 UTC 3 years ago
Нет, это случайное совпадение :)
Вероятность зависит от того, сколько ящиков разрешается открыть каждому студенту.
Если 90, то примерно 0.9
Если 80, то примерно 0.8
Если 70, то примерно 0.65
Если 60, то примерно 0.5
Если 50, то примерно 0.3
Если 30, то примерно 0.1
А e тут ни при чем.
June 6 2016, 08:18:55 UTC 3 years ago
А что касается общефилософских рассуждений - еще со времен моих успехов в шахматах у меня сложился свой подход к таким ситуациям. Констатировать, что позиция безнадежна - и интерпретировать это как указание на необходимость нестандартных действий. Сплошь и рядом после того, как противнику приходится принимать решения в нестандартной ситуации, позиция в итоге оказывается вовсе не безнадежной. А сколько ошибок с обоих сторон после этого выявится при компьютерном анализе - не так важно. Куда важнее, кто в итоге ошибся последним :)
June 6 2016, 08:34:57 UTC 3 years ago Edited: June 6 2016, 08:37:11 UTC
Вот спасибо! Ценная информация. Там же, кстати, нашлось и решение задачи про три двери. Оказывается, это называется Парадокс Монти-Холла
А я и не знал!
June 6 2016, 16:03:42 UTC 3 years ago
Намного более парадоксальна.. кажется этоназывается "задача о двух конвертах"
June 6 2016, 16:05:04 UTC 3 years ago
June 6 2016, 16:08:30 UTC 3 years ago
Разумеется правильный ответ "По барабану" Не выгодин и не невыгоден. Но вот какя зацепка:
Ты понимаешь, что в другом денег равновероятно или 2x или x/2 (Если в твоем конверте денег x) Матожидание этого 5x/4>x ....
June 6 2016, 16:15:00 UTC 3 years ago
June 6 2016, 16:21:34 UTC 3 years ago Edited: June 6 2016, 16:22:48 UTC
Вот на меня посмотри. Мне пришлось думать не меньше часа, пока я не осознал смысл правильного решения. Мне пришлось для этого представить, а что если дверей будет не три, а сто.
June 6 2016, 16:33:03 UTC 3 years ago
А чели чть подумать, что становится быстро очевидно, что смена дверей меняет реоятность на противоположную 1/3->2/3 Это, разумеется, в случае, если Якубович всегда показывает дверь А если нет, то вот: http://sxakludant.livejournal.com/88987.html
June 6 2016, 07:29:11 UTC 3 years ago
June 6 2016, 08:28:03 UTC 3 years ago
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.
June 6 2016, 13:24:41 UTC 3 years ago
Тут я дал маху. С Вашего разрешения, устраню эту ошибку из текста.
June 6 2016, 14:38:59 UTC 3 years ago
С тех пор помню ее как самую красивую головоломку, чтоя видел
June 6 2016, 14:40:27 UTC 3 years ago
June 6 2016, 15:56:13 UTC 3 years ago
Найти выход из совершенно безвыходной на первый взгляд ситуации - это ... просто нет слов, как красиво.