|
|
 |
Условие
В лаборатории на полке стоят 120 внешне неразличимых пробирок, в 118 из которых находится нейтральное вещество, в одной – яд и в одной – противоядие. Пробирки случайно перемешались, и нужно найти пробирку с ядом и пробирку с противоядием. Для этого можно воспользоваться услугами внешней тестирующей лаборатории, в которую одновременно отправляют несколько смесей жидкостей из любого числа пробирок (по одной капле из пробирки), и для каждой смеси лаборатория сообщит результат: +1, если в смеси есть яд и нет противоядия; −1, если в смеси есть противоядие, но нет яда; 0 в остальных случаях.
Можно ли, подготовив 19 таких смесей и послав их в лабораторию единой посылкой, по сообщенным результатам гарантированно определить, в какой пробирке яд, а в какой противоядие?
Решение
Для описания отправляемых в лабораторию смесей составим таблицу, состоящую из 120 строк и 19 столбцов. Каждый столбец таблицы – это описание состава смеси, отправляемой в лабораторию. На пересечении i-й строки и j-го столбца стоит единица, если j-я смесь содержит жидкость из i-й пробирки, и ноль в противном случае.
Сначала попробуем найти пару пробирок с ядом и противоядием, не устанавливая, где в этой паре яд, а где противоядие. Для этого огрубим результат лаборатории, убрав из него знак (то есть будем считать, что для каждой смеси лаборатория сообщает результат +1, если в смеси есть яд без противоядия или противоядие без яда, и ноль иначе). Рассмотрим две строки, соответствующие пробиркам с ядом и противоядием. Их покоординатная сумма, взятая по модулю 2, совпадает со строкой результатов, присланных лабораторией. Следовательно, если все суммы пар строк таблицы, взятые по модулю 2, будут попарно различны, то в результате тестирования мы сможем определить номера строк, соответствующих яду и противоядию.
Такую таблицу можно построить следующим образом. Первую ее строку заполним произвольно. Вторую строку заполняем так, чтобы она не совпадала с первой. Третья и все последующие строки должны удовлетворять двум условиям:
1) новая строка не должна совпадать с уже заполненными;
2) новая строка должна быть такой, чтобы суммы всех возможных пар построенных строк, взятые по модулю 2, были различны.
Покажем, что построение возможно. Покоординатную сумму строк a и b, взятую по модулю 2, будем обозначать как a⊕b. Рассмотрим строчки s1,s2,s3 и s4. Предположим, что s1⊕s2=s3⊕s4, тогда s1⊕s2⊕s3=s3⊕s3⊕s4=s4. Следовательно, правила построения таблицы можно переформулировать следующим образом:
1) новая строка не должна совпадать с уже заполненными;
2) новая строка должна быть такой, чтобы она была отлична от всех возможных сумм троек уже построенных строк.
Число строк длины 19, составленных из нулей и единиц, равно 219=210⋅29>1000⋅500=500000. Запретов, даже после заполнения всех 120 строк, будет не более чем C3120+120=120⋅119⋅1186+120<20⋅120⋅120+120=288120<300000. Следовательно, такую таблицу можно построить.
Чтобы определить пару пробирок с ядом и противоядием, найдем все попарные суммы строк таблицы, взятые по модулю 2. Найдем такие строки s1 и s2, что s1⊕s2 совпадает с огрубленным результатом лаборатории. Пробирки, соответствующие строкам s1 и s2, содержат яд и противоядие. Далее, рассматривая уже настоящий результат лаборатории, мы сможем точно сказать, в какой пробирке яд, а в какой противоядие. Действительно, обязательно найдется хотя бы одна смесь, содержащая либо только яд, либо только противоядие, иначе строки таблицы, соответствующие пробирке с ядом и пробирке с противоядием, будут одинаковыми, что запрещено построением. Тогда по знаку результата для этой смеси мы сможем определить, был в ней яд или противоядие.
Ответ
Да, можно.
