まず最初にこんな問題はどうでしょうか。
これは「32」であろうことは容易に想像できます。
それでは次の問題はどうでしょうか。
こちらは具体的な図形の問題です。これも数字の並びということでは最初の問題と変わりません。数列が先に進むにつれて作図も数え上げも面倒になってきます。そうなると理屈はさておいても答えは「32」に違いない、と一足飛びに考えてしまいたくなります。さて、実際に数え上げてみました。すると「31」にしかならず１つ足りません。
今回の問題は区画の最大数を求めることなので、３つ以上の線分が同一の点で交わってしまうと区画の数は最大値から減ってしまいます。それに注意しながら幾度となくチャレンジしてみましたがやはり最大値は「31」にしかなりません。
こうなるとやはり理屈に立ち戻らないといけなくなります。
(n-1)個の点が配置されている状態においてn個目の点を追加するときの区画数の増加分を考えてみます。
新たな点nから(n-1)本の線分を引きます。各線分は既存の線分と交わることになりますが一回交差するたびに区画が一つ増えることが次の図からわかります。
従って(n-1)本の各線分が公差する点の数の総和を求めればそれがそのまま区画の増加分に対応します。一般にk番目の点は、既存のn-1個の点を二つのグループに分断します。一方が(k-1)個、もう一方が(n-1-k)です。追加した線分が交差する点の最大値は、この二つのグループ間で結ぶ線分の組み合わせの数であるその積に、”1”を加えたものとなります。上図の例では、４つの交点が登場して区画数は５つ増えています。つまり、
これをk=1～(ｎ-1)までの総和を計算することで漸化式は次のように計算されます。
次にこれを用いて一般項を求めてみると、
となりました。これを具体的な数列で表してみると、
となります。「31」は正しかったことがわかりました。教訓としては数列の最初の５項くらいで分かった気になってはいけない、ということですね。
