Перед вами 12 однакових на вигляд монет. Одна з них фальшива і важить інакше, ніж справжні, але невідомо, легша вона чи важча. Є шальки терезів без гир: вони показують лише, яка чаша важча або що чаші врівноважені. Яка найменша кількість зважувань гарантує, що ви знайдете фальшиву монету і скажете, легша вона чи важча?
Здається, що треба ділити навпіл: 6 на 6, потім 3 на 3, і виходить 4–5 зважувань. Але терези мають три відповіді, а не дві: ліва чаша вниз, права вниз або рівновага. Три зважування дають 3³ = 27 результатів, а варіантів лише 24: 12 монет, кожна легша або важча. Треба тільки кожним зважуванням ділити варіанти на три рівні купки.
Класична задача зі збірок головоломок. Компанію, яка питала б саме про 12 монет, джерела не називають, але легший варіант, 8 монет з однією легшою, Вільям Паундстоун (2003) наводить як питання зі співбесід у Microsoft. Цю задачу люблять, бо перша ідея, «ділити навпіл», тут не працює, а правильна вимагає думати не про монети, а про те, скільки відповідей може дати один прилад.
12 монет, пронумерованих від 1 до 12. Одинадцять справжніх, вони важать абсолютно однаково. Одна фальшива.
Фальшива монета важить інакше, але невідомо, легша вона чи важча. На вигляд її не відрізнити.
Шалькові терези без гир. На кожну чашу можна покласти скільки завгодно монет. Терези показують одне з трьох: ліва чаша важча, права важча або рівновага.
Назвати фальшиву монету і сказати, легша вона чи важча. Не вгадати, а знати напевно, хоч яка монета фальшива.
Яка найменша кількість зважувань це гарантує?
«Ділимо навпіл: 6 на 6, потім 3 на 3, потім ще раз… Виходить 4–6 зважувань»
Хтось важить монети парами і отримує до 7 зважувань. Насправді досить 3, а 2 не вистачить за жодної стратегії. Хитрість у тому, що перше зважування має бути 4 на 4, а ще четверо монет лишаються осторонь.
12 монет, одна фальшива, легша чи важча, невідомо. Оберіть найменшу кількість зважувань, яка, на вашу думку, гарантує успіх.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Ділити навпіл тут пастка: терези дають три відповіді, а не дві. «Рівновага» теж інформація, і її варто використати.
Рахуйте не монети, а варіанти: кожна монета може бути важчою або легшою. Скільки різних історій результатів можуть дати n зважувань?
Варіантів 24, і кожному потрібна своя послідовність показів терезів. Скільки послідовностей дають n зважувань? Це лише нижня межа: перевірте, чи можна так розкласти монети, щоб її досягти.
Клацайте монети, щоб покласти їх на ліву чашу, на праву або прибрати. Монет на чашах має бути порівну. Підступ у тому, що фальшива монета ще не вирішила, якою вона є. Після кожного зважування вона обирає результат, який лишає вам найбільше роботи, але ніколи не суперечить попереднім результатам. Сітка внизу показує, які з 24 варіантів ще можливі.
↑ означає «ця монета важча», ↓ означає «легша». Закреслені варіанти вже виключені.
Оберіть стратегію. Сторінка проганяє її на кожному з 24 варіантів (яка монета фальшива і в який бік) і рахує зважування точно. Потім симулює 100 000 випадкових фальшивок і порівнює частки з точними.
Числа в сітці показують, скільки зважувань знадобилося для кожного варіанта. Червона клітинка означає, що стратегія не відрізнила цей варіант від іншого.
Ключ у тому, що терези відповідають на питання трьома способами, а підозрюваних не 12, а 24. Ось п'ять способів це побачити.
Знайти монету замало: треба ще сказати, легша вона чи важча. Тому кожна монета дає два варіанти, «важча» і «легша». Разом 12 · 2 = 24 варіанти, і будь-яка стратегія мусить їх усі розрізнити.
Кожне зважування закінчується одним із трьох результатів, тож n зважувань дають щонайбільше 3n різних історій. Два зважування дають 9 історій на 24 варіанти: якісь варіанти неминуче дадуть однакову історію, і ви їх не розрізните. Це принцип Діріхле. Три зважування дають 27 ≥ 24, тож 3 зважування можуть вистачити, а що їх справді вистачає, показує раунд 2.
Після першого зважування лишається два, тож у кожній купці має бути не більше 3² = 9 варіантів. Якщо на чашах по k монет, перекіс лишає 2k варіантів (k монет «важча» на нижній чаші і k «легша» на верхній), а рівновага лишає 2 · (12 − 2k). Обидва числа не більші за 9 лише при k = 4.
Для 13 монет варіантів 26, і 26 ≤ 27, тож простий підрахунок не забороняє 3 зважування. Але перше зважування не вміє поділити 26 як 9 + 8 + 9: перекіс завжди дає парну кількість варіантів, тобто щонайбільше 8, а рівновага при 4 на 4 лишає 10. Повний перебір усіх стратегій це підтверджує: для 13 монет потрібно 4 зважування. Якщо ж дати ще одну монету, про яку відомо, що вона справжня, 13 монет вкладаються в 3 зважування.
Монети, що вже побували на врівноважених терезах, точно справжні. Їх можна підкладати, щоб зважування було нерівним за складом підозрюваних: три підозрювані проти трьох еталонів. А після перекосу допомагає перемішати чаші: 1 і 2 лишаються ліворуч, 5 переходить ліворуч, 3 і 6 стоять праворуч, 9 є еталоном. Кожна купка після другого зважування містить не більше 3 варіантів, а 3 варіанти третє зважування розрізняє.
Відповідь із двох рівноймовірних варіантів дає 1 біт, із трьох рівноймовірних дає 1 трит, а це log₂ 3 ≈ 1,585 біта. Щоб вибрати один варіант із 24, потрібно log₃ 24 ≈ 2,89 трита, тож трьох зважувань вистачить, лише якщо кожне дає майже повний трит. Скільки дає перше зважування, залежить від того, наскільки рівно воно ділить варіанти:
Ентропія H = −Σ p · log₃ p досягає максимуму 1 трит, коли три результати рівноймовірні. Розклад 8 + 8 + 8 дає рівно 1 трит, 3 на 3 дає 0,946, а 6 на 6 лише 0,631: рівновага при 6 на 6 неможлива, і третя відповідь терезів пропадає.
N монет дають 2N варіантів. Історія «усі зважування рівні» нікому не годиться: або такого результату не буває, або монета ні разу не лежала на терезах і невідомо, легша вона чи важча.
Перше зважування k на k, осторонь m = N − 2k монет. Перекіс лишає 2k варіантів, рівновага лишає 2m, і на кожен випадок лишається n − 1 зважування.
Ліва нерівність, бо 2k парне, а 3n−1 непарне. Права за тим самим міркуванням про «усі рівні», уже для решти зважувань.
Додаємо: N = 2k + m.
Для трьох зважувань: k ≤ 4 і m ≤ 4, тож N ≤ 12. Межа досяжна: класичний розв'язок вище.
Фрімен Дайсон 1946 року довів, що (3ⁿ − 3)/2 монет можна розібрати за n зважувань і більше не можна. Якщо ж є одна завідомо справжня монета, межа зростає до (3ⁿ − 1)/2: для трьох зважувань 13 монет.
Задача про монети росте у три боки. У математиці вона дає точну формулу і схему, де всі зважування розписані заздалегідь. У логіці вона вчить ставити питання, що ділять варіанти порівну. А на практиці те саме правило будує дерева рішень у машинному навчанні.
Математика
Формула (3ⁿ − 3)/2 росте втричі з кожним зважуванням: 3, 12, 39, 120 монет. Дві зміни умови додають по одній монеті. Якщо є еталонна справжня монета, межа (3ⁿ − 1)/2. Якщо треба лише знайти монету, а легша вона чи важча, байдуже, теж (3ⁿ − 1)/2: одна монета може жодного разу не лягти на терези, і якщо все врівноважилось, це вона.
Обидві зміни разом дають (3ⁿ + 1)/2, тобто 14 монет за 3 зважування. Усі ці числа сторінка перевіряє перебором усіх стратегій для 1–3 зважувань; для 4 зважувань (39, 40, 40 і 41) ми перевірили так само окремо. Курйоз: дві монети без еталона не розібрати взагалі, бо після 1 : 2 невідомо, яка з них винна.
Дивно, але підлаштовуватися під результати не обов'язково. Дайсон показав, що всі зважування можна скласти заздалегідь. Дайте кожній монеті код із трьох знаків: Л означає «на лівій чаші», П «на правій», – «осторонь». Тоді важча монета дає історію, що збігається з її кодом, а легша дає дзеркальну.
Щоб це спрацювало, треба три умови: жоден код не порожній, жоден не є дзеркалом іншого, і в кожному зважуванні на чашах порівну монет. Ненульових кодів 26, вони утворюють 13 дзеркальних пар; з пари можна взяти лише один код, і ще одну пару доводиться відкинути, щоб урівняти чаші. Звідси знову 12.
Логіка
Сторінка вгадає його за 3 питання, на кожне з яких є три відповіді.
Задача про монети вчить загального правила: найкраще питання ділить варіанти, що лишилися, на якомога рівніші частини. Тоді будь-яка відповідь відсікає найбільше. Мовою Шеннона це питання з найбільшою ентропією відповіді: його результат найважче передбачити, тож він найбільше повідомляє.
З двома відповідями правило дає двійковий пошук, як у задачі про отруєне вино. З трьома відповідями виходить трійковий пошук: 27 = 3³, тож 3 питання. Зважування 6 на 6 схоже на питання, на яке ніколи не відповідають «рівно»: одна з трьох відповідей просто пропадає.
Практика
14 днів із класичного прикладу Квінлана: погода і чи грали того дня в теніс (теніс додали пізніші підручники). Клацніть ознаку, щоб розбити дні за нею.
1986 року Росс Квінлан описав алгоритм ID3, який будує дерево рішень за таблицею прикладів. На кожному кроці він обирає ознаку, після якої невизначеність відповіді падає найбільше: приріст інформації дорівнює ентропії до розбиття мінус середня ентропія частин. Це те саме правило, що й «4 на 4»: найкраще питання найбільше зменшує невизначеність.
Тут ентропія відповіді «грали чи ні» дорівнює 0,940 біта. Прогноз (сонячно, хмарно, дощ) знижує її найбільше, на 0,247 біта (Квінлан округлює до 0,246), тож він стає коренем дерева. Далі в сонячні дні вирішує вологість, а в дощові вітер, і дерево класифікує всі 14 днів без помилок. Те саме правило працює в діагностиці несправностей: першою роблять перевірку, яка найрівніше ділить можливі причини.
Версія з дванадцятьма монетами вперше з'явилася друком у січні 1945 року: її запропонував Е. Д. Шелл як задачу в «American Mathematical Monthly». Того ж року Говард Гросман опублікував нотатку «The twelve-coin problem» у «Scripta Mathematica».
Фрімен Дайсон, згодом відомий працями з квантової електродинаміки, опублікував у «Mathematical Gazette» статтю «The problem of the pennies». Він розв'язав задачу для будь-якої кількості зважувань і показав схему з трійковими кодами, де всі зважування задано наперед.
Це легенда, але гарна. Річард Гай і Річард Новаковський (1995) пишуть, що під час Другої світової задача була популярна по обидва боки Атлантики і її навіть пропонували скинути над Німеччиною, щоб зірвати ворожі воєнні зусилля. Ден Педо 1958 року переказав дзеркальну історію: нібито її підкинули в Британію ворожі агенти, бо дослідники операцій витратили на неї надто багато людино-годин.
1612 року Клод-Гаспар Баше де Мезіріак у збірці «Problèmes plaisans et délectables» показав, що гирями 1, 3, 9 і 27 можна зважити будь-яку цілу вагу від 1 до 40, якщо класти гирі на обидві чаші. Він зауважив, що цю властивість помічали багато хто, але ніхто не пояснив, і довів її. Це та сама трійкова система з цифрами −1, 0, +1.
У Московському університеті під керівництвом Миколи Брусенцова збудували «Сетунь», комп'ютер на збалансованій трійковій системі: кожен розряд мав значення −1, 0 або +1, як шальки терезів. Машин випустили близько п'ятдесяти.
Таблиця з 14 днів погоди з'явилася 1986 року в статті Росса Квінлана «Induction of Decision Trees» у першому томі журналу «Machine Learning». У Квінлана це просто суботні ранки, придатні «для якогось невизначеного заняття», а приріст інформації прогнозу він друкує як 0,246 біта. Тенісом це заняття стало в пізніших підручниках, і таблиця тепер, мабуть, найвідоміший навчальний приклад дерев рішень.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.