どこまで深く潜れる？

1m→3m→6m→10m→15mというように、増やす幅を1mずつ増やしながら1つ目のカプセルでテストする。

1つ目のカプセルが壊れたら、最後にテストした安全な深さから、1mずつ深くしていきながら2つ目のカプセルでテストする。

解説

1個目のカプセルで、次の深度を順に試します。

1m → 3m → 6m → 10m → 15m → 21m → 28m → …

つまり、深度の増やし方を

+1, +2, +3, +4, +5, …（1ずつ増やす）にします。
この並びは「三角数」と呼ばれ、n回目の深度は$$1+2+\cdots+n=\frac{n(n+1)}{2}$$

になります。

1. まず大事な考え：1個目が壊れたら、2個目は1m刻みしかできない

カプセルが壊れた瞬間、そのカプセルは使えなくなります。
試作カプセルは2個だけなので、もし1個目が壊れたら、残りは1個です。

残りが1個の状態で飛び飛びに深いところを試すと、もしそこで壊れたらその時点で終了してしまいます。
だから、1個目が壊れたあとは安全策として

1mずつ上げて調べるしかありません。

この「後半は1m刻みになる」という性質が、戦略を決める最大の制約です。

2. 「どれくらい飛ばすのがちょうどいい？」を決める直感

ここからが本題です。

例えば「今までに N 回テストして、ある深さ S までは壊れない」と分かっている状況を考えます。
次の（N+1回目）で、どれくらい深いところまで試すべきでしょうか？

• あまり深くまで飛ばさないと、もし本当の限界深度がずっと深かったときに、
  「壊れないのに浅い所をチマチマ試しただけ」で、回数が無駄になります。
• 逆に深く飛ばしすぎると、もしその回で壊れたときに、
  その直前の安全深度から壊れた深度までの区間を、2個目で1m刻みで総当たりする羽目になります。
  その区間が大きすぎると、「その回で壊れた場合だけ」極端に損をしてしまい、最悪ケースがそこに偏ります。

そこで出てくる自然な考え方がこれです。

ここまでに N 回も試してきたのだから、次で壊れても後処理にかかる最悪の手間も、せいぜい N 回程度に抑えておきたい。
そうすれば「どこで壊れても痛みが同じくらい」になり、最悪ケースが偏らなくなる。

これが「最悪ケースの均等化」の直感です。

3. 均等化すると「増分が 1,2,3,…」になる

「次で壊れたら、2個目で1m刻みに調べるしかない」ので、
次のテストで飛ばす幅（ジャンプ幅）を大きくしすぎると、その分だけ後半の総当たりが長くなります。

だから、n回目のテストでは、もしこの回で壊れたとしても、残りの作業（1m刻み総当たり）が n 回くらいで済む幅にしておくのがちょうど良い、ということになります。

つまりジャンプ幅を

• 1回目：1m
• 2回目：2m
• 3回目：3m
• 4回目：4m
• …

とするのが、均等化の最も素直な形です。

このとき、試す深さは自然に、1, 1+2=3, 1+2+3=6, 1+2+3+4=10,…

となり、三角数になります。

4.最悪のケースの試行回数

1個目のカプセルがn回で壊れたとします。

三角数の地点を試しているので、n回目のテストでは前回の地点よりnメートル深いところをテストしています。

つまり、n-1回目の地点から1mずつ試して行く必要があります。

最悪のケースは、1回目のカプセルが壊れた地点より1mだけ浅い場所がちょうど分岐点の場合です。

つまり追加でn-1回テストするので、合計の回数は,n + (n-1)で、2n-1回になります。

これを深さが増えるとどのように増えるか確認してみましょう。

カプセルが壊れた地点をFとします。

上で解説した通り、n回目の深度はn(n-1)/2mになるので

$F = n(n-1)/2$

$F ≈ N^2/2$

$2F ≈ N^2$

$N ≈ √2F$

となり、最悪のケースの回数である2n-1回は2√2F-1回となり、深さの2倍の平方根に比例します。

また、別の方法として1m、4m、9m、16mと、1回目のカプセルで平方数を試して行く方法もあります。

そちらの方法では最悪のケースの回数がおよそ3√F-2回程度になります。

比べてみると、三角数は2√2F-1 ≈ 2.828√F回、平方数は3√F回と、少しだけ三角数の方が有利になっています。