2019年度の東京工業大学（現東京科学大学）の入学試験に次のような問題が出題されました．

東京工業大学 2019 数学第4問
$H_1,H_2,\ldots,H_n$を空間内の$n$枚の平面とする．$H_1,H_2,\ldots,H_n$によって空間が$T(H_1,H_2,\ldots,H_n)$個の空間領域に分割されるとする．例えば，空間の座標を$(x,y,z)$とするとき，

平面$x=0$を$H_1$，平面$y=0$を$H_2$，平面$z=0$を$H_3$とすると，$T(H_1,H_2,H_3)=8$.
平面$x=0$を$H_1$，平面$y=0$を$H_2$，平面$x+y=1$を$H_3$とすると，$T(H_1,H_2,H_3)=7$.
平面$x=0$を$H_1$，平面$x=1$を$H_2$，平面$y=0$を$H_3$とすると，$T(H_1,H_2,H_3)=6$.
平面$x=0$を$H_1$，平面$y=0$を$H_2$，平面$z=0$を$H_3$，平面$x+y+z=1$を$H_4$とすると，$T(H_1,H_2,H_3,H_4)=15$

である．

各$n$に対して$T(H_1,H_2,\ldots,H_n)$のとりうる値のうち最も大きいものを求めよ．
各$n$に対して$T(H_1,H_2,\ldots,H_n)$のとりうる値のうち2番目に大きいものを求めよ．ただし，$n\geq 2$とする．
各$n$に対して$T(H_1,H_2,\ldots,H_n)$のとりうる値のうち3番目に大きいものを求めよ．ただし，$n\geq 3$とする．

空間全体を平面で区切ったとき，いくつの領域ができるかという素朴な疑問です．この問題は当時かなりの難問としてSNS上で話題となりました．

本記事では，この問題の高次元への一般化を考えます．なお，実は(3)の答えで$n$が小さいときに一般式で表せない例外が発生する（$n=4$のときだけ1つ小さくなる）のですが，その例外の高次元化については難しすぎるので，$n$が十分大きいとして回避することにします．具体的には次の問題を考えます．

一般化
$N\geq 2$とする．$H_1,H_2,\ldots,H_n$を$N$次元空間$\mathbb{R}^N$内の相異なる$N-1$次元超平面とする．$H_1,H_2,\ldots,H_n$によって$\mathbb{R}^N$が分割されてできる$N$次元領域の個数を$T_N(H_1,H_2,\ldots,H_n)$とおく．

$T_N(H_1,H_2,\ldots,H_n)$の取り得る値のうち最大のもの$M_1(N,n)$を求めよ．
$T_N(H_1,H_2,\ldots,H_n)$の取り得る値のうち$m$番目に大きいもの$M_m(N,n)$を求めよ．ただし，$N\geq 3$, $m\geq 2$, $n\geq 2(N-2)m$とする．

1 2次元の場合

本題の問題を解く前に次元が低い場合を考えてイメージをつかみましょう．最も考えやすいのは2次元の場合です．漸化式を作ることで，高校数学の教科書レベルの問題となります．

平面を$n$本の直線で分割したときにできる領域の最大個数を$a_n\,(=M_1(2,n))$とおきます．既に$n$本の直線が配置されているとき，もう1本直線$\ell$を加えると，$\ell$は最大$n$本の直線と交わります．このとき，新たにできる交点の数は$n$個であり，$\ell$は$n+1$個の領域にまたがり，$\ell$がそれらの領域を二分割することで領域の個数は$n+1$だけ増えます．交点が多い方が増える領域の個数も大きくなります．よって，漸化式 \[a_{n+1}=a_n+n+1,\quad a_{0}=1\] が成り立ち，これを解いて \[a_n=a_0+\sum_{k=0}^{n-1}(k+1)=1+ \sum_{k=1}^{n}k=1+\frac{1}{2}n(n+1)=\frac{1}{2}(n^2+n+2)\] が得られます．

一方で，漸化式を使わずにいきなり領域の数を求めることもできます．先程の直線の追加による領域の増加の様子を更に突き詰めて考えると，領域が増える原因は「直線の存在による分割」と「直線同士の交差」のみで，それぞれが1つ発生するごとに1つ領域が増加することが分かります．また，直線が一つもない初期状態では「空間全体」という1つの領域が存在しています．よって，直線が$n$本あるという条件の下で領域の数が最大となるのは，交差が最も多い場合，すなわち任意の2本の直線が平行でなく互いに交わり，3本以上の直線が同一の点では交わらない場合（このような状況を「一般の位置にある」という）であり，そのときの領域の個数は \[\begin{align}
M_1(2,n)&= (\text{交点の総数})+(\text{直線の本数})+1 \\
&={_n}C_2+n+1 \\
&=\frac{1}{2}(n^2+n+2)
\end{align}\] と計算できます．

2 $N$次元の場合

さて，今度は一般の$N$次元の問題に挑戦しましょう． 2次元の場合を参考に，領域の増加の仕方を考えていきます．イメージが湧きにくい場合は3次元空間を想像しましょう．今度は次元$N$も動くため，$N,n$に関する二重の漸化式が得られることになります．

2次元の場合と同様に，「一般の位置にある」というのは言葉通り特殊な位置関係ではないという意味ですが，より正確には$H_1,H_2,\ldots,H_m\subset\mathbb{R}^N$が一般の位置にあるとは，次の2条件

$\operatorname{dim}\bigcap_{j=1}^k H_{i_j}=N-k$ for $k\leq N$, $1\leq i_1<i_2<\cdots <i_k\leq m$;
$\bigcap_{j=1}^k H_{i_j}=\emptyset$ for $k> N$, $1\leq i_1<i_2<\cdots <i_k\leq m$

が成り立つことを言います．直感的には，無秩序に超平面を配置すればほぼ確実に「一般の位置」になります．

既に$n$枚の$N-1$次元超平面$H_1,\ldots,H_n$がある状態にもう1枚$N-1$次元超平面$H_{n+1}$を加えたときに増加する領域の個数$D(H_1,\ldots,H_n;H_{n+1})$は，$H_1\cup \cdots\cup H_n$が$H_{n+1}$を分割することで作られる$N-2$次元領域の個数と等しい．よって，\[D(H_1,\ldots,H_n;H_{n+1})\leq M_1(N-1,n)\] が成り立つ．等号$D(H_1,\ldots,H_n;H_{n+1})= M_1(N-1,n)$は$H_{n+1}$上で$H_1\cap H_{n+1},\ldots,H_n\cap H_{n+1}$が一般の位置にある（それらの共通部分の間に平行であったり3つ以上が同じ部分で交わったりするなどの特殊な位置関係がない）ときに達成される．よって， \[\displaystyle\max_{H_1,\ldots,H_{n+1}}D(H_1,\ldots,H_n;H_{n+1})= M_1(N-1,n)\] であり，二重漸化式 \[M_1(N+1,n+1)=M_1(N+1,n)+M_1(N,n),\quad M_1(N,1)=2,\quad M_1(1,n)=n+1\; (N,n\geq 1)\] が得られる．よって， \[\begin{align}
M_1(N,n)&= \sum_{i=1}^{n-1}M_1(N-1,i)+2\\
&=\sum_{i_2=1}^{n-1}\left(\sum_{i_1=1}^{i_2-1}M_1(N-2,i_1)+2\right)+2\\
&=\cdots \\
&=\sum_{i_{N-1}=1}^{n-1}\left(\sum_{i_{N-2}=1}^{i_{N-1}-1}\left(\cdots \left(\sum_{i_{1}=1}^{i_{2}-1}(i_1+1)+2\right)+2\right)+\cdots+2\right)+2 \\
&=\sum_{i_{N-1}=1}^{n-1}\left(\sum_{i_{N-2}=1}^{i_{N-1}-1}\left(\cdots \left(\sum_{i_{0}=1}^{i_{1}-1}1+2\right)+2\right)+\cdots+2\right)+2 \\
&= \sum_{i_{N-1}=1}^{n-1} \sum_{i_{N-2}=1}^{i_{N-1}-1}\cdots\sum_{i_0=1}^{i_1-1}1 +\sum_{\ell=1}^N 2 \sum_{i_{N-1}=1}^{n-1} \sum_{i_{N-2}=1}^{i_{N-1}-1}\cdots\sum_{i_\ell=1}^{i_{\ell+1}-1}1 \\
&= {_{n-1}}C_N+2 {_{n-1}}C_{N-1}+2 {_{n-1}}C_{N-2}+\cdots + 2{_{n-1}}C_{0} \\
&=\sum_{j=0}^N {_n}C_j.
\end{align}\] ここで， \[\begin{align}
\sum_{i_{k-1}=1}^m \sum_{i_{k-2}=1}^{i_{k-1}-1}\cdots \sum_{i_{0}=1}^{i_{1}-1}1 &= \sum_{1\leq i_0<i_1<\cdots i_{k-1}\leq m}1 \\
&= (1\leq i_0<i_1<\cdots i_{k-1}\leq m\text{を満たす組}(i_0,i_1,\ldots,i_{k-1})\in \mathbb{N}^k\text{の個数}) \\
&=(\text{1から$m$までの自然数から$k$個選ぶ場合の数}) \\
&= {_m}C_k
\end{align}\] とパスカルの三角形の性質${_{n-1}}C_j+ {_{n-1}}C_{j-1}= {_{n}}C_j$を用いた．
超平面$H_1,\ldots,H_{n-m+1}$を(1)の最大化条件を満たすように（つまり一般の位置に）置く．次に，超平面$H_{n-m+2}$を直線$H_1\cap H_2\cap\cdots \cap H_{N-2}\cap H_{n-m+2}$と平面$H_{N-1}\cap H_{N}\cap\cdots\cap H_{2N-5}\cap H_{n-m+2}$が平行になる以外には$H_1,\ldots,H_{n-m+2}$およびそれらの交わりのうちどの2つも平行でないように置く．同様に$j=2,3,\ldots,m$に対して超平面$H_{n-m+j}$を直線$H_{(2N-5)(j-2)+1}\cap H_{(2N-5)(j-2)+2}\cap\cdots \cap H_{(2N-5)(j-2)+N-2}\cap H_{n-m+j}$と平面$H_{(2N-5)(j-2)+N-1}\cap H_{(2N-5)(j-2)+N}\cap\cdots\cap H_{(2N-5)(j-1)}\cap H_{n-m+j}$が平行になる以外には$H_1,\ldots,H_{n-m+j}$およびそれらの交わりのうちどの2つも平行でないように置く．このとき，$m-1$枚の超平面$H_{n-m+2}, H_{n-m+3},\ldots, H_{n}$のそれぞれを配置する操作によって新たに生じる領域の個数がその最大の場合から1ずつ減ったものになっているから，$H_1,\ldots,H_n$によって分割される領域の個数は$M_1(N,n)-m+1$となるはずである．$m$を$m-1,m-2,\ldots,2$に置き換えても同様の配置が可能だから，これと$M_1(N,n)$の間の任意の自然数は$T(H_1,H_2,\ldots,H_n)$の値となり得る．よって，$M_1(N,n)-m+1= \sum_{j=0}^N {_n}C_j-m+1$が$m$番目に大きい領域の個数$M_m(N,n)$である．

不思議なことに自然と二項係数の和が出てきました．2次元の場合の2つ目の解き方でも途中で二項係数の和が登場していましたね．試しに，(1)の答えに$N=2$を代入してみると， \[M_1(2,n)={_n}C_2+{_n}C_1+{_n}C_0=\frac{1}{2}(n^2+n+2)\] となり，確かに2次元の場合と一致しています．高次元でも同様であることが確認できました．

今回は組み合わせの考え方と漸化式を使って超平面配置問題を考えてみました．次回はこの問題をザスラフスキーの定理を使ってよりエレガントに解いてみたいと思います．

この記事を共有

N次元超平面配置の問題part1

1 2次元の場合

2 \(N\)次元の場合