2016/01/03

モーザー数列

分野: 数列  レベル: マニアック

円周上に $n$ 個の頂点を打ち,その全ての2頂点間を線分で結ぶ。このとき,円は $M$ 個の領域に分割されるとする。
$M$ の最大値は $a_n=\dfrac{1}{24}(n^4-6n^3+23n^2-18n+24)$

Moser’s circle problem という問題です。数列 $\{a_n\}$ をモーザー数列と言います。

$n$ が小さい場合

円の分割問題

$a_1=1$,$a_2=2$,
$a_3=4$(円に内接する三角形は領域を4つに分割する),
$a_4=8$(円に内接する四角形は領域を8つに分割する),
$a_5=16$

となります。 $a_n=2^{n-1}$ と予想したくなりますが,実は違うというのが面白いです($a_6=31$)。最初の数項だけでは数列は1つに決まりません!

一般の位置

3つの線分が一点で交わる場合には,1つの頂点をほんの少しだけズラすことでそのような点を解消し,領域を1つ増やすことができます。

1つの頂点をズラすと別の点で「3つの線分が一点で交わる」という現象が起こる可能性もありますが,ズラす度合いを調節する(調節の仕方は無数にある)ことで,このような場合は排除できます。

よって,以下では3つの線分が一点で交わらない状況を考えます。このような場合を「 $n$ 個の頂点が一般の位置にある場合」と呼ぶことにします。

冒頭の定理の証明

主張:$n$ 個の頂点が一般の位置にある場合,$M$ は $a_n=\dfrac{1}{24}(n^4-6n^3+23n^2-18n+24)$ で一定
を帰納法で証明します。後半は単純な数列の計算です。→べき乗の和の公式

証明

$n=1$ のときは明らか。

$n=k$ のとき主張が正しいと仮定する。 $k+1$ 個の頂点が一般の位置にある場合について考える。頂点を(時計回りの順番で)$P_0,P_1,\cdots,P_k$ とする。

$P_1,\cdots,P_k$ たちを結ぶ線分によって領域は $a_k$ 個に分割される(帰納法の仮定)。そこに線分 $P_0P_i\:(i=1,\cdots,k)$ を追加することで領域がいくつ増えるかを考える。

モーザー数列の導出

線分 $P_0P_i$ は$(i-1)(k-i)$ 本の線分とぶつかるので,領域を$(i-1)(k-i)+1$ 個増やす。

よって,$P_0$ を追加することで,領域は
$\displaystyle\sum_{i=1}^k\{(i-1)(k-i)+1\}\\
=-\dfrac{k(k+1)(2k+1)}{6}+(k+1)\dfrac{k(k+1)}{2}+(1-k)k\\
=\dfrac{1}{6}k^3-\dfrac{1}{2}k^2+\dfrac{4}{3}k$
個増える。

よって,$k+1$ 個の頂点が一般の位置にある場合の領域の個数は
$a_k+\dfrac{1}{6}k^3-\dfrac{1}{2}k^2+\dfrac{4}{3}k$

これが $a_{k+1}$ と等しいことは簡単な計算で確認できる。

僕は数列の最初の数項から次の項を求めよというクイズが嫌いです。
分野: 数列  レベル: マニアック