Тысяча бутылок и десять индикаторов — разбор задачи

Условие

Среди $1000$ бутылок ровно одна содержит примесь. Есть $10$ одноразовых индикаторов: каждый через сутки покажет, была ли примесь хотя бы в одной нанесённой капле. Капли можно смешивать, чувствительность идеальна. Разрешён только один одновременный раунд. Как определить бутылку?

О задаче · Школьники и взрослые

Тема: Информация
Для кого: Школьники и взрослые
Уровень библиотеки: Продвинутый · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

У десяти индикаторов $2^{10}$ разных комбинаций ответов.

Подсказка 2

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

Разобрать решение по шагам

Пронумеруйте $0$ – $999$

Для каждого номера хватит десяти двоичных разрядов, потому что $2^{10}=1024$

Подготовьте смеси

На индикатор разряда $k$ нанесите капли из всех бутылок, где этот разряд равен $1$ Один образец может попасть на несколько индикаторов.

Прочитайте ответ

Сработавшие индикаторы составят двоичную запись испорченной бутылки. Если не сработал ни один, это № $0$ существование ровно одной плохой бутылки гарантировано.

Номер превращается в инструкцию

01№ 13двоичная запись 0000001101

021 + 4 + 8эти индикаторы получают каплю

030000001101обратное чтение даёт номер 13

Ответ

$10$ индикаторов, назначенных десяти двоичным разрядам.

Главная идея

Продуманное кодирование превращает поиск объекта в чтение его адреса.

Как заметить эту идею в другой задаче

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

Возможная ошибка

Разделить бутылки на десять непересекающихся групп: результат укажет лишь группу, а не бутылку.

Источник и примечания

Источник и редакция

Классическая задача. Формулировка, рисунки и разбор — Popov Academy.

Проверь себя

Какое минимальное число таких индикаторов нужно для $100$ бутылок?

Ответ к дополнительной задаче

Нужно $7$ индикаторов:

2^6=64<100\le128=2^7.

Шести двоичных результатов недостаточно, а семи хватит.

Продолжить тему: Поиск и алгоритмы →

Тема, знания и приёмы

Поиск и алгоритмы · Нужна школьная база

Степени двойки
Представление числа нулями и единицами

Приёмы решения: Последовательный подсчёт без повторов

Задать вопрос по задаче →

Условие

Пронумеруйте 000–999999999

Подготовьте смеси

Прочитайте ответ

Источник и редакция

Условие

Дополнительная задача

Пронумеруйте $0$ – $999$