Высшая проба 2026, 9 класс, задача 6
( балл) В лаборатории есть пробирок. В одной из них - бесцветный химикат, а в остальных - вода. Требуется определить, в какой из пробирок находится химикат. Для этого можно приготовить несколько смесей жидкостей из пробирок и отправить на экспертизу, которая для каждой смеси покажет, содержится ли в ней хотя бы химиката, или нет. Какое наименьшее количество смесей надо единовременно отправить на экспертизу, чтобы по её результатам точно узнать, в какой из пробирок химикат?
Ответ
Ответ. .
Решение. Оценка. Заметим, что если некоторая смесь менее, чем на состоит из содержимого одной из пробирок, результат будет одинаковым вне зависимости от того, был ли в соответствующей пробирке химикат. Значит, содержимое всех таких пробирок можно убрать из смеси, и результат это никак не изменит (так как процентное содержание содержимого каждой из пробирок только увеличится), а если содержимое любой из пробирок в смеси составляет менее , то такую смесь можно вообще не отправлять на экспертизу, ведь результат для нее точно будет отрицательный.
Получаем, что если некоторый набор смесей позволяет определить, в какой из пробирок химикат, то найдется и такой набор, в котором в каждой смеси содержимое любой из пробирок составляет не менее (а значит, в каждой смеси содержимое не более пробирок), при этом тоже позволяющий определить, в какой из пробирок химикат. В связи с этим, в дальнейшем будем рассматривать только смеси, в которых есть содержимое не более пробирок.
Пронумеруем смеси и для каждой пробирки запишем, в какие смеси вошло ее содержимое. Заметим, что для всех пробирок множество записанных номеров должно быть уникальным, ведь в противном случае результат экспертизы не сможет отличить пару пробирок с совпадающими множествами.
Пусть всего будет приготовлено смесей. Тогда ни в одну смесь можно будет не добавлять только одну пробирку, добавить в одну смесь можно будет не более , а остальные пробирки надо будет добавить хотя бы в две смеси. Таким образом, суммарное количество записанных номеров смесей для каждой из пробирок будет не менее . С другой стороны, в каждой смеси есть жидкости из не более, чем пробирок, поэтому записанных номеров будет не более . Получаем, что , откуда смесей будет не менее .
Пример. Покажем, как обойтись ровно двадцатью смесями. Запишем номера всех ста пробирок в таблицу.
В первые смесей включим содержимое первых строк таблицы, в следующие - содержимое первых столбцов таблицы.
Если экспертиза покажет наличие химиката только в одной из первых смесей, то искомая пробирка находится на пересечении строки, соответствующей смеси, для которой результат положительный, и последнего столбца. Если экспертиза покажет наличие химиката только в одной из смесей из второго десятка, то искомая пробирка находится на пересечении столбца, соответствующего этой смеси, и последней строки. Если же химикат окажется в двух смесях, то номер искомой пробирки будет находиться на пересечении строки и столбца, соответствующих смесям с положительным результатом