Пробы крови

*

Сложность: 

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

Подсказка

Если вы желаете угадать задуманное кем-то число за наименьшее число вопросов, задавая вопросы, предполагающие лишь ответы «да» или «нет», то самое лучшее — всякий раз делить множество, в которое оно входит, пополам. Так, например, если задумано какое-то число от 1 до 16, то угадать его наверняка можно за 4 вопроса и, вообще говоря, быстрее нельзя.

Решение

За 7 анализов можно найти заражённую пробу, если изначально было от 26 + 1 = 65 до 27 = 128 проб. Если бы число проб было более 129, то исследование на первом шаге 1-й пробы было бы нерациональным, так как (в случае отрицательного результата) осталось бы после этого по-прежнему более 128 неисследованных проб, а значит, число оставшихся анализов будет более 7. Поскольку, по мнению профессора, исследование на первом шаге одной любой пробы не меняет оптимальности процедуры, то число исследуемых проб равно 129.




Комментарии

You've really imsrseped me with that answer!

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

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.