АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЭЮЯ#
§🔍YouTube канал Занимательные задачи

zadach.net YouTube канал Занимательные задачи

логическая задача, задача на четность

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

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

Ответ

129

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

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

О задаче

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

Список похожих занимательных задач:

◄ На предыдущую страницу

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

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

Имя: Почта:
Сообщение:

Проверочный код: 2+2×2=   

Решите задачу

Сколько будет если разделить 1 рубль на 1/5.

a) 2 рубля.
b) 20 копеек.
c) 5 рублей.
d) 25 копеек.

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

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

Задачи по географии
Задачи по географии
Задачи по физике
Задачи по физике
Задачи на движение
Задачи на движение
Задачи на вероятность
Задачи на вероятность
Задачи про возраст
Задачи про возраст
Задачи с часами
Задачи с часами


Учительский портал

Энциклопедия занимательных задачSirotaSOFT © 2021 - 2025