Задача 352
Тесты крови

Каждую 25-ю овцу из стада необходимо проверить на редкий вирус, который поражает 2% популяции овец. Существует точный и высокочувствительный ПЦР тест образцов крови, который дает однозначный положительный/отрицательный результат, но он дорогой и очень затратный по времени.

Из-за высокой цены, главный ветеринар предлагает вместо 25 отдельных тестов проводить следующую процедуру:

Овец распределяют на 5 груп по 5 овец в каждой. 5 образцов крови каждой овцы из группы смешиваются вместе, после чего проводится один тест. Тогда,

  • Если результат отрицательный, то все овцы в этой группе считаются здоровыми.
  • Если результат положительный, проводится 5 дополнительных тестов. Отдельный тест для образца крови каждого животного, чтобы определить зараженных особей.

Поскольку вероятность заражения каждого отдельно взятого животного составляет всего 0.02, то первый тест (объединенных образцов) для каждой группы будет:

  • Отрицательным (и больше тестов не потребуется) с вероятностью 0.985 = 0.9039207968.
  • Положительным (потребуется 5 дополнительных тестов) с вероятностью 1 - 0.9039207968 = 0.0960792032.

Таким образом, ожидаемое количество тестов для каждой группы составвит 1 + 0.0960792032 × 5 = 1.480396016.
Следовательно, все 5 групп можно просеять со средним количеством тестов 1.480396016 × 5 = 7.40198008, что дает огромный выигрыш, более чем 70% !

Хотя описанная выше процедура выглядит очень эффективной, ее можно существенно улучшить (всегда предполагается, что тест достаточно чувствителен и что нет никаких побочных эффектов при смешивании образцов крови). К примеру:

  • Можно начать с теста смеси всех 25 образцов крови. Можно убедиться, что примерно в 60.35% случаев тест будет отрицательным и дополнительные тесты не потребуются. Более подробное тестирование потребуется лишь в оставшихся 39.65% случаев.
  • Если известно, что по крайней мере одно из животных в группе из 5 особей инфицировано, и что первые 4 индивидуальных теста дадут отрицательный результат, то совершенно не требуется проводить тест для пятого животного (очевидно, что именно оно и будет инфицировано).
  • Можно попробовать изменить количество групп / количество особей в группе, меняя эти числа на каждом уровне так, чтобы общее число проведенных тестов было минимальным.

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

В данном примере оказывается, что наиболее эффективная по затратам методика тестирования (будем называть ее оптимальной стратегией) потребует в среднем всего лишь 4.155452 тестов!

Для такой оптимальной стратегии определим T(s,p) как среднее количество тестов, необходимое для отсеивания больных животных в стаде из s овец, при вероятности заболевания каждой особи p.
Таким образом, округлив результат до шести знаков после десятичной точки, T(25,0.02) = 4.155452 и T(25,0.10) = 12.702124.

Найдите ΣT(10000,p) для всех p=0.01, 0.02, 0.03, ... 0.50.
Ответ округлите до шести знаков после десятичной точки.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net