パズルの国のアリス

卵の強度テスト(解答)

坂井 公(筑波大学)題字・イラスト:斉藤重之

 

解答例2人が考えた手順とは次のようなものだ。最初のサンプル卵をまず10段目から落とす。もし割れてしまえば,次のサンプル卵で,1段目から順にテストする。最悪でも9段目までテストすればレベルが確定する。最初のテストで割れなければ,次は10+9=19段目から落とす。このとき割れてしまえば,次の卵で11段目からテストすれば最悪でも18段目まででテストが完了するので,落とす回数は合計で10回以内だ。

2回目のテスト(19段目)でも割れなければ,以下,3回目は10+9+8=27段目,4回目は34段目と,増やす段数を下げながら割れるまでテストしていく。例えば5回目で割れたとすると,それは10+9+8+7+6=40段目を試したときであり,その前の34段目では割れなかったのだから,2つめの卵で35段から順に39段まで最大5回,1つめの卵の分を合わせても10回のテストでレベルが確定する。

最初の卵が7回目の10+9+8+7+6+5+4=49段目のテストでも割れなければ,2つめの卵を使うまでもなく,次は最上段の50段目からのテストで品質調査は完了する。

一般には,サンプルが2つ使える場合,硬度レベルが1から1+2+…+n=n(n+1)/2までの判定は 合計n回以下の落下テストで可能であるといえる。この問題では50段だから,n(n+1)/2≧50に当てはめると,n=10という答えが得られる。

もし,サンプルが3個あるなら,最初のサンプルを落として割れてしまったとき,まだ2個のサンプルが使えるので,テストした段より下の段数がn(n+ 1)/2以下なら,あとn回のテストで調査は完了する。最初の卵が割れなければ,そこより上の段を調べればよく,そのために3個の卵がそのまま使える。したがって3個のサンプルが使える場合にn回以下の落下テストで調べられる段数をL(n)とするなら,Lは漸化式

L(n+1)=L(n)+1+n(n+1)/2を満たす。明らかにL(1)=1だから,最初の方を表にしてみると,

 

n 1 2 3 4 5 6 7 8 ・・・
L(n) 1 3 7 14 25 41 63 92

 

となり50段ならば7回以内の落下テストで調査が完了する。(最初は,6(6+1)/2=21の上の段,つまり22段目からテストするといい。)

実は,上の漸化式を解くと

L(n)= n(n2+5)/6

という式が得られるが,この式を導くのはお任せしよう。

さらに一般化して,サンプルがm個使える場合にn回の落下テストで識別できるレベル数をL(n,m)とするなら,先と同様な考察により,漸化式

L(n+1,m+1)

=L(n,m+1)+1+L(n,m)

が得られる。実際,

L(n,1)=n,

L(n,2)=n(n+1)/2

L(n,3)=n(n2+5)/6

のすべてが

L(n,0)=n(0,m)=0

として,この漸化式から導かれる。漸化式を解いて,L(n,m)の式をなるべく一般的な形で書くなら

 

 

とすることも可能だ。ここで記号は2項係数だが,j が0≦j≦kの範囲にないときは0と定義する。

例えば

であるが,値を計算するだけなら先の漸化式を用いるほうが簡単だろう。

ただ,こういう式が出てくるからにはL(n,m)の値を組み合わせ論的に導くこともできそうに思うのだが,少なくとも筆者にはうまい説明が見つからない。読者の皆さんの教えを請う。

 

 

参考にした本:Peter Winklerによる次の2冊(ともに出版元はA K Peters, Ltd.)Mathematical Puzzles: A Connoisseur’s Collection(2004)Mathematical Mind-Benders(2007)ルイス・キャロルによる 『不思議の国のアリス』『鏡の国のアリス』

 

 

問題に戻る

 

 

 

問題はこちらです