наш завдання-головоломка минулого місяця було заощадити a 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-го століття. Я радий, що наполягав на тому, щоб Зоряний Флот зробив його стандартним на всіх наших кораблях».
Вона повернулася до екіпажу. «Ось і все, офіцери. Ти знаєш, що робити!"
Ми точно не знаємо, що Ухура сказала своїй команді. Але Джей Пайєтт і Роб Корлетт мали гарну ідею. Ось знову Роб Корлетт:
Якщо злий Катенаті почує, що вони використовують цю стратегію, він може змінити імена, показані на дисплеї, щоб забезпечити цикл, довший за 4.
Щоб порушити це, ув'язненим потрібно погодитися на таємне розпорядження, яке рандомізує послідовність. Вони роблять це, кажучи щось на кшталт «якщо ви бачите ім’я Ухури, тоді перейдіть до кнопки з позначкою Chekov. Якщо ви бачите ім’я Чекова, перейдіть до кнопки Сміт тощо.
Таким чином, зміна порядку за допомогою Catenati не має значення, оскільки вона працює, лише якщо ви знаєте, як екіпаж буде реагувати на імена на дисплеях. Однак вони повинні зберігати таємницю будь-якого переупорядкування, інакше його знову можуть зламати.
Як ми бачили, Ухура гарантував збереження таємниці. Кожному члену екіпажу потрібно було лише використати той самий таємний порядок і переконатися, що злий Катенаті не знає, що це таке. Насправді, зміна порядку злим Катенаті фактично збільшила ймовірність успіху команди!
Ось що сталося. Першим до рулетної камери повели Ухуру. Вона натиснула три кнопки. Жоден не був її. Їй сумувати чи радіти? Вона затамувала подих і натиснула четверту. Вона знайшла свій справжній ґудзик!
Вона знала, що їх усіх врятують.
Головоломка 5
До якої межі наближається максимальний відсоток успіху в міру нескінченного збільшення розміру десанту? Чи можете ви пояснити, чому цей метод набагато ефективніший, ніж випадкове натискання кнопки?
JPayette написав:
Все вищесказане прямо узагальнюється для екіпажу з 2 осібn членам кожному дозволено натискати щонайбільше n кнопки. З Головоломки 2 ми робимо висновок, що їхній шанс на успіх є
1 − (підсумувати k між n + 1 і 2n з 1 /k).
Суму можна порівняти з інтегралом від 1/x на інтервалі [n, 2n], що дозволяє довести, що як n зростає до нескінченності, зазначена вище ймовірність зменшується, збігаючись до вражаючого значення 1 − ln(2) ≈ 30.6%. [Насправді 30.69% до двох знаків після коми.]
Роб Корлетт додав:
Якщо ви не знаєте інтегрування, ви можете швидко отримати приблизну відповідь шляхом розрахунку за допомогою електронної таблиці. Одного разу я досяг 0.307 n досягло приблизно 750, що з точністю до 3 знаків після коми.
Вище ми вже пояснили, чому цей метод працює. Усі петлі, довші за 1, використовуються кількома членами екіпажу. Тож їхні успіхи та невдачі тісно пов’язані між собою. Це ілюстрація принципу «Всі за одного, один за всіх». Прямо з посібника Зоряного флоту!
Дякуємо всім нашим дописувачам. Джей Пайєтт і Роб Корлетт надали гідні відповіді, через які цей стовпець рішень здавався майже зайвим. На жаль, я мушу дотримуватися нашого правила вибору одного переможця в колонці головоломки. Приз Insights отримує JPayette як визнання внеску тут і в попередній головоломці. Щиро вітаю! Роб Корлетт, ваші внески не будуть забуті.
До зустрічі наступного місяця, щоб отримати нову статистику!
