Детективная история.

В отеле, во время вечеринки, произошло отравление. Полиции необходимо как можно скорее отыскать бокал с отравленным напитком. Предполагается, что содержимое любой группы бокалов можно анализировать одновременно. Для этого из каждого бокала берется проба, все пробы смешиваются, и проводится один общий анализ получившейся смеси.Всех бокалов, примерно, от 100 до 200 штук.Прибывший эксперт пересчитал бокалы и предложил провести экспертизу первого попавшегося одного бокала.При этом он утверждал, что это приведет к быстрейшему установлению истины. Назовете точное число бокалов на вечеринке?

Ответ

Решение задачи

Установить, какой из множества бокалов седержит яд, быстрее всего можно с помощью так называемой дихотомии - последовательное деление целого на две части, затем каждой из них снова на две части и т.д. Разделим бокалы (их всего n) на две группь Если n четно, то в каждой из групп должно быть по n/2 бокалов. Если же n нечетно, то в одной группе должно быть (n+1)/2 бокалов, а в другой (n-1)/2 бокалов. Отобрав пробы из всех бокалов одной группы, мы сливаем их вместе и проводим анализ. По результатам анализа мы судим, в какой из двух групп находите бокал с ядом. Затем мы повторяем всю процедуру, сузив, таким образом, поле поисков примерно вдвое (при четном n - ровн вдвое). Если число бокалов заключено между 100 и 128, для установления бокала с ядом необходимо произвести всего семь разбиений на группы (и соответственно семь анализов). Если число бокалов заключено между 129 и 200, то для установления бокала с ядом необходимо произвести восемь анализов. Таким образом, бокалов должно было быть 128+1=129, ибо лишь в этом случае анализ содержимого одного бокала не уменьшает эффективность процедуры установлению истины. Действительно, при отыскании бокала с ядом среди 129 бокалов по методу дихотомии требуется провести 8 анализов. Те же 8 анализов нам придется провести, если мы сначала проверим содержимое одного бокала, а затем применим дихотомию к 128 бокалам (на что уйдет еще 7 анализов).

О задаче

Похожие задачи

Скачать задачу

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

Оставить комментарий

Свои вопросы, комментарии, замечания и занимательные задачи присылайте через предложенную ниже форму.

Занимательные задачи

Ещё больше занимательных задач собрано в следующих разделах: