パズルの国のアリス

自動ピザカッター(解答)

最初のウォーミングアップ問題だが,まず最大のピース数を考える前に,どういう切り分け方がありうるかを考えてみよう。まず1回切るだけだと,ピザは2切れに分かれるのみだ。2回ならば,その2つの切断線が交われば4ピースに,そうでなければ3ピースに分かれる。切断線が3本だと,場合の数が急に増えるが,まだ書き出すことができて,例えば下図のような場合が考えられ,ピース数は左から順に4,5,6,7だ。

切断線の本数が同じなら線の交点が多いほどピース数が増えそうだということは図から見て取れる。既に何本かの切断線があるときにもう1本切断線を増やすとどうなるかを考えてみよう。下図をご覧いただきたい。

青線で示した新しい切断線は他の3本の切断線と交わり,4つの線分に分割されているが,これらの線分それぞれが既にあったピースを二分してピース数を増やしている。つまり,この切断線が加わることにより,ピース数は4つ増えている。

 さて,既にn本の切断線があるところに,新しい切断線を加えるとピース数は最大でいくつ増えるだろうか。これは簡単だ。切断線は直線だから,他の線と2カ所以上で交わることはできない。つまり,既にあるn本すべてと交わることで,交点数は最大のnになり,切断線自身は最大でn+1個の線分に分割される。これらの線分が既にあったピースをそれぞれ二分するからピース数は最大でn+1増えることになる。新しい切断線を注意深く引けば,この最大の交点数nを達成することがいつでも可能なことは,すぐわかる。従って,n本の切断線でできる最大のピース数をFnとすると,漸化式Fn+1Fn+(n+1)が得られる。また,F0=1だから,この漸化式を解いて,Fn=(n2n+2)/2を得ることは,高校数学の範囲だろう。F3=7だから,n=3の場合の4つの図(一番上の図)において,一番右がピース数最大の場合を与えることに合致する。

 このように漸化式を考えながら,以降の問題に挑戦することも難しくはないのだが,上の考え方をさらに整理してみよう。切断線が1本増え,その切断線が他の切断線とnカ所で交わるとピース数がn+1増える。このことから,次のことに気がつくのがポイントだ。直線だけで丸いピザを切る場合,切断線の数をL,それらの直線が作る交点の数をPとするとピース数はPL+1となる。なぜなら,最初は丸いピザが1ピースだけあり,切断線やそれらの交点の増加はそのままピース数の増加につながるからだ。この式に基づいて,先のピース数最大の場合をもう一度考えると,明らかにLnであり,Pが最大になるのはn本の切断線がすべて互いに交わる場合だから,nC2である。従って,最大ピース数は

で与えられる。

 次の問題は平均ピース数だ。これを上の考え方で一気に料理してしまおう。先と同じでLnだが,Pは最大を考えるのではなく平均だ。それには2本の切断線が交わる確率がわかればよい。切断線の端点はピザの周から2点を一様ランダムに選ぶというのが条件だった。2本の切断線の場合,これは4点を一様ランダムに選び,その2つずつを結ぶのと変わらない。ただ,どの2つを結ぶかで下図の3通りに分かれる。

切断線が交わるのは真ん中の場合だけであり,一様ランダムという仮定から,その確率は1/3だ(上図のどれになるかはまったく均等)。従って全部でnC2ある切断線の対の中で交わるのはその1/3と期待され,交点数Pの期待値はnC2/3となる。よって,ピース数の平均値(期待値)は

 最後の問題は,同時にm点を選び出すタイプの自動カッターによるピース数だ。mが小さいときはmが1増えるごとに倍になっているので,ピース数は2mー1と予想したくなるが,これはm=6で成り立たなくなる。これも先の問題と同様に考えよう。

 まずLだ。これは比較的簡単で,m個の点から2つずつ選んで2点を結ぶ切断線をすべて引くのだから,LnC2だ。厄介そうに思えるのがPだが,実は,m個の点から4つを選び四角形を作ると,その対角線の交点として切断線の交点が得られることに気がつくと簡単になる。逆に切断線が交わっていれば,それらを対角線とする四角形がただ1つ決まるので,四角形と切断線の交点は1対1に対応し,その数は等しい。m個の点から4つを選んで作る四角形の数はもちろんnC4であり,これがPに等しいから,ピース数は

となる。これはmに関する4次式だから,多項式の形に書くこともできるが,上のままのほうがかえって計算しやすいような気がするのでこのままにしておこう。この式は,mlの場合にmCl=0と決めておけば,m=1,2,3の場合にも使えて便利である。m=1,2,3,4,5,6,7の場合,それぞれ1,2,4,8,16,31,57となり,倍倍になっていくというパターンからm=6で初めて外れることがわかる。

となる。これはmに関する4次式だから,多項式の形に書くこともできるが,上のままのほうがかえって計算しやすいような気がするのでこのままにしておこう。この式は,mlの場合にmCl=0と決めておけば,m=1,2,3の場合にも使えて便利である。m=1,2,3,4,5,6,7の場合,それぞれ1,2,4,8,16,31,57となり,倍倍になっていくというパターンからm=6で初めて外れることがわかる。

問題はこちらです