Народження групового тестування
Роберт Дорфман описав ідею об'єднаних аналізів у короткій статті «The Detection of Defective Members of Large Populations» в «Annals of Mathematical Statistics». Пізніше він став професором економіки в Гарварді.
Через добу в короля бенкет. У льоху 1000 пляшок вина, і рівно одна з них отруєна. Отрута діє повільно: щур, який випив хоч краплю, помирає приблизно через 20 годин, не раніше. Тож перевірити вино встигнете лише раз: усі щури п'ють одночасно, а потім ви чекаєте. Кожен щур може скуштувати скільки завгодно пляшок. Скільки щурів потрібно, щоб напевно знайти отруєну пляшку?
Здається, що треба по щуру на пляшку, тобто 999. Але кожен щур відповідає на одне питання «так чи ні», а 10 таких відповідей розрізняють 2¹⁰ = 1024 варіанти. Запишіть номери пляшок у двійковій системі, і мертві щури самі складуть номер отруєної.
Ця задача часто трапляється у збірках головоломок для співбесід програмістів і аналітиків. За нею стоїть ціла галузь математики, групове тестування, і та сама ідея, на якій тримається будь-який цифровий код.
У льоху 1000 пляшок, пронумерованих від 1 до 1000. Рівно одна отруєна. На вигляд, запах і смак вони однакові.
Навіть крихітна крапля смертельна, але діє повільно: щур помирає приблизно через 20 годин, не раніше. До бенкету 24 години, тож другої спроби не буде.
Кожному щуру можна дати по краплі з будь-якого набору пляшок: з однієї, з десяти, з п'ятисот. Щур, який не випив отрути, лишається живим.
Усі щури п'ють одночасно. Через 20 годин ви бачите, хто з них живий, а хто мертвий, і за цим маєте назвати отруєну пляшку. Не вгадати, а знати напевно.
Яка найменша кількість щурів гарантує, що ви знайдете отруєну пляшку?
«По щуру на пляшку: 999 щурів, а останню пляшку можна не перевіряти»
Дехто економить і каже «500» або «приблизно 100». Насправді досить 10 щурів, а 9 не вистачить за жодної стратегії. Хитрість у тому, що кожен щур п'є з багатьох пляшок, і важливо, яка саме компанія щурів помре.
1000 пляшок, одна отруєна, один раунд дегустації. Зафіксуйте найменшу кількість щурів, яка, на вашу думку, гарантує успіх.
Тут з'явиться розбір вашої відповіді.
Візьмемо льох поменше. У таблиці рядок відповідає щуру, стовпець пляшці. Клацніть клітинку, і щур питиме з цієї пляшки. Коли стратегія готова, натисніть «Зламати стратегію»: сторінка шукатиме дві пляшки, після яких помруть ті самі щури. Якщо такі є, ви їх не розрізните.
Порівняймо, як часто стратегія називає правильну пляшку залежно від кількості щурів. Якщо кілька пляшок дали однаковий результат, ви обираєте одну з них навмання. Лінії показують точну ймовірність, точки показують частку успіхів у симуляції.
Вісь щурів логарифмічна, щоб на одному графіку вмістилися і 10, і 999. Випадкову стратегію генеруємо заново після кожних N/5 отруєнь (N означає кількість пляшок): кожен щур п'є з кожної пляшки з імовірністю 1/2.
Головне тут не скільки пляшок перевірити, а скільки різних результатів можуть дати щури. Ось п'ять способів це побачити.
Даючи щуру краплі з певного набору пляшок, ви питаєте: «Отрута в цьому наборі?» Мертвий щур означає «так», живий означає «ні». Це одна відповідь із двох можливих, тобто один біт. 10 щурів дають 10 відповідей одночасно.
Дайте щурам ваги 1, 2, 4, …, 512. Щур із вагою 2k п'є з тих пляшок, у двійковому записі номера яких у розряді 2k стоїть 1. Тоді помруть саме ті щури, чиї ваги складаються в номер отруєної пляшки.
Кожен щур буває живим або мертвим, тож m щурів дають щонайбільше 2m різних результатів. Якщо пляшок більше, ніж результатів, дві пляшки неминуче дадуть однаковий результат: це принцип Діріхле, «кроликів більше, ніж кліток». З 9 щурами результатів 512, а пляшок 1000, тож жодна стратегія з 9 щурів не гарантує успіху.
Коли кожен щур п'є лише з однієї пляшки, помирає щонайбільше один щур. 999 щурів могли б дати 2999 різних результатів, а це число з 301 цифри, проте стратегія використовує лише 1000 із них: «помер щур № k» або «ніхто не помер». Майже кожен щур майже напевно скаже «ні», і його відповідь майже нічого не повідомляє.
Клод Шеннон 1948 року запропонував міряти інформацію тим, наскільки відповідь зменшує невизначеність. Відповідь на питання, де «так» і «ні» однаково ймовірні, дає рівно 1 біт, а відповідь, яку ви майже напевно передбачите, дає майже нуль. Щоб вибрати одну пляшку з 1000, потрібно log₂ 1000 ≈ 9,97 біта. У двійковій стратегії кожен щур помирає приблизно в половині випадків (від 489 до 500 пляшок з 1000), тож дає майже повний біт, і 10 щурів якраз вистачає.
Двійкова стратегія не лише досягає межі, а й не потребує жодних обчислень під час дегустації: розклад щурам можна написати заздалегідь, а відповідь прочитати як число. З N пляшками досить ⌈log₂ N⌉ щурів, і менше не можна.
Задача з щурами відкриває двері в три світи. У математиці вона росте в теорію кодів. У логіці стає грою «20 питань». А на практиці той самий прийом економить мільйони аналізів крові і допомагає програмістам шукати помилки.
Математика
Нехай отрута вбиває за 10 годин. Тоді за добу вміщуються два раунди: перший на початку, другий через 10 годин, а результати видно до 20-ї години. Тепер щур має три можливі долі: помер після першого раунду, помер після другого або вижив. Запишіть номер пляшки в трійковій системі: цифра 1 означає «щур п'є з цієї пляшки в першому раунді», 2 означає «у другому», 0 означає «не п'є взагалі».
З m щурами результатів 3m. 3⁶ = 729 замало для 1000 пляшок, а 3⁷ = 2187 досить, тож потрібно 7 щурів. Загалом з r раундами кожен щур дає r + 1 результат, і потрібно ⌈logr+1 N⌉ щурів. Щур, що загинув у першому раунді, у другому вже не п'є, але це не заважає: його цифра вже відома.
8 пляшок, 3 щури, двійкова стратегія. Оберіть дві отруєні пляшки.
Коли отруєних пляшок дві, щур помирає, якщо скуштував хоча б одну з них. Двійкові номери тут підводять: результат показує лише, на яких місцях хоча б в одного з двох номерів стоїть 1, а це не визначає пару однозначно.
Пар із 1000 пляшок C(1000, 2) = 499 500. Результатів має бути не менше, ніж пар, а 2¹⁸ = 262 144 замало, тоді як 2¹⁹ = 524 288 уже досить, тож потрібно щонайменше 19 щурів. Це лише нижня межа, і досягти її непросто. Для 8 пляшок межа дорівнює 5 (28 пар, 2⁵ = 32), а повний перебір усіх стратегій показує, що насправді потрібно 6 щурів.
Так задача про щурів перетворюється на групове тестування: як перевірити багато зразків малою кількістю об'єднаних тестів, коли «поганих» може бути кілька.
16 пляшок, 7 щурів. Оберіть отруєну пляшку, а потім клацніть будь-якого щура, щоб він «збрехав»: помер без причини або вижив попри отруту.
Для 16 пляшок вистачає 4 щурів, але якщо один із них може «збрехати», результат уже не довіряєш. Наївний захист: потроїти кожного щура і вірити більшості, це 12 щурів. Річард Геммінг 1950 року знайшов кращий спосіб: 4 щури несуть номер пляшки, а ще 3 перевіряють парність різних груп. Разом 7.
Чому саме 7? Кожна пляшка має «займати» 8 результатів: чесний і 7 варіантів, де збрехав один із щурів. 16 · 8 = 128 = 2⁷, тож 7 щурів досить упритул, без жодного зайвого результату. Три перевірки утворюють «синдром»: трицифрове двійкове число, яке прямо називає номер щура, що збрехав.
Логіка
Сторінка вгадає його щонайбільше за 10 питань «так чи ні».
У грі «20 питань» один гравець задумує предмет, а інші вгадують його питаннями «так чи ні». Якщо кожне питання ділить варіанти навпіл, 20 питань розрізняють 2²⁰ = 1 048 576 предметів. Програмісти називають це двійковим пошуком.
Є важлива різниця. У грі ви обираєте наступне питання, знаючи попередні відповіді. Щури ж відповідають усі одразу, і питання треба скласти заздалегідь. Дивно, але для однієї отруєної пляшки це нічого не коштує: в обох випадках потрібно 10 питань. Різниця лише в часі: 10 раундів по 20 годин проти одного.
Практика
1943 року економіст і статистик Роберт Дорфман запропонував перевіряти чоловіків, яких призивали до армії США, на сифіліс так: змішати кров k людей і зробити один аналіз. Якщо він негативний, усі k здорові. Якщо позитивний, кожного з групи перевіряють окремо. Тоді на людину припадає 1/k + 1 − (1 − p)k тестів, де p означає частку хворих.
Для сифілісу тоді ідею так і не застосували: за даними книжки Ду і Хвана з групового тестування, аналіз Вассермана втрачав точність, коли змішували вісім-дев'ять зразків. Зате 2020 року, під час пандемії COVID-19, Техніон і лікарня Рамбам в Ізраїлі показали, що ПЛР-тест знаходить один позитивний зразок у суміші з 32 чи 64.
А програмісти щодня шукають «отруєну пляшку» командою git bisect: вона знаходить коміт, що зламав програму, двійковим пошуком. Серед 1000 комітів на це йде близько 10 кроків, тільки кожен крок залежить від попереднього, як у грі «20 питань».
Роберт Дорфман описав ідею об'єднаних аналізів у короткій статті «The Detection of Defective Members of Large Populations» в «Annals of Mathematical Statistics». Пізніше він став професором економіки в Гарварді.
Скорочення «bit» від «binary digit» придумав Джон Тьюкі в службовій записці Bell Labs 9 січня 1947 року. Друком слово вперше вжив Клод Шеннон 1948 року в статті «A Mathematical Theory of Communication».
Річард Геммінг працював у Bell Labs, і його дратував зчитувач перфокарт, який раз у раз помилявся. Так з'явився код (7,4): 4 біти даних, 3 перевірні, і будь-яка одна помилка виправляється.
Гра «20 питань» відома щонайменше з XVIII століття, а в 1940-х у США стала популярною радіовікториною. Якщо кожне питання ділить варіанти навпіл, 20 питань розрізняють 2²⁰ предметів.
У березні 2020 року дослідники Техніону й лікарні Рамбам повідомили, що об'єднаний ПЛР-тест виявив коронавірус у суміші 64 зразків, серед яких позитивним був лише один. Окремо перевіряли тільки зразки з позитивних сумішей.
У документації git є приклад: «Bisecting: 675 revisions left to test after this (roughly 10 steps)». Це той самий двійковий пошук: кожна відповідь «добре» чи «погано» відсікає половину комітів.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.