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

На кухне отеля на столе стояли в ряд частично наполненные стаканы, что-то между одной и двумя сотнями штук. Только в одном из них был яд, и нам необходимо узнать, в котором именно, прежде чем мы начнем снимать отпечатки пальцев. Лаборатория может проверить жидкость в каждом стакане, однако проверка требует времени и денег, и, естественно, необходимо сократить число таких проверок до минимума. Оказавшийся неподалеку профессора математики подсчитал стаканы, улыбнулся и сказал:
- Возьмите любой стакан, и исследуйте его первым.
- Но не растратим ли мы впустую одно испытание? - возразили детективы.
- Не полностью одно - и мне хотелось бы рискнуть, - сказал профессор, - Это составляет часть оптимальной процедуры. Мы можем сперва исследовать один стакан, неважно, какой именно.
Чему равнялось точное число стаканов? (предполагается, что мы можем исследовать одновременно содержимое любого числа стаканов, взяв небольшое число жидкости из каждого из них и смешав эти порции вместе)

Ответ

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

Обычная, наиболее эффективная процедура состоит в том, чтобы исследовать сразу половину стаканов, затем половину стаканов из той группы, где обнаружен яд, затем половину от половины и т. д. до тех пор, пока мы не найдем нужный стакан. Таким образом, степени 2 дают нам первый ключ: для двух стаканов потребуется одна проверка, для трех или четырех - две проверки; для пяти или шести - три проверки ит. д. Число 128 - это единственная степень двойки, расположенная между 100 и 200, так что для 129 и большего числа стаканов нам потребуется 8 испытаний. Точнее говоря, нам могло бы потребоваться 8, но, проверив сначала 1 стакан, мы оставим себе 7 испытаний для оставшихся 128 стаканов, что дает ту же оценку 8 для максимального числа испытаний. В действительности в случае первой процедуры математическое ожидание числа испытаний равно 7,0155..., в то время как во втором случае оно равно 7,9457... Так что, прибегая ко второй процедуре, мы "растрачиваем" 0,930... испытания (<не полностью одно> испытание, как сказал профессор). Его риск оправдался, ибо именно первый стакан оказался отравленным, что укрепило доверие работников лаборатории к ученому настолько, что во всех дальнейших случаях он мог действовать, как считал нужным.

О задаче

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

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

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

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

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

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

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