Определение яда и противоядия: сложная задача из теории алгоритмов

Для описания отправляемых в лабораторию смесей составим таблицу, состоящую из 120 строк и 19 столбцов. Каждый столбец таблицы – это описание состава смеси, отправляемой в лабораторию. На пересечении $i$-й строки и $j$-го столбца стоит единица, если $j$-я смесь содержит жидкость из $i$-й пробирки, и ноль в противном случае.

Сначала попробуем найти пару пробирок с ядом и противоядием, не устанавливая, где в этой паре яд, а где противоядие. Для этого огрубим результат лаборатории, убрав из него знак (то есть будем считать, что для каждой смеси лаборатория сообщает результат $+1$, если в смеси есть яд без противоядия или противоядие без яда, и ноль иначе). Рассмотрим две строки, соответствующие пробиркам с ядом и противоядием. Их покоординатная сумма, взятая по модулю 2, совпадает со строкой результатов, присланных лабораторией. Следовательно, если все суммы пар строк таблицы, взятые по модулю 2, будут попарно различны, то в результате тестирования мы сможем определить номера строк, соответствующих яду и противоядию.

Такую таблицу можно построить следующим образом. Первую ее строку заполним произвольно. Вторую строку заполняем так, чтобы она не совпадала с первой. Третья и все последующие строки должны удовлетворять двум условиям:

1. новая строка не должна совпадать с уже заполненными;

2. новая строка должна быть такой, чтобы суммы всех возможных пар построенных строк, взятые по модулю 2, были различны.

Покажем, что построение возможно. Покоординатную сумму строк $a$ и $b$, взятую по модулю 2, будем обозначать как $a\oplus b$. Рассмотрим строчки $s_1, s_2, s_3$ и $s_4$. Предположим, что $s_1\oplus s_2=s_3\oplus s_4$, тогда $s_1\oplus s_2\oplus s_3 = s_3\oplus s_3\oplus s_4=s_4$. Следовательно, правила построения таблицы можно переформулировать следующим образом:

1. новая строка не должна совпадать с уже заполненными;

2. новая строка должна быть такой, чтобы она была отлична от всех возможных сумм троек уже построенных строк.

Число строк длины 19, составленных из нулей и единиц, равно $2^{19} = 2^{10} \cdot 2^9 > 1000 \cdot 500 = 500 000$. Запретов, даже после заполнения всех 120 строк, будет не более чем $C^3_{120} + 120 = \frac{120\cdot119\cdot118}{6} + 120 < 20\cdot 120 \cdot 120 + 120 = 288 120 < 300 000$. Следовательно, такую таблицу можно построить.

Чтобы определить пару пробирок с ядом и противоядием, найдем все попарные суммы строк таблицы, взятые по модулю 2. Найдем такие строки $s_1$ и $s_2$, что $s_1\oplus s_2$ совпадает с огрубленным результатом лаборатории. Пробирки, соответствующие строкам $s_1$ и $s_2$, содержат яд и противоядие. Далее, рассматривая уже настоящий результат лаборатории, мы сможем точно сказать, в какой пробирке яд, а в какой противоядие. Действительно, обязательно найдется хотя бы одна смесь, содержащая либо только яд, либо только противоядие, иначе строки таблицы, соответствующие пробирке с ядом и пробирке с противоядием, будут одинаковыми, что запрещено построением. Тогда по знаку результата для этой смеси мы сможем определить, был в ней яд или противоядие.