Загадка 1 000 пробирок

Загадка о тысяче пробирок

Кавер-версия классической головоломки про 1 000 бутылок вина. Проверяет навыки алгоритмического мышления и очень распространена в ИТ-компаниях.

Так как чрезмерное употребление алкоголя вредит вашему здоровью, у нас будет задача про лекарства. Представьте, что вы работаете в лаборатории, которая ищет средство от смертельной болезни. Вам на испытание пришла партия из 1 000 пробирок с лекарством, которое нужно опробовать на людях. Проверка санкционирована Минздравом, у вас имеются все лицензии, но есть проблема. Вы узнаёте, что одну пробирку перепутали и по ошибке отправили вместо лекарства ядовитый реактив. Внешне он ничем не отличается от медикамента.

Вам нужно как можно скорее передать пробирки в больницы для запуска клинического теста, но отправлять отравленную пробирку нельзя: погибнут люди. Тесты всех пробирок займут месяцы, это очень долго. Но у вас есть лабораторные мыши. Вы знаете, что лекарство безвредно для них, а даже капля яда их убьёт за сутки. Но у вас только 10 мышей, а пробирок — 1 000.

Как определить, где яд, как можно быстрее? За какое время можно гарантированно найти пробирку с ядом?

Самопроверка

Прежде чем узнать решение, ответьте на такие вопросы:

  • Рационально ли выбирать какие-то отдельные бутылки из общей массы или нужно протестировать всё?
  • Есть ли в условии задачи лимит по количеству введённого лекарства?
  • Обязаны ли мы тестировать одну мышь только одной пробиркой? Можно ли использовать одно животное несколько раз или дать ему лекарства из нескольких пробирок?

Сначала кажется, что решить задачу нереально — мышей в 100 раз меньше, чем пробирок. Значит, нам нужно как-то научиться быстро сокращать количество элементов, которые нужно проверить.

Мы знаем, что даже капля яда убьёт мышь за сутки. Значит, если мы смешаем эту каплю с настоящим лекарством, яд тоже сработает. Воспользуемся этим так:

Разделим все пробирки на равные группы — по 100 пробирок в каждой.

В каждой группе возьмём по капле из каждой пробирки и смешаем их. Получим 10 смесей, одна из которых отравлена, и дадим каждой мыши свою смесь. Через сутки мы увидим, какой грызун погиб, и поймём, где конкретно был яд.

Теперь у нас осталось 100 пробирок и девять мышей. Видите, мы за сутки сократили количество пробирок в 10 раз. Будем использовать этот же приём и дальше: делить сосуды на равные группы и делать смеси. На второй день разделим 100 пробирок на девять групп :

Восемь групп по 11 пробирок и одна группа из 12 пробирок.

Как видите, на совсем равные части поделить не получилось, но это не критично — задача всё равно решается. Теперь даём смеси мышам и через сутки смотрим, какое животное погибнет на этот раз.

Предположим самый сложный случай — яд был в смеси из 12 пробирок. У нас остаётся восемь мышей и 12 пробирок. Их тоже делим на восемь групп:

Четыре группы по две пробирки, и четыре группы по одной пробирке.

Снова даём вещество мышам и через сутки смотрим на результат. Если погибла особь, которая пила только из одной пробирки, — то она и была отравлена, а значит, мы нашли яд за три дня. Если эта мышь дегустировала смесь из двух сосудов, то на следующий день мы берём эти две пробирки, две мыши из тех, что остались, и обеим даём попробовать своё лекарство. Через сутки мы тоже узнаем, где был яд.

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

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

На подумать

Чтобы решить эту задачу, нам нужен был циклический алгоритм. В первой части он делил оставшуюся пробу на порции по числу мышей, во второй снимал пробу и в третьей проверял, в какой пробе было лекарство. Кайф алгоритма в том, что его скорость исполнения нелинейна. Что это значит?

Допустим, у нас был бы бесконечный запас времени и те же 10 мышей. Мы даём каждой по одной капле из одной из пробирок в день. Если яд в районе тридцатой пробирки, мы узнаем об этом через три дня. Если в 1 000-й, то для поиска отравы потребуется 100 дней. Если бы сосудов было 10 тысяч, то понадобилось бы 1 000 дней. Время исполнения алгоритма растёт линейно: чем больше пробирок, тем больше дней.

Теперь посмотрим на наш алгоритм: чтобы проверить 1 000 пробирок, нужно четыре дня. Если бы образцов было 10 тысяч, потребовалось бы пять дней. Возрастание числа пробирок в 10 раз увеличило время исполнения только на 25%.

Это и есть нелинейная скорость выполнения. Представьте, насколько такие алгоритмы более эффективны на больших массивах данных.

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Объясни мне: как опубликовать свой сайт в интернете

Покупаем домен, оформляем хостинг, настраиваем привязку и заливаем файлы. Купаемся в лучах славы.

medium
Генератор паролей
Превращаем генератор паролей в настоящую программу

Настало время настоящего программирования — собираем приложение из исходников.

hard
Задача про соседских тараканов
Задача про соседских тараканов

Простая математика, но непростая логика. Проверьте, получится ли у вас.

easy
Задача: как успеть на презентацию

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

easy
Задачка: тревелблогеры на самолёте
Задачка: тревелблогеры на самолёте

Как им облететь вокруг Земли?

hard
Реально сложная задачка

Логика, математика и антисоциальное поведение.

hard
Задачка от Джеффа Безоса. На размышление даётся 30 секунд
Задачка от Джеффа Безоса. На размышление даётся 30 секунд

Считается, что её могут загадать на собеседовании в «Амазон».

hard
Тревелблогеры в пустыне

Математика против дешевых инстаграмных амбиций.

easy
Задача про персональные данные

Настоящая задача XXI века.

medium
Очень сложная задача про обруч
Очень сложная задача про обруч

Классическая математическая задачка, которая взрывает мозг.

easy
Задача про начальника транспортного цеха

Что быстрее — вспомнить формулы за 7 класс или написать программу для решения?

easy
Задача про тимлида и его новую команду

В этой задаче врут почти все.

medium
Школьная загадка про сейф, которая ставит в тупик большинство взрослых

Но не программистов.

hard
hard