Наши задача-головоломка в прошлом месяце было спасти Star Trek надводная партия из восьми человек во главе с Предприятие Сотрудник по связям Лейтенант Ухура (играет покойный Мишель Николс). Экипаж заключен в тюрьму инопланетной расой Катенати на планете в Ожерелье Туманность. Чтобы сбежать, они должны максимизировать свою вероятность выполнения задачи, которая на первый взгляд дает лишь призрачную вероятность успеха.
Экипаж из восьми человек информируется о задаче, пока его временно держат в общей комнате, где они могут свободно общаться и разрабатывать стратегию. Через несколько часов их по одному отведут в комнату, называемую комнатой с рулеткой. В этой комнате есть восемь кнопок, расположенных в ряд, каждая из которых запрограммирована на то, чтобы реагировать на разных членов экипажа. Чтобы ввести экипаж в заблуждение, на каждой кнопке случайным образом неправильно помечено имя другого члена экипажа. Каждому члену экипажа разрешено нажимать до четырех кнопок в любом порядке. Всякий раз, когда они нажимают кнопку, они видят, кому эта кнопка на самом деле принадлежит. За четыре попытки они должны найти назначенную им кнопку. Чтобы экипаж вышел на свободу, все они должны преуспеть в этой задаче. Если хотя бы один из них выйдет из строя, будут выполнены все. После того, как член экипажа завершит свою попытку, он должен быть изолирован без возможности передачи информации кому-либо из своих товарищей по экипажу.
Шансы на успех кажутся ничтожными. Если члены экипажа выбирают кнопки случайным образом, у каждого будет 1 шанс из 2 найти свою кнопку. Вероятность успеха всех восьми составляет всего 1 к 256, или около 0.4%.
Но им не нужно нажимать кнопки случайным образом. Одним из способов повысить вероятность успеха может быть каким-то образом сгладить все нажатия кнопок. Это подводит нас к нашему первому вопросу-головоломке.
Головоломка 1
Насколько можно повысить вероятность выживания экипажа, если они будут следить за тем, чтобы все кнопки нажимались одинаково часто (вместо случайного нажатия любых четырех кнопок)?
Роб Корлетт и ДжейПайетт ответили на этот хорошо, как и на все остальные вопросы. Что касается неуловимой центральной идеи головоломок в этой колонке, Роб Корлетт, Дж. Пайетт и Йоуни Сеппянен красиво описал, а Саша Буньон предоставил компьютерное решение.
Вот ответ Роба Корлетта:
Один из способов гарантировать, что каждая кнопка будет нажата одинаковое количество раз, состоит в том, чтобы разделить заключенных на две равные группы по 4 человека.
Каждая группа нажимает только кнопки, соответствующие членам их группы. Таким образом, если A, B, C и D находятся в одной подгруппе, они нажимают только кнопки для A, B, C и D.
Это меняет проблему на вопрос о вероятности того, что каждый заключенный будет отнесен к правильной группе, поскольку тогда они гарантированно нажмут свою кнопку за четыре или меньше нажатий.
Количество способов заполнить первую группу (а значит, и вторую группу) четырьмя людьми равно количеству способов выбрать 4 из 8, что равно C(8, 4) = 70. Следовательно, общее количество способов распределение всех на две группы равно 70.
Существует только одно распределение, которое правильно распределяет каждого заключенного в правильную группу, поэтому вероятность того, что все попадут в правильную группу и все заключенные выживут, составляет 1/70, что в 3.66 раза лучше, чем 1/256 в предыдущей стратегии. [Но это все еще очень мало: всего 1.4% вероятности.]
Головоломка 2
Существует способ повысить первоначальные мрачные шансы более чем в 90 раз, примерно до 36.5%, что кажется чудом! Эта стратегия включает в себя использование петель или цепочек догадок — отсюда ссылки на туманность Ожерелье и Катенати (цепь по латыни цепь). В базовой форме стратегии каждый член экипажа начинает с нажатия кнопки с его именем, затем переходит к кнопке с именем члена экипажа, которому на самом деле принадлежала первая кнопка, и так далее, создавая цепочку имен.
Давайте посмотрим, как это работает на практике. На схеме кнопки показаны белым цветом. Синими буквами ниже показаны истинные владельцы кнопок. Когда первый член экипажа А входит в камеру с рулеткой, она первой нажимает кнопку А. Это кнопка C, поэтому она нажимает кнопку C, затем кнопку E и, наконец, кнопку F, которая на самом деле является собственной кнопкой A, поэтому она успешно нашла ее с четырех попыток. Обратите внимание, что кнопки ACEF образуют замкнутый контур из четырех кнопок. Когда члены экипажа C, E и F ходят по очереди, они также проходят по тому же замкнутому кругу, начиная со своих соответствующих мест, и также находят свои кнопки с четырех попыток.
Это расположение также имеет две меньшие петли по две кнопки в каждой: BD и GH. Эти четыре члена экипажа найдут свои кнопки за две попытки. Так что при таком раскладе все члены экипажа добьются успеха, и они заслужат свою свободу. Ясно, что если в расположении есть только петли длины 4 или меньше, то все члены экипажа добьются успеха и будут освобождены. Если, с другой стороны, есть один цикл из 5 или более, то все члены экипажа в этом цикле не смогут найти свою кнопку с четырех попыток, и экипаж будет казнен. Чтобы найти вероятность успеха, мы можем найти вероятность наличия цикла из 5, 6, 7 или 8, сложить их и вычесть эту сумму из 1. Это легче вычислить, чем наоборот, потому что для восьми пуговиц, может быть только одна петля из 5, 6, 7 или 8 членов.
Есть 8! различные способы расположения восьми кнопок. Но когда мы делаем петли, одна и та же петля составляет восемь из этих расположений (ABCDEFGH образует ту же петлю, что и BCDEFGHA, которая совпадает с CDEFGHAB и т. д.). Таким образом, вероятность наличия цикла размером 8 равна (8!/8)/8!, что равно просто 1/8. Точно так же вероятность наличия петли размера 7 равна 1/7, размера 6 — 1/6, а размера 5 — 1/5. Таким образом, вероятность успеха нашего бесстрашного экипажа равна 1 − (1/5 + 1/6 + 1/7 + 1/8), или 36.5%, как упоминалось ранее.
Вышеупомянутая стратегия работает для любого количества заключенных, и улучшение шансов по сравнению со случайным подходом быстро увеличивается по мере увеличения этого числа. Это примерно в семь раз для четырех заключенных, в 24 раза для шести, в 93 раза для восьми и поразительно (3.8 × 1029)-кратно на 100 заключенных. Ключом к пониманию этого огромного роста является то, что метод связывает успех или неудачу каждого члена группы с успехом других. В очень значительной степени все они добиваются успеха или терпят неудачу вместе. Вероятность успеха группы не слишком сильно падает по сравнению с вероятностью одного человека, падая только с 50% для одного заключенного до 30.69% при неограниченном увеличении числа заключенных. С другой стороны, вероятность случайного подхода или даже успешного подхода «четное нажатие кнопки» быстро снижается почти до нуля даже для небольшого числа заключенных.
Если логика этой стратегии все еще кажется неясной, вот анализ проблемы 100 заключенных в этом отличное видео Veritasium.
Головоломка 3
Эта головоломка была о том, как лейтенант Ухура вспомнил детскую игру, которая была по сути той же головоломкой, но для шести человек. В качестве подсказки я предложил решить задачу вчетвером. Теперь, когда у нас есть формула, мы можем легко вычислить вероятности.
Для четырех человек вероятность того, что самая длинная петля состоит всего из 2 или 1, составляет: 1 - (1/3 + 1/4) или 41.7% с семикратным выигрышем по сравнению со случайным выбором.
Для шести человек вероятность того, что самая длинная петля равна 3, 2 или 1, составляет: 1 - (1/4 + 1/5 + 1/6) или 38.3% с более чем 24-кратным выигрышем по сравнению со случайным выбором.
Головоломка 4
По мере того, как наша история продолжается, выясняется, что один из Катенати особенно невзлюбил Предприятие экипаж и удаленно следит за ними. Он подозревает, что они придумали эффективную стратегию, основанную на диаграмме Ухуры. Он полон решимости помешать их плану, проскользнув в камеру и намеренно изменив порядок надписей на кнопках до того, как начнется рулетка. Сможет ли он успешно сорвать план? Что десант должен скрывать особенно тщательно?
В самом начале обсуждения стратегии экипажа глаза Ухуры внезапно сузились. Она подала сигнал своей команде и переключилась на разговор на николезском, объявив: «Все дальнейшие обсуждения на николезском, пожалуйста». Никольский был новым языком, который Ухура изобрела в начале своей карьеры именно для таких ситуаций, чтобы обойти использование универсальных переводчиков. — Вы, должно быть, заметили этого подозрительного Катенати, — продолжала она. «Он может попытаться саботировать нас, поэтому нам нужно изменить наш план. Вот что нам нужно сделать…»
Ухура излагала новый план до тех пор, пока не убедилась, что каждый член ее команды прекрасно его знает. Затем она задумалась с отсутствующим взглядом в глазах: «Я назвала Николиз в честь культовой актрисы 20-го века. Я рад, что настоял на том, чтобы Звездный Флот сделал его стандартным для всех наших кораблей.
Она повернулась к экипажу. — Это все, офицеры. Ты знаешь что делать!"
Мы точно не знаем, что Ухура сказала своей команде. Но у JPayette и Роба Корлетта была довольно хорошая идея. Вот снова Роб Корлетт:
Если злой Катенати узнает, что они используют эту стратегию, он может переключить имена, отображаемые на дисплее, чтобы убедиться, что цикл длиннее 4.
Чтобы сломать это, заключенные должны согласиться на секретный порядок, который рандомизирует последовательность. Они делают это, говоря что-то вроде «если вы видите имя Ухуры, то перейдите к кнопке с надписью «Чехов». Если вы видите отображаемое имя Чехова, нажмите кнопку с пометкой Smith и т. д.».
Таким образом, переупорядочивание Catenati не имеет значения, поскольку оно работает только в том случае, если вы знаете, как команда будет реагировать на имена на дисплеях. Однако они должны держать в секрете любое изменение порядка, иначе он снова может быть нарушен.
Как мы видели, Ухура позаботилась о сохранности секрета. Каждому члену экипажа просто нужно было использовать один и тот же секретный приказ и убедиться, что злые Катенати не знают, что это такое. На самом деле, изменение приказа злым Катенати фактически увеличило вероятность успеха экипажа!
Это то, что случилось. Ухуру первой отвели в комнату с рулеткой. Она нажала три кнопки. Ни один не принадлежал ей. Должна ли она быть грустной или радостной? Она затаила дыхание и нажала четвертую. Она нашла свою настоящую кнопку!
Она знала, что они все будут спасены.
Головоломка 5
К какому пределу приближается максимальный процент успеха при бесконечном увеличении размера десанта? Можете ли вы объяснить, почему этот метод намного эффективнее, чем случайное нажатие кнопки?
JPayette писал:
Все вышесказанное прямо обобщается на экипаж из 2 человек.n каждому участнику разрешено нажимать не более n кнопки. Из Головоломки 2 мы делаем вывод, что их шансы на успех
1 - (сумма по k между n + 1 и 2n 1 /k).
Сумму можно сравнить с интегралом от 1/x на интервале [n, 2 n], что позволяет доказать, что при n возрастает до бесконечности, указанная выше вероятность уменьшается и достигает поразительного значения 1 − ln(2) ≈ 30.6%. [На самом деле 30.69% с точностью до двух знаков после запятой.]
Роб Корлетт добавил:
Если вы не знаете интеграцию, вы можете быстро получить приблизительный ответ путем расчета с помощью электронной таблицы. Я однажды добрался до 0.307 n достиг около 750, что с точностью до 3 знаков после запятой.
Мы уже объяснили выше, почему этот метод работает. Все петли длиннее 1 используются несколькими членами экипажа. Так что их успехи и неудачи тесно связаны. Это иллюстрация принципа «Все за одного и один за всех». Прямо из руководства Звездного Флота!
Спасибо всем нашим участникам. JPayette и Rob Corlett представили заслуживающие награды ответы, из-за которых эта колонка решений казалась почти излишней. Увы, я должен придерживаться нашего правила выбирать одного победителя в каждой колонке головоломок. Приз Insights присуждается JPayette в знак признания вклада в эту и предыдущую головоломки. Поздравляем! Роб Корлетт, ваш вклад не будет забыт.
Увидимся в следующем месяце за новыми идеями!
