Problem 352 の編集

*[[Problem 352:http://projecteuler.net/problem=352]] 「血液検査」 [#m20037e3]

25頭の羊それぞれに, 羊の個体数のうち2%に感染することで知られる希少なウイルスの検査を行うことになった. 血液サンプルを使用する正確で超高感度なPCR(ポリメラーゼ連鎖反応法)検査があり, 明確に陰性, 陽性を判定してくれる. しかし, この検査は非常に時間と費用がかかる.

高コストを理由に, 担当の獣医は25頭それぞれを検査するのではなく, 代わりに以下の手続きで行うことを勧めた :

羊を5頭ずつの5グループに分ける. それぞれのグループ5頭分の血液サンプルを混合し, 検査を1回行う. それから,

- もし結果が陰性なら, そのグループの羊すべてがウイルスに感染していないとみなす.
- もし結果が陽性なら, 感染している個体(複数の場合もある)を識別するために(それぞれ個別に)5回の追加検査を行う.

感染している確率は0.02なので, グループそれぞれの(混合サンプルにおいての)最初の検査は以下のようになる :

- 陰性(追加検査が不要)の確率 0.98&sup{5}; = 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頭のグループのうち少なくとも1頭の動物が感染していることがわかっており, 4頭の個体検査を行った結果が陰性だった場合, 5頭目の検査は(感染していることがわかったので)行う必要がない.
-検査の期待回数の総計が一番少なくなるように, それぞれの段階で, グループの数を変えたり, またはそれぞれのグループの頭数を変えたりして調節できる.

可能性が非常に多岐にわたるのを簡単にするため, 最もコスト効率の高い検査計画を考えるうえで一つの制約を課すこととする：混合したサンプルから始めたとき, このサンプルに関わる羊が完全にふるい分けされる（つまり全ての羊についてウィルスに感染しているかいないかが判明する）まで, 他の羊の調査を始めてはならない.

今の例では, 最もコスト効率の高い検査計画(これを「最適戦略」と呼ぼう)は平均でたったの ''4.155452'' 回の検査で済む！

最適戦略を使って, ウイルスに確率 &tex{p}; で感染した個体が &tex{s}; 頭いる羊の群れをふるい分けするのに必要な平均検査回数とT(&tex{s,p};)としよう.
小数点以下7桁の位で四捨五入すると T(25, 0.02) = 4.155452, T(25, 0.10) = 12.702124 となる.

p=0.01, 0.02, 0.03, ... 0.50 のときの ΣT(10000,p) を求めよ. ~
小数点以下7桁の位で四捨五入して回答すること.

タイムスタンプを変更しない