наш останній набір головоломок представлені скромними подвійними вагами, історично символом торгівлі та уряду, мистецтва та науки. Терези балансу також популярні в рекреаційній математиці. Головоломки про баланс вимагають чіткого, логічного обґрунтування та добре піддаються математичному узагальненню. Давайте подивимося як Quanta читачі збалансували ці якості в головоломках нижче.
Головоломка 1
У вас є вісім однакових монет. Один підроблений і легший за інші, які мають однакову вагу. Знайдіть погану монету за два зважування. Знайдіть загальну формулу для максимальної кількості монет, у яких можна знайти фальшиву x зважування.
Розгляд простої версії проблеми часто відкриває ключ до вирішення. У цьому випадку уявіть, що у вас є лише три монети, одна з яких легша за дві інші. Якщо ви зважите будь-яке з них проти одного з двох інших, вони або збалансуються, або ні. Якщо ні, ви знаєте, що легше. Якщо балансують, то третій – світлий. Вам потрібно лише одне зважування.
Тож у цій головоломці, якщо ви можете виділити групу з трьох (або менше), що містить легку монету під час першого зважування, вам знадобиться ще одне зважування. Ви можете зробити це, збалансувавши будь-які три проти будь-яких інших трьох. Якщо дві групи незбалансовані, ви знайшли групу, що містить легку, і можете продовжити, як описано вище, для другого зважування. Якщо вони зрівноважені, просто зважте дві монети, що залишилися, одна проти одної, і ви знайдете легшу.
Зауважте, що це також працює, якщо в незваженій групі є три монети, тому ми могли почати з дев’яти монет. Дотримуючись цієї логіки та починаючи з трьох монет, для кожного додаткового зважування ми можемо знайти легку монету втричі більше, ніж кількість монет, яку ми мали раніше. Формула, яка дає нам максимальну кількість монет n in w тому зважування n = 3w.
Головоломка 2
У вас є 12 однакових на вигляд монет. Один важчий або легший за інші, які мають однакову вагу.
-
Знайдіть погану монету за три зважування.
-
Яка максимальна кількість монет, для якої можна знайти погану за чотири зважування? Опишіть, як ви знайдете фальшиву монету.
Рішення цієї головоломки добре описав Тед, який також показав, що ви можете виявити погану монету серед 13 монет за три зважування. Ось рішення Теда (з відступами для розділення трьох зважувань у кожному випадку):
Почніть зі зважування 4 монет проти 4 монет.
Випадок 1: якщо дисбаланс, для другого зважування покладіть по 2 з важчої сторони з обох сторін шкали разом із 1 з легшої сторони.
1a: Якщо незбалансована монета, то поганою монетою є або 2 монети, які все ще знаходяться на важкій стороні, або одна монета, яка все ще знаходиться на легкій стороні.
Зважте 2 можливі важкі монети, поганою є або важча з двох, або одна легка, якщо вони збалансовані.
1b: Якщо друге зважування збалансоване, погана монета є однією з 2 невикористаних із легшої сторони першого зважування.
Зважте один на одного, легший поганий.
Випадок 2: якщо збалансовано, погана монета є однією з 5 монет, що залишилися. Зважте 3 із них проти будь-яких 3 уже зважених (які, як відомо, є хорошими).
Випадок 2a: Якщо монета незбалансована, ви знаєте, що погана монета є однією з цих 3 і легка вона чи важка.
Третє зважування — будь-які 2 монети один проти одного — якщо незбалансоване, це визначає погану монету, якщо збалансоване — остання з трьох.
Випадок 2b: якщо друге зважування збалансовано, погана монета є однією з 2 монет, що залишилися.
Зважте будь-яку з них проти завідомо доброї монети. Якщо цей результат незбалансований, ця нова монета погана, і ви знаєте, важка вона чи легка. Якщо цей результат збалансований, 13-та монета погана, але невідомо, важка вона чи легка (про це нам не потрібно знати, тому ми закінчили).
Тед також показали, що максимальна кількість монет для чотирьох зважувань становить 40. Формула цієї головоломки така: n = (3w − 1)/2.
Для решти головоломок узагальнені формули все ще досліджуються професійними математиками та є предметом опублікованих статей, деякі з яких цитуються Rainer aus dem Spring. Я обмежусь рішеннями для невеликої кількості монет, які ми розглядаємо в головоломках, і згадаю лише узагальнення, які природно випливають із методів, які використовуються в цих випадках.
Головоломка 3
Це варіант головоломки 1. У вас знову є вісім однакових монет, одна з яких легша за інші. Однак тепер у вас є три ваги. Дві ваги працюють, але третя не працює і дає випадкові результати (інколи правильні, а іноді неправильні). Ви не знаєте, яка шкала зламалася. Скільки потрібно зважувань, щоб знайти легку монету?
Як ми бачили в задачі 1, для цього потрібно лише два зважування з хорошими вагами. Ми також знаємо, що дві хороші ваги завжди збігаються, тому, якщо ми просто повторимо кожне зважування на всіх трьох вагах, ми отримаємо відповідь у шість зважувань, як запропонував читач. Якщо ми спробуємо зробити це за меншу кількість зважувань, це стане трохи складніше. Ми не можемо визначити хороші ваги, просто зваживши однакові монети на двох терезах, тому що навіть якщо вони збігаються, будь-яка з двох може бути поганою. (Це також показує, як легко дезінформація або випадкова інформація може заплутати правду.)
Насправді, цю проблему можна вирішити, дуже розумно, лише за чотири зважування! Rainer aus dem Spring опублікував рішення, використовуючи новомодне позначення, яке, здається, було створено для цієї головоломки. Але перш ніж ви підете туди, я хочу, щоб ви уявили сценарій, який, я сподіваюся, зробить усе більш інтуїтивно зрозумілим.
Уявіть, що ви детектив, який розслідує наїзд і втечу в крихітній країні, на автомобілях якої двозначні номерні знаки, які містять лише цифри 0, 1 і 2. Троє людей, A, B і C, спостерігали за інцидентом. Двоє з них завжди відповідають правильно на запитання з трьома варіантами відповідей, а один дає абсолютно випадкові відповіді. Ви не знаєте, хто випадково відповідає. Ви повинні поставити кожному з них одне запитання з трьома варіантами відповідей, а потім вибрати того, хто точно говорить правду, щоб отримати більше інформації.
Ось як ви це робите. Запитайте А, чи перша цифра дорівнює 0, 1 або 2. Скажімо, А скаже 2. Запитайте Б, чи друга цифра 0, 1 або 2. Скажімо, В скаже 1. Потім попросіть С зробити вибір між цими трьома твердженнями:
- Тільки А говорить правду.
- Лише B говорить правду.
- Обидва кажуть правду.
Ви можете повірити тому, кому скаже C, і запитати цю людину про іншу цифру. Щоб зрозуміти чому, подумайте, що якщо А бреше, то С надійний і скаже, що Б говорить правду. Друга цифра фактично буде 1, і тоді ви можете запитати B про першу цифру. Подібним чином, якщо B бреше, то C знову надійний і скаже, що A говорить правду. Тоді перша цифра насправді дорівнює 2, і ви можете запитати А про другу цифру. Нарешті, якщо C бреше, то і A, і B є надійними, тому ви все ще можете вірити та вибирати того, кому C скаже. (І якщо C каже, що і A, і B говорять правду, то вони повинні бути правдиві.) Ключовим тут є те, що ваш вибір запитань не дозволяє C брехати таким чином, щоб поставити під сумнів і A, і B. Оскільки принаймні одне з A і B має бути надійним, ви завжди можете вибрати той, з яким погоджується C, навіть якщо це просто випадкова відповідь. Якщо всі три згодні, то у вас вже є обидві цифри номерного знака.
Ось як перекласти цю казку назад у нашу головоломку. Шкала A, B і C. Ви можете перевести дві цифри номерного знака на монети таким чином: 01 – монета 1, 02 – монета 2, 10 – монета 3, 11 – монета 4, 12 – монета 5, 20 — це монета 6, 21 — це монета 7, а 22 — це монета 8. Проникливі читачі зрозуміють, що це триосновна (або трійкова) система числення. Також зауважте, що існує додаткове можливе число 3, яке ви можете використати для дев’ятої монети, для якої ця техніка також працюватиме, як у головоломці 00.
Під час першого зважування ви ділите монети на їхню першу цифру (з основою 3), тому вашими трьома групами будуть монети [1, 2], [3, 4, 5] і [6, 7, 8]. Зважте [3, 4, 5] проти [6, 7, 8] на шкалі А. Якщо А працює добре, ви матимете правильну першу групу цифр, як у головоломці 1. Аналогічно, для другого зважування на шкалі В ваші групи будуть цифри з однаковою другою цифрою: [1, 4, 7], [2, 5, 8] і [3, 6]. Якщо B працює добре, у вас буде правильна друга цифра. Під час третього зважування на вагах С ви зважуєте групу, яку визначив А, проти групи, яку визначив Б. У нашому прикладі для 21 групами будуть [6, 7, 8] і [1, 4, 7]. Монету 7 не можна покласти з обох сторін одночасно, тому ми її не використовуємо й зважуємо [6, 8] і [1, 4] одна проти одної. Зауважте, що якщо A і B є надійними, тоді 7 насправді є правильною відповіддю, і не має значення, яка сторона виявиться легшою на C. Якщо випадково зважування на C збалансоване, тоді всі три терези збігаються, і Ви отримаєте відповідь (монета 7) лише за три зважування. Якщо A є надійним, а B – ні, легша монета знаходиться в [6, 8], яку шкала C підтвердить, а якщо B надійна, а A ні, легша монета знаходиться в [1, 4], яка шкала C також підтвердить.
Тож за три зважування ми або визначили легку монету, або звузили її групу до двох, а також визначили робочу шкалу. Четверте зважування на вагах A або B (залежно від того, з якими вагами C погоджується) зробить решту.
Це рішення здається мені неймовірно красивим!
Цей метод можна узагальнити, щоб знайти легку монету серед 32x монети в 3x + 1 зважування з даним комплектом терезів. Таким чином, для 81 монети потрібно сім зважувань. Для більшої кількості монет (>~1,000), ще сильніше рішення існує.
Головоломка 4
У вас є 16 монет, вісім з яких важкі й однакової ваги. Інші вісім легкі та такої ж ваги. Ви не знаєте, які монети важкі чи легкі. Монети виглядають однаково, за винятком однієї, яка має спеціальні позначки. Чи можете ви визначити легку чи важку спеціальну монету за допомогою одних хороших терезів за три зважування? З якої максимальної кількості монет ви можете почати й успішно вирішити цю задачу за чотири зважування?
На перший погляд цю головоломку здається майже неможливою за три зважування, як зробив висновок один із наших читачів. Тим не менш, при певній кмітливості це можна зробити, і те, і інше Тед та Rainer aus dem Spring надав правильні рішення. Тед надав кілька безцінних загальних принципів, на які варто звернути увагу.
По-перше, поки ви не отримаєте незбалансований результат зважування, у вас не буде достатньо інформації, щоб визначити, важка чи легка спеціальна монета. Тому вам доведеться спробувати отримати незбалансований результат.
По-друге, якщо ви отримуєте збалансований результат (скажімо, спеціальна монета A врівноважує монету B), ви можете об’єднати збалансовані монети та зважити їх проти двох інших монет, C і D. Якщо вони незбалансовані, у вас є відповідь; інакше ви подвоїли кількість подібних монет, що може допомогти вам отримати незбалансовану відповідь під час наступного зважування. Ви також можете виконати цей процес у зворотному порядку з кількістю монет, які є степенями двійки (4, 8 тощо), якщо у вас є початковий незбалансований результат, як видно з наступного рішення.
Нижче наведено повну процедуру, яка може визначити тип спеціальної монети A в усіх випадках за три зважування. (B, C і D — це три монети, розміщені на тій самій стороні, що й A у вазі 1 (W1); X і Y — це дві монети, які не використовуються в W1.)
Цю головоломку придумав російський математик Костянтин Кноп, світовий авторитет у головоломках із зважуванням монет. Багато його робіт російською мовою, але ви можете знайти кілька головоломок із монетами (серед інших цікавих головоломок) на блозі його співробітниці Тані Хованової.
Що стосується узагальнення, то я залишаю це за вами, щоб побачити, чи працює цей самий метод для пошуку типу спеціальної монети серед 32 монет, з яких 16 важких і 16 легких.
Головоломка 5
У вас є n ідентичні на вигляд монети, деякі з яких підроблені та легші за інші. Все, що ви знаєте, це те, що є принаймні одна фальшива монета і що нормальних монет більше, ніж фальшивих. Ваше завдання виявити всі фальшиві монети.
Той факт, що існує принаймні одна лайт-коін і що нормальних монет більше, ніж лайт-монет, робить цю головоломку менш складною, ніж здається на перший погляд, принаймні для невеликих кількостей. Давайте подивимося на цифри зважувань від однієї до восьми монет.
Для однієї та двох монет не може бути легких монет за другою умовою, тому зважування не потрібні.
Три монети: лише одна легка монета. Для кожної головоломки 1 потрібно одне зважування.
Чотири монети: лише одна легка монета. Потрібне ще одне зважування, отже w = 2.
П'ять монет: від однієї до двох легких монет. Це перший цікавий випадок. Постає питання: чи зважити одну монету проти однієї чи дві монети проти двох?
Якщо зважити один проти одного, то ми можемо мати:
- Два незбалансованих зважування: виявлено дві монети; ми закінчили.
- Одне зважування з двох: збалансовані монети мають бути нормальними, тому остання монета потребує ще одного зважування, w = 3.
- Два збалансованих зважування: під час третього зважування зважте одну монету з кожного попереднього зважування проти іншої. Якщо вони збалансовані, то всі чотири нормальні, а монета 5 є світлою. Ми закінчили; w = 3 знову. Якщо вони незбалансовані, ми знайшли дві легкі монети, і завершили три зважування.
Якщо натомість ми зважимо два проти двох, нам усе одно знадобиться три зважування, тому що ми повинні розрізняти можливості того, що монети можуть бути несхожими або схожими з обох сторін. Зважування з використанням невеликої кількості монет, згрупованих разом, здається, не мають жодних переваг перед зважуваннями окремих монет.
Це підтверджується для:
Шість монет: від однієї до двох легких монет; w = 4.
Сім монет: від однієї до трьох легких монет; w = 5.
Вісім монет: від однієї до трьох легких монет; w = 6. Це рішення має просту структуру:
- Спочатку зробіть чотири зважування однієї монети проти іншої. Усі монети використовуються.
- Найгірший випадок: усі чотири зважування збалансовані (є дві легкі монети, які врівноважують одна одну).
- Наступні два зважування: зважте монету з ваги 1 проти монети з ваги 2; аналогічно зважте монету вагою 3 проти монети вагою 4.
- Одне з цих зважувань буде незбалансованим, ідентифікуючи дві легкі монети. Ми завершили шість зважувань.
Вибачте, наша послідовність 0, 0, 1, 2, 3, 4, 5, 6, звичайно, недостатньо цікава, щоб надіслати її Он-лайн енциклопедія цілих послідовностей!
As Йонас Тегерсен К'єллстадлі вказав, рішення, здається, є w = n − 2 для малих чисел, але ми не довели, що це не зміниться для більших чисел. У деяких n, використання кількох зважувань монет може стати кращим або більшим за зважування n − може знадобитися 2. Ми можемо просто узагальнити рішення для восьми монет на всі ступені числа 2, даючи n − 2 як верхня межа для кількості зважувань для всіх степенів числа 2.
Марк Пірсон обговорив схожість цієї проблеми з кодами з виправленням помилок і запропонував використовувати підхід теорії інформації, заснований на кількості можливих результатів. Використовуючи такий підхід, Майк Робертс опублікував нижню межу для більш загального випадку, який Rainer aus dem Spring вивів наближення для. Райнер також опублікував верхня межа з опублікованої статті, але зазначив, що межі не є різкими для низького n і тому не корисний для малих чисел, які ми розглянули вище. Таким чином, для семи монет наведені межі дають діапазон від 4 до 16, між якими знаходиться наша відповідь, 5. Дж. Пайєтт дає додаткові математичні посилання та межі для всіх головоломок.
Дякуємо всім, хто брав участь. Приз Insights за цей місяць разом отримають Тед і Райнер aus dem Spring. Щиро вітаю!
До нових зустрічей наступного разу Insights.
