恐竜エッグドロップv2

This question is a little different and kinda follow-up version
of
Dinosaur Egg Drop

1-あなたは100階建ての建物と6つのApatosaurus恐竜の卵があります。

2 – あなたは81階建ての建物と3つのマソスポランダス恐竜の卵を持っています。

どちらの場合でも、これらの異なる種類の恐竜卵の耐久性を見つけたいと思います(私はあなたがなぜそれをテストする必要があるのか​​わかりませんが、狂った科学者)。

だから少なくとも何回、卵が各最悪の状況で壊れないように最上階を見つけるために卵を落とす必要がありますか?

ベストアンサー

より一般的には、$ e $の卵があるとし、$ d
$の雫の時間しかないとします。あなたが成功できる最も高い建物は何ですか?すべての良い質問のように、これはパスカルの三角形を使って答えられます。

$ e $の卵と$ d $の雫を考えれば、あなたが成功できる最大の建物は   $$ binom {d}
1+ binom {d} 2+ dots + binom {d} {e} $$フロア。これはパスカルの三角形の$ d
$番目の行の最初の$ e $エントリの合計と等しく、最初のエントリをスキップします(常に1です)。

  1. With 100 floors and 6 eggs, the optimal number of drops is 7. 7
    drops is enough since the sum of the first 6 entries in the 7th row
    is 7 + 21 + 35 + 35 + 21 + 7 = 126 ≥ 100. 6 drops is not enough
    since looking at the 6th row, 6 + 15 + 20 + 15 + 6 + 1 = 63 <
    100.

  2. With 81 floors and 3 eggs, it will take 8 drops, since 8 + 28 +
    58 ≥ 81, but 7 + 21 + 35 < 81.


 Modified Pascals's triangle (left side of ones removed).

                        1
                     2     1
                  3     3     1
               4     6     4     1
            5    10    10     5     1
         6    15    20    15     6     1
      7    21    35    35    21     7     1
   8    28    56    70    56    28     8     1

私は証拠のスケッチを提供します。 Opt(d、e)をd滴とe卵で処理できる階の数とすると、 Opt(d、e)= 1 +
Opt(d-1、e)+ Opt(d-1、e-1)$$
どうして?あなたが成功することができれば、落ちる床の上にOpt(d-1、e)フロアが最大でなければなりません。なぜなら、卵が生存すればd-1滴とe卵が残るからです。同様に、卵が壊れた場合には、最大でもOpt(d-1、e-1)フロアがなければなりません。あなたが成功することができれば、床の総数は、最大で2つの数字の合計と、あなたが落とした階の1になります。上の方程式は、$
d $の帰納法によって$ binom {d} 1+ binom {d} 2+ dots + binom {d} {e}
$式を証明することができます。

一般に、$ f $フロアがあれば、床番号$ 1 + binom {d-1} 1+ binom {d-1} 2+
dots + binom {d-1} {e-1}、$ $ $は$ binom {d} 1+ binom {d} 2+
dots + binom {d} {e} ge f $のような最小の数です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です