某所で「まじめな数学の問題」として紹介された問題。
「円を４本の直線で分割します。このとき、円は最大限、いくつの部分に分けられるでしょう？？」
このままの問題だと’やれば解ける’となるので、では例えば引く線が400本だったらどうなるのか？とかそんな事を私は考える。いや、400本の場合に特別な興味があるワケではなくて、一般の n 本に対してこれはいくつになるか？を求めたい。とは、言えリンク先に正解がもうすでに書いてあるんだけど。
ここで注目する事は、
・２直線は１点で交わる
・１直線は１つの領域を２つに分ける。
これだけ。
さて、これをどう考えるかと言うと、単純で。
先ず、n本の線が引かれた時に円の最大の分割の数がSnとする。n = 0 の時は、S0 = 1 だ。
で、今 Sn の時にそこにもう1本加え、その線が以前に引かれたn本の線と交わる事が出来れば、その時n個の新しい領域を加える事が出来る。
つまり、こんな式が出来る。
Sn+1 ≦ Sn + n
さて、この不等式なのだけど、非常に等式が成立して欲しいところだ。ところが、実際どの直線も平行でなくどの交点も2本以上の直線が交差しないように配置する事は可能だ。で、その交点を円の中に収めた時、領域が最大数になるのだけどそのためには直線を平行移動させるとか、円を大きくするとかするように考えるとこれも可能である事が分かるハズだ。ハズだ。だよね？
となれば、こんな漸化式が出来る。
Sn+1 = Sn + n
これをぱぱっと解いて、
Sn+1 = S0 + 1 + 2 + 3 + … + n
Sn = 1+{n(n+1)}/2
となる。やった。完了。
で、参考文献はこれ。
「コンピュータの数学」Graham/Knuth/[ほか]著 有沢誠/[ほか]訳
これにはさらに折れ線にした時の拡張などが載ってるよ。
また、すでに私の手元には無いのだけど、この本には、
「パズルより面白い中学入試の算数 深読みすれば宝の山」ピーター・フランクル/著
３次元や４次元に拡張する話が載っていたような。
って、ことでやる気のある人は、ｎ次元の拡張を考えてみてはいかが？