Отравленный стакан

Cтранные люди, эти математики — сказал однажды полицейский жене.

отравленный стаканНа столе у нас стояли в ряд несколько заполненных жидкостью стаканов, и в одном из них был яд. Нам нужно было узнать, в каком именно, чтобы потом снять отпечатки пальцев. Мы могли бы сделать это в нашей лаборатории. Проверив жидкости в каждом стакане отдельно, но это куча времени и денег. Поэтому нужно было каким-то способом сократить чисто тестов. Профессор математики согласился нам помочь. Сначала он пересчитал стаканы и сказал:

—  Выбирайте любой из них. Проверим его.

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

— А сколько было всех стаканов? — спросила жена полицейского.

— Ну где-то между 100 и 200.

Так сколько же стаканов было точно? (Предположим, что любую группу стаканов можно анализировать одновременно, забирая малое количество жидкости из каждого, смешивая образцы и проводя одно исследование.)

Ответ: Вот как выглядел первоначальный ответ на эту задачу. При анализе жидкого содержимого любого количества стаканов с целью поиска одного-единственного стакана с ядом наиболее эффективен бинарный подход. Имеющиеся стаканы делятся примерно пополам. Проверяется одна группа стаканов (при этом смешиваются пробы из всех стаканов в группе и проверяются за один раз). Та группа, в которой обнаруживают яд, делится пополам и процедура повторяется, пока отравленный стакан не находят. Если стаканов от 100 до 128, то требуется семь тестов. Если от 129 до 200 — то восемь тестов. Цифра 128 поворотная, потому что она единственная в интервале 100-200 из ряда удвоения 1, 2,4, 8, 16, 32, 64, 128, 256 и т. д. Надо полагать, что в гостинице было 129 стаканов, потому что только в этом случае (а нам был задан диапазон 100-200) нас отделяет от возможности проведения наиболее эффективной процедуры только один стакан. Проверка 129 стаканов по такой процедуре потребует восьми тестов. Но если сначала проверить один стакан, то оставшиеся 128 стаканов потребуют не более семи тестов, так что общее количество тестов не меняется.

Если обратиться к теории вероятности, то ожидаемое количество испытаний для 129 стаканов составляет 7,0155. Если же вы проверите вначале один стакан, то ожидаемое количество испытаний составит 7,9457. Количество испытаний получается больше, так что комиссар полиции был прав относительно того, что предложение математика расточительно. Однако в случае с 129 стаканами эта ошибка будет простительной.

Материалы по теме:
Поделиться с друзьями:
Оцените материал:
1 Star2 Stars3 Stars4 Stars5 Stars (Проголосуйте первым!)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *