Задача про 64 монетах, двох ув'язнених і однієї шахівниці



Примітки перекладача: оскільки я далекий як від математики, так і від англійської мови, в перекладі напевно присутні дрібні неточності і грубі помилки, так що зауваження в особистому повідомленні/коментарі вітаються. Переклад трохи скорочений і перероблений, частково в силу того, що деякі фрази я не зміг перевести/зрозуміти.
Оригінальні позначення сторін монети head/tail я замінив на аверс/реверс, щоб не вносити плутанину російськомовними орел/решка. На ілюстрації вище ліворуч аверс (head), праворуч реверс (tail).

Порятунок неможливо?

Це одна з тих типових загадок про ув'язнених, в яких ви засуджені до смерті і можете врятуватися, тільки якщо доведете свої розумові здібності тюремникові. Ви і ваш друг були укладені у в'язницю. Ваш тюремник пропонує вам випробування. Якщо ви його виконаєте, ви обидва будете звільнені.

Правила:
  • Тюремник відводить вас в окрему камеру. В камері знаходяться шахівниця і банку з 64 монетами.
  • Тюремник бере монети по одній і кладе їх на кожну клітину дошки. Він поміщає монети довільно — деякі будуть звернені вгору аверсом, деякі — реверсом (або всі будуть аверсом, або реверсом, ви поняття не маєте, все на розсуд тюремника). Якщо ви спробуєте втрутитися в процес розкладки монет, це спричинить негайну смерть. Якщо ви спробуєте примусити, порадити або переконати тюремника будь-яким способом — негайна смерть. Ви можете тільки дивитися.
  • Коли всі монети будуть розкладені, тюремник вкаже на одну з клітин і скаже: «Ця!» Зазначена клітина — «магічна» — ваш ключ до свободи.
  • Тюремник дозволить вам перевернути одну монету на дошці. Тільки одну, але це може бути будь-яка монета на ваш вибір. Це єдина зміна, що вам дозволено зробити в розкладці тюремника.
  • Потім ви будете виведені з кімнати. Якщо ви спробуєте залишити будь-які повідомлення або підказки для вашого друга… так, ви вгадали, негайна смерть!
  • Тюремник призведе вашого друга в кімнату.
  • Ваш друг повинен буде оглянути дошку (чіпати заборонено) і вирішити, де, на його погляд, розташована «магічна» клітина.
  • У нього тільки одна спроба. Виходячи з розташування монет, він повинен вказати на клітину і сказати: «Ця!»
  • Якщо він вкаже вірно, ви обидва будете помилувані і негайно звільнені. Якщо невірно — вас обох стратять.
  • Тюремник пояснює ці правила вам обом заздалегідь і дає час наради, щоб розробити стратегію.

Можливо розробити стратегію?

На перший погляд, цю задачу неможливо вирішити. Ми не можемо впливати на тюремника, розкладка монет може бути будь-яка, і ми поняття не маємо, на яку клітину тюремник вкаже (фактично, він сам, можливо, не знає, яку клітину вибере).

64 клітини, на які він може зазначити. 26 можливих відповідей. Нам потрібно 6 бітів інформації, щоб точно ідентифікувати клітку. Якщо ви перевертаєте монету, це один біт інформації. Оскільки ми не можемо передати стан дошки «до», у нашого друга немає можливості вказати, яка монети була перевернута. Подумайте, якщо один входить в кімнату і бачить 63 аверсу і 1 реверс, він не може знати, що єдиний реверс — це монета, які ви перевернули, або перед вами була дошка з 62 аверсами і 2 реверсами, і ви перевернули один реверс!

Можливо передати 6 бітів інформації перевертанням однієї монети?

Є стратегія, що дозволяє вам врятуватися зі 100% ймовірністю незалежно від розкладки монет та положення «магічної» клітини. Рішення не передбачає будь-якого шахрайства або хитрощів, воно чисто математичне.

Початок

Завдання можна вирішити, оскільки фактично у нас є більше інформації, ніж один біт, який передається між вами і вашим другом. Розташування інших монет зберігає інформацію, і ми можемо це використовувати. Насправді у нас є достатня кількість (шість) керованих бітів у розкладці монет, з допомогою яких ми можемо ідентифікувати будь-яку клітину на дошці.

Дві клітини

Уявіть, що у нас дошка всього з двома клітинами. Є 4 можливих варіанти розташування монет (А — аверс, Р — реверс): РР, АА, РА, АР.



Тюремник може вибрати в якості «магічної» як першу клітину, так і другу.
Заздалегідь ми домовляємося про одне правило — якщо тюремник вказує на першу клітку (білу), то необхідно зробити так, щоб на першій клітці був аверс. Можливі варіанти:



Якщо розкладка була РР, я можу перевернути першу монету аверсом, якщо АА — я переверну другу монету, так як перша вже повернена аверсом (за нашим правилом це нічого не змінить, але я повинен перевернути монету).
У всіх варіантах вище на першій клітці виявився аверс. Згідно з нашим правилом, це означає, що тюремник вибрав першу клітку.

Аналогічно, якщо тюремник вкаже на другу клітку, я зроблю так, щоб на першій клітці був НЕ аверс. Це підказка моєму другові, що «магічна» клітина — не перша.



У всіх варіантах на першій клітці не аверс. За нашим правилом це означає, що тюремник вибрав другу клітку.

Проблема вирішена!

Індукція

Математики (і деякі програмісти) скажуть вам, що це все, що нам потрібно, щоб довести, що рішення задачі можливо. Якщо ми можемо закодувати один біт інформації, використовуючи дві клітини, то за допомогою математичної індукції ми можемо підтвердити, що можливо закодувати 2 біта в 4 клетах, 3 — в 8… 6 бітів — 64 клітинах.

Двійкове подання

Якщо ми промаркируем клітини від 0 (верхня ліва) до 63 (нижня права) у двійковому поданні, ми зможемо показати, частиною якого вкладеного безлічі кожна клітина є.

оригіналі статті розміщено інтерактивне зображення дошки. Число в нижньому лівому кутку відображає номер клітини в двійковій запису. Кожна цифра представляє безліч, до якого клітина відноситься. Одиниця в будь-якій позиції показує, що клітина знаходиться в одній половині множина, нуль — в іншій. За визначенням кожна клітина унікальна і має індивідуальний набір бітів.

Парність

Замість використання двох клітин як в простому прикладі вище ми розділимо дошку на різні комбінації двох множин. Застосуємо до цих двох регіонах/множиною те ж правило маркування, що і з поодинокими клітинами — будемо позначати, у першому або другому регіоні знаходиться «магічна» клітина.

Оскільки регіони є колекціями клітин, ми не можемо просто повернути всі монети в регіоні аверсом. Замість цього ми перевернемо одну монету. Ми можемо порахувати кількість аверсов в регіоні — якщо їх число буде непарною, прийме це за одиницю, якщо парних — нуль. Перевертання одному монети в регіоні змінить число аверсов з непарного на парне, і навпаки (додавання/віднімання одиниці до будь-якого числа інвертує його парність/непарність).

Таке поняття парності. Перехід з одного стану в інше додаванням або відніманням одного біта широко використовується в комп'ютерах.

Щоб змінити парність регіону, нам достатньо перевернути одну монету в ньому.

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



20 еквівалентно логічному «І» (AND) з 000001, 21 — 000010… 25 — 100000.

За визначенням, кожна клітина має унікальний набір бітів. Ми можемо перевернути одну монету, щоб змінити парність будь-якої комбінації цих фільтрів.

Розкладка, створена тюремником, має власну (природну) парність. Монети розташовані довільним чином, і ми можемо порахувати парність (кількість аверсов) в кожному регіоні. Комбінація цих бітів парності дасть нам випадкове шестибитное число.

Для ідентифікації «магічної» клітини нам необхідно як раз шість бітів, і ми можемо закодувати їх за допомогою парності. Ми знаємо, що можемо перевернути одну будь-яку монету, і це призведе до зміни одного/декількох бітів числа. Все, що нам потрібно — знайти потрібну монету, перевертання якої змінить комбінацію бітів парності таким чином, щоб вийшло необхідне число (двійковий запис номера «магічної» клітини).

Всі разом

Тут я знову відсилаю читачів до інтерактивної моделі у статті-оригіналі.


На лівій дошці можна вибрати розташування «магічної» клітини. Внизу праворуч вказаний помер вибраної клітини (Target=...), ліворуч — його двійкове подання.

Дошка праворуч показує розкладку монет. Зображені тільки аверси (з міркувань наочності), реверси позначені порожніми клітинами. Кнопка «Random» заповнює дошку новим випадковим набором монет. Кнопка «Clear» перевертає всі монети реверсом.

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

Звідки ці значення?

Ми вже знаємо, звідки взялося число під лівою дошкою. Це просто двійкове опис клітини, кожен біт числа показує, присутній чи ні ця монета в фільтрах-степенях двійки, зображених вище.

Сіре число під правою дошкою показує власну парність дошки. Для кожного фільтра ми знаходимо, парне чи непарне число аверсов розташоване в цьому регіоні. Одиниця в будь-якому розряді числа говорить про те, що в цьому регіоні непарне число аверсов.

Зелене число показує номер тієї клітини, стан якої потрібно змінити (перевернути монету), щоб парність дошки відповідала бажаного номером «магічної» клітини. Воно обчислюється виконанням бітової операції виключаюче «АБО» (XOR) над власною парністю дошки і бажаним значенням.

Виключаюче «АБО»

Оператор XOR широко використовується в програмуванні. У нього кілька цікавих властивостей. Якщо виключаюче «АБО» застосувати двічі з одним і тим же значенням, він поверне початковий стан:

(A XOR B) XOR B = A

Також, якщо ми застосуємо XOR до якого-небудь числа і повного набору бітів (числа, що складається з одних одиниць), всі біти початкового числа будуть інвертовані. Застосування XOR до якогось набору (встановлених) бітів інвертує у вихідному числі ці біти і зберігає стан інших.

Саме тому ми використовували оператор XOR для обчислення положення монети. Для кожного біта парності, незалежно від того, чи містить він вже вірне значення, і ми хочемо його зберегти (XOR c 0), або ми хочемо переключити його (XOR c 1).

Приклад:
Якщо номер «магічної» клітини 101001 (41) і власна парність дошки 010101, то нам потрібно перевернути монету в клітці 111100 (60):

Також ви можете використовувати XOR, щоб швидко порахувати власну парність дошки. Для цього потрібно один раз обійти всю дошку і провести цю операцію над кожним значенням (порядковим номером) клітини з аверсом.

Математика може врятувати вам життя!


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.