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

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

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

• もし結果が陰性なら, そのグループの羊すべてがウイルスに感染していないとみなす.

• もし結果が陽性なら, 感染している個体(複数の場合もある)を識別するために(それぞれ個別に)5回の追加検査を行う.

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

• 陰性(追加検査が不要)の確率 $0.98^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 回の検査で済む！

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

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

次数 n の六角形果樹園(hexagonal orchard)は, 辺の長さ n の正六角形状に配置された三角形格子と定義される. 次数5の六角形果樹園の例を以下に示す :

緑色で強調された部分は, 中心から見たときにより近くの点によって隠されてしまう点を示している. 上記の次数5の六角形果樹園の場合, 中心から見て30個の点が隠されることがわかるだろう.

次数 n の六角形果樹園において中心から隠される点の個数を H(n) としよう. 以下に例を示す.

H(5) = 30. H(10) = 138. H(1 000) = 1177848.

H(100 000 000)を求めよ.

集合 {1,2, ..., n} から, 「任意の二つの要素の組がすべて互いに素となる(mutually co-prime)」集合を, 要素の合計が最大になるように選んだとき, その合計を Co(n) と定義する.

例えば, Co(10) の値は 30 となり, 最大となる部分集合は {1, 5, 7, 8, 9} となる.

Co(30) = 193, ならびに Co(100) = 1356 がすでに与えられている.

Co(200000) を求めよ.

n 桁の巡回数はとても興味深い特性を持っている : 1,2,3,4, ... n で乗算すると, すべての積が同じ桁数になり, 同じ順番で現れ, しかも輪状に回転している！

最小の巡回数は6桁の数 142857 である :

142857 × 1 = 142857 142857 × 2 = 285714 142857 × 3 = 428571 142857 × 4 = 571428 142857 × 5 = 714285 142857 × 6 = 857142

次の巡回数は16桁の数 0588235294117647 である :

0588235294117647 × 1 = 0588235294117647 0588235294117647 × 2 = 1176470588235294 0588235294117647 × 3 = 1764705882352941 ... 0588235294117647 × 16 = 9411764705882352

巡回数について留意すべきこととして, 先行ゼロ(数の先頭につくゼロ)が重要である.

最左からの11桁が 00000000137, 最右からの5桁が 56789 となる巡回数が唯一存在する. (すなわち, 内部の桁が明かされていない 00000000137...56789 という形をもつ) この数のすべての桁の合計を求めよ.

30の約数について考えよう : 1,2,3,5,6,10,15,30. 30の約数$d$は, そのすべてにおいて$d+30/d$の値が素数になる.

$n$のすべての約数$d$について$d+n/d$が素数になるような, 100 000 000 以下の正の整数$n$の合計を求めよ.

月を中心$(0,0,0)$、半径$r$の球$C(r)$として表そう。

月面上、すなわち$C(r)$の表面で整数座標の位置には月面基地がある。座標$(0,0,r)$にあるものを北極基地、座標$(0,0,-r)$にあるものを南極基地と呼ぼう。

すべての基地は、他の基地と互いに最短最短距離となる道路で結ばれている。それは両基地を通る大圏コース上にある。基地間の旅行は危険をともなう。2基地間の距離が$d$ならば、旅行のリスク測度は$(\frac{d}{\pi r})^2$となる（これをその道路のリスクと呼ぼう）。旅行が3基地以上からなる場合、利用する道路のリスクの合計がその旅行のリスクとなる。

北極基地から南極基地へ直接旅行すると距離は$\pi r$となりリスクは1になる。北極基地から南極基地へ、$(0,r,0)$にある基地を経由して旅行すると、距離は同じだがリスクは小さくなる：

$\displaystyle \big (\frac{\frac{1}{2} \pi r}{\pi r} \big )^2 + \big (\frac{\frac{1}{2} \pi r}{\pi r} \big )^2 = 0.5$

月$C(r)$での北極基地から南極基地への旅行にともなう最小リスクを$M(r)$としよう。

小数点以下11桁で四捨五入すると$M(7)=0.1784943998$となる。

$\displaystyle \sum_{n=1}^{15} M(2^n-1)$を求めよ。

小数点以下11桁で四捨五入し a.bcdefghijk の形式で回答せよ。

ヒルベルトの最新の無限ホテルに, 無限数の客(1,2,3,...と番号付けされている)が客室を取ろうと列をなしている. そのホテルは無限数のフロア(1,2,3,...と番号付けされている)を有し, またそれぞれのフロアは無限の客室(1,2,3,...と番号付けされている)を持つ.

当初, ホテルはすべて空室である. ヒルベルトは客 n への客室の割り当て方を次のように発表する :

n 番目の客は, 以下の条件のどちらかをみたす一番最小の数のフロアについて, 最初の(訳注:その時点で最小の数となる)空いている客室を取る.

• そのフロアに客が誰もいないとき

• そのフロアに先客がおり、直前にそのフロアの客室を取った客が m で, m + n が完全平方数のとき

客 1 は, フロア 1 が空きなので, フロア 1 の客室 1 を取る. 客 2 は, 1 + 2 = 3 が完全平方数でないので, フロア 1 の客室 2 は取れない. 代わりに客 2 は, フロア2が空きなので, フロア 2 の客室 1 を取る. 客 3 は, 1 + 3 = 4 が完全平方数なので, フロア 1 の客室 2 を取る.

最終的には, 列にいたすべての客がホテルの客室を取ることができる.

関数を、フロアの客室に客が泊まっている場合は、誰もその客室に泊まっていないときは 0 を返すと定義しよう。以下に例を示す : P(1, 1) = 1 P(1, 2) = 3 P(2, 1) = 2 P(10, 20) = 440 P(25, 75) = 4863 P(99, 100) = 19454

となるようなすべての正のとに対し, すべてのの合計を求め, その最後の8桁を答えよ.

三次元空間内に$(x_1,y_1,z_1) , (x_2,y_2,z_2)$の二点が与えられているとき, この二点間のマンハッタン距離は$|x_1-x_2|+|y_1-y_2|+|z_1-z_2|$と定義される.

$C(r)$を原点$O(0,0,0)$を中心とする半径$r$の球とする. $I(r)$を球$C(r)$の表面上の整数の座標を持つすべての点の集合とする. $S(r)$を原点$O$から$I(r)$のすべての要素へのマンハッタン距離の総和とする.

例として, $S(45)=34518$.

$S(10^{10})$を求めよ.

多項式$g(x) = x^3 - 2^n \cdot x^2 + n$の最大の実根を$a_n$とする。 例えば$a_2 = 3.86619826\dots$である。

$\displaystyle \sum_{i=1}^{30} \lfloor a_i^{987654321} \rfloor$の最後の8桁を求めよ。

注記：$\lfloor \cdot \rfloor$ は床関数（実数に対してそれ以下の最大の整数）を表す。

すべての部屋が辺の長さ1の完全な正六角形からなるミツバチの蜂の巣を考えよう.

ある特定の部屋に女王蜂が居る.

正の実数$L$に対し, 女王蜂の部屋から$L$の距離がある部屋の個数を$B(L)$としよう(すべての距離は部屋の中心から部屋の中心までを計測したものとする). ここで蜂の巣はどんな距離でも対応できるほど大きいと仮定する.

例をあげよう.$B(\sqrt{3}) = 6, B(\sqrt{21}) = 12, B(111\, 111\, 111) = 54$である.

$B(L)=450$を満たす距離$L ≤ 5 \times 10^{11}$の個数を求めよ.