|
|
логическая задача, задача на четность
Детективная история.
В отеле, во время вечеринки, произошло отравление. Полиции необходимо как можно скорее отыскать бокал с отравленным напитком. Предполагается, что содержимое любой группы бокалов можно анализировать одновременно. Для этого из каждого бокала берется проба, все пробы смешиваются, и проводится один общий анализ получившейся смеси.Всех бокалов, примерно, от 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 анализов).
О задаче
- Категория: Логические задачи, Четность,
- Степень сложности: сложная.
- Ключевые слова: 100, 200, бокал, вечеринка, гостиница, отель,
- Источник: Математические новеллы, Россыпи головоломок,
Похожие задачи
Список похожих занимательных задач:
Оставить комментарий
Свои вопросы, комментарии, замечания и занимательные задачи присылайте через предложенную ниже форму.
Занимательные задачи
Ещё больше занимательных задач собрано в следующих разделах:
 Задачи по географии |
 Задачи по физике |
 Задачи на движение |
 Задачи на вероятность |
 Задачи про возраст |
 Задачи с часами |
|
|
|
|
|
| Энциклопедия занимательных задач | SirotaSOFT © 2021 - 2025 |