Комбинаторика на ММО: графы, турниры, логика, конструктивы

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

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

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

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

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

Покажем, что построение возможно. Покоординатную сумму строк и взятую по модулю будем обозначать как Рассмотрим строчки и Предположим, что тогда

Следовательно, правила построения таблицы можно переформулировать следующим образом:

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

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

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

Следовательно, такую таблицу можно построить.

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