Комбинаторика на ММО: графы, турниры, логика, конструктивы
Ошибка.
Попробуйте повторить позже
В лаборатории на полке стоят 
внешне неразличимых пробирок, в 
из которых находится нейтральное вещество, в одной — яд и в
одной — противоядие. Пробирки случайно перемешались, и нужно найти пробирку с ядом и пробирку с противоядием. Для этого
можно воспользоваться услугами внешней тестирующей лаборатории, в которую одновременно отправляют несколько
смесей жидкостей из любого числа пробирок (по одной капле из пробирки), и для каждой смеси лаборатория сообщит
результат:
если в смеси есть яд и нет противоядия;
если в смеси есть противоядие, но нет яда;
в остальных случаях.
Можно ли, подготовив 
таких смесей и послав их в лабораторию единой посылкой, по сообщённым результатам гарантированно
определить, в какой пробирке яд, а в какой противоядие?
Источники:
Подсказка 1
Попытаемся доказать в задаче положительный ответ. Если мы умеем находить пробирки с ядом и противоядием, то умеем находить две пробирки, отличающиеся от остальных. Оказывается, в терминах задачи можно смотреть на модуль присланного лабораторией числа и, основываясь на этих данных, найти нужные пробирки. Попробуйте с таким усилением решить задачу.
Подсказка 2
Поймите, при каких посылках в лабораторию вы сможете определить, где нейтральное вещество, а где нет. Для этого удобно рассматривать посылку как последовательность из 120 нулей и единиц, где единица означает, что пробирка с соответствующим номером отправилась на пробу. Поймите, как в терминах таких последовательностей отличать результаты лаборатории.
Подсказка 3
Поймите, что если покоординатная сумма строк с ядом и противоядием, взятая по модулю 2, совпадает с результатом лаборатории, то какие тогда должны быть условия на 19 посылок? Достаточно найти 19 различных слов длины 120, чтобы суммы всех возможных пар строк, взятые по модулю 2, были различны. Почему такие строки найдутся? Как после всех результатов всё-таки определить, где был яд, а где — противоядие?
Для описания отправляемых в лабораторию смесей составим таблицу, состоящую из 
строк и 
столбцов. Каждый столбец таблицы —
это описание состава смеси, отправляемой в лабораторию. На пересечении 
-й строки и 
-го столбца стоит единица, если 
-я смесь
содержит жидкость из 
-й пробирки, и ноль в противном случае.
Сначала попробуем найти пару пробирок с ядом и противоядием, не устанавливая, где в этой паре яд, а где противоядие.
Для этого огрубим результат лаборатории, убрав из него знак (то есть будем считать, что для каждой смеси лаборатория
сообщает результат 
если в смеси есть яд без противоядия или противоядие без яда, и ноль иначе). Pacсмотрим две
строки, соответствующие пробиркам с ядом и противоядием. Их покоординатная сумма, взятая по модулю 
совпадает со
строкой результатов, присланных лабораторией. Следовательно, если все суммы пар строк таблицы, взятые по модулю 
будут попарно различны, то в результате тестирования мы сможем определить номера строк, соответствующих яду и
противоядию.
Такую таблицу можно построить следующим образом. Первую ее строку заполним произвольно. Вторую строку заполняем так, чтобы она не совпадала с первой. Третья и все последующие строки должны удовлетворять двум условиям:
- новая строка не должна совпадать с уже заполненными;
- новая строка должна быть такой, чтобы суммы всех возможных пар построенных строк, взятые по модулю 
были
различны.
Покажем, что построение возможно. Покоординатную сумму строк 
и 
взятую по модулю 
будем обозначать как 
Рассмотрим строчки 
и 
Предположим, что 
тогда
Следовательно, правила построения таблицы можно переформулировать следующим образом:
- новая строка не должна совпадать с уже заполненными;
- новая строка должна быть такой, чтобы она была отлична от всех возможных сумм троек уже построенных строк.
Число строк длины 
составленных из нулей и единиц, равно 
Запретов, даже после заполнения
всех 
строк, будет не более чем
Следовательно, такую таблицу можно построить.
Чтобы определить пару пробирок с ядом и противоядием, найдем все попарные суммы строк таблицы, взятые по модулю 
Найдем
такие строки 
и 
что 
совпадает с огрубленным результатом лаборатории. Пробирки, соответствующие строкам 
и 
содержат яд и противоядие. Далее, рассматривая уже настоящий результат лаборатории, мы сможем точно сказать, в какой
пробирке яд, a в какой противоядие. Действительно, обязательно найдется хотя бы одна смесь, содержащая либо только яд,
либо только противоядие, иначе строки таблицы, соответствующие пробирке с ядом и пробирке с противоядием, будут
одинаковыми, что запрещено построением. Тогда по знаку результата для этой смеси мы сможем определить, был в ней яд или
противоядие.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
