МОШ 2021, 11 класс, задача 5
В лаборатории есть пробирок с жидкостями. В одной из них находится яд, а в другой — противоядие. Если в смесь попал яд, но не попало противоядие, она становится ядовитой, если противоядие, но не яд — целебной, а если попали и яд, и противоядие или ни то, ни другое — нейтральной. Можно ли, отправив в лабораторию смесей, каждая из которых состоит из нескольких исходных жидкостей, гарантированно определить, в какой пробирке находится яд, а в какой — противоядие?
(А. Шаповалов)
Ответ
Ответ: да.
Решение. Для описания отправляемых в лабораторию смесей составим таблицу, состоящую из строк и столбцов. Каждый столбец таблицы — это описание состава смеси, отправляемой в лабораторию. На пересечении -ой строки и -го столбца стоит единица, если -я смесь содержит жидкость из -й пробирки, и ноль в противном случае.
Сначала попробуем найти пару пробирок с ядом и противоядием, не устанавливая, где в этой паре яд, а где противоядие. Для этого огрубим результат лаборатории, убрав из него знак (то есть будем считать, что для каждой смеси лаборатория сообщает результат , если в смеси есть яд без противоядия или противоядие без яда, и ноль иначе). Рассмотрим две строки, соответствующие пробиркам с ядом и противоядием. Их покоординатная сумма, взятая по модулю , совпадает со строкой результатов, присланных лабораторией. Следовательно, если все суммы пар строк таблицы, взятые по модулю , будут попарно различны, то в результате тестирования мы сможем определить номера строк, соответствующих яду и противоядию.
Такую таблицу можно построить следующим образом. Первую её строку заполним произвольно. Вторую строку заполняем так, чтобы она не совпадала с первой. Третья и все последующие строки должны удовлетворять двум условиям:
- новая строка не должна совпадать с уже заполненными;
- новая строка должна быть такой, чтобы суммы всех возможных пар построенных строк, взятые по модулю , были различны.
Покажем, что построение возможно. Покоординатную сумму строк и , взятую по модулю , будем обозначать как . Рассмотрим строчки , , и . Предположим, что , тогда
Следовательно, правила построения таблицы можно переформулировать следующим образом:
- новая строка не должна совпадать с уже заполненными;
- новая строка должна быть такой, чтобы она была отлична от всех возможных сумм троек уже построенных строк.
Число строк длины , составленных из нулей и единиц, равно
Запретов, даже после заполнения всех строк, будет не более чем
Следовательно, такую таблицу можно построить.
Чтобы определить пару пробирок с ядом и противоядием, найдём все попарные суммы строк таблицы, взятые по модулю . Найдём такие строки и , что совпадает с огрублённым результатом лаборатории. Пробирки, соответствующие строкам и , содержат яд и противоядие.
Далее, рассматривая уже настоящий результат лаборатории, мы сможем точно сказать, в какой пробирке яд, а в какой противоядие. Действительно, обязательно найдётся хотя бы одна смесь, содержащая либо только яд, либо только противоядие, иначе строки таблицы, соответствующие пробирке с ядом и пробирке с противоядием, будут одинаковыми, что запрещено построением. Тогда по знаку результата для этой смеси мы сможем определить, был в ней яд или противоядие.