Как русским не оказаться в Латинской Америке (математическая головоломка)
Один латиноамериканский диктатор в гневе хотел казнить сто студентов, виновных в политических беспорядках.
Желая показать свою справедливость, уважение к образованию и всецелую приверженность идеалам гуманизма, диктатор решил дать им призрачный шанс на спасение, предложив решить неразрешимую задачу.
А именно.
В испытательной комнате были поставлены сто ящиков, в каждый из которых вложена бумага с именем одного из студентов. Студенты по одному заходили в комнату, и каждый из них должен был угадать, в каком из ящиков находится ЕГО имя. Студентам было объявлено заранее, что если хотя бы один из них не справится с задачей, казнят ВСЕХ.
Побуждаемый особо изощренным садизмом, диктатор разрешает каждому студенту совершить пятьдесят попыток. Злобному тирану хочется своими глазами полюбоваться, как обреченные люди будут дрожащими руками открывать проклятые ящики в безумной надежде найти там спасение... но надежда тщетна!
Для каждого в отдельности вероятность угадать "свой" ящик - 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-а.
Может быть, шансы русских на выживание невелики, но пока мы верим в то, что мы существуем, они все-таки не нулевые - Бог милостив. Если же мы отбросим эту надежду как "маловероятную", то эти шансы становятся равны нулю.
С другой стороны, мне импонирует стремление Щеглова подходить к вопросу максимально разумно и основательно. Позиция Крылова на этом фоне и правда выглядит чуть-чуть глуповато.
Но ведь и студент-математик из моей притчи - он не просто бил себя пяткой в грудь, крича "у нас есть шансы!". Он разработал разумную стратегию, основанную на предположении, что "нам повезет" и при этом максимально увеличивающую шансы на победу.
Итак, если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколько-нибудь развязности, какая у Балтазара Балтазарыча, да, пожалуй, прибавить к этому ещё дородности Ивана Павловича если каким-то образом совместить разумный и научный подход Щеглова с оптимизмом Крылова, терпеливо перенося при этом брюзгливое ворчание Щеглова и доброжелательно снисходя к немощам Крылова - то можно, вполне увеличить шансы на нашу общую победу.
Вот на какие размышления натолкнула меня сия латиноамериканская энигма.
Желая показать свою справедливость, уважение к образованию и всецелую приверженность идеалам гуманизма, диктатор решил дать им призрачный шанс на спасение, предложив решить неразрешимую задачу.
А именно.
В испытательной комнате были поставлены сто ящиков, в каждый из которых вложена бумага с именем одного из студентов. Студенты по одному заходили в комнату, и каждый из них должен был угадать, в каком из ящиков находится ЕГО имя. Студентам было объявлено заранее, что если хотя бы один из них не справится с задачей, казнят ВСЕХ.
Побуждаемый особо изощренным садизмом, диктатор разрешает каждому студенту совершить пятьдесят попыток. Злобному тирану хочется своими глазами полюбоваться, как обреченные люди будут дрожащими руками открывать проклятые ящики в безумной надежде найти там спасение... но надежда тщетна!
Для каждого в отдельности вероятность угадать "свой" ящик - 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-а.
Может быть, шансы русских на выживание невелики, но пока мы верим в то, что мы существуем, они все-таки не нулевые - Бог милостив. Если же мы отбросим эту надежду как "маловероятную", то эти шансы становятся равны нулю.
С другой стороны, мне импонирует стремление Щеглова подходить к вопросу максимально разумно и основательно. Позиция Крылова на этом фоне и правда выглядит чуть-чуть глуповато.
Но ведь и студент-математик из моей притчи - он не просто бил себя пяткой в грудь, крича "у нас есть шансы!". Он разработал разумную стратегию, основанную на предположении, что "нам повезет" и при этом максимально увеличивающую шансы на победу.
Итак, если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколько-нибудь развязности, какая у Балтазара Балтазарыча, да, пожалуй, прибавить к этому ещё дородности Ивана Павловича если каким-то образом совместить разумный и научный подход Щеглова с оптимизмом Крылова, терпеливо перенося при этом брюзгливое ворчание Щеглова и доброжелательно снисходя к немощам Крылова - то можно, вполне увеличить шансы на нашу общую победу.
Вот на какие размышления натолкнула меня сия латиноамериканская энигма.