空間分割の無理ゲー問題 – 2019年東工大 数学 第4問
小問３の解法
T(H_1, \cdot \cdot \cdot, H_n) の取りうる値のうち、3番目に大きいものを求めよ、ということなので、その記号を d_n \text{ } ( n \geqq 3 ) と置きます。
新しい平面を、既存の平面との交線で平行なものが2組（計4本）できるように置けば、追加された平面が分割される領域数が a_n -2 個になっていい感じですが、そのような平面の置き方は出来そうにありません。
それでは、新しい平面を、既存の平面のどれかと平行になるように置けばどうでしょうか。既存の平面が n-1 枚の時、新しい平面と交わるものは n-2 枚なので、以下のような漸化式を立てられます。
d_n = b_{n-1} + a_{n-2}なんかいい感じですが、実はこれではだめです。3番目に大きい値より、小さくなります。
本問の凶悪なところは、こうやって出した値でも、 n= 3, n=4 のときは値が正しいことです（ n= 3 のときは6、 n= 4 のときは12になる）。
n の最初の2つで試してみて、それらしい値(実際に正しい値)が得られるので、間違っていることに気づきようがありません。ほんと良くできています。
ではどうするかと言うと、2番目に多い数を求めるロジックを、2度適用します。すなわち、 H_1, \cdot \cdot \cdot, H_{n-1} を、小問2のロジックによって配置された平面群であるとします。このとき、空間分割数は c_{n-1} です。
この平面群に対し、新しく追加する平面 H_n を、 c_{n-1} を求めるときに選んだ平面対とは別の2平面の交線に平行になるように配置します。
このとき、 H_n と既存平面群の交線の数は n-1 ですが、そのうち1対が平行になっているので、これらの直線によって H_n が分割される数は a_{n-1} -1 となります。
H_n 追加前の空間分割数は c_{n-1} なので、 H_n 追加後の空間分割数 d_n は以下の式を満たします。
\begin{aligned}
& d_n = c_{n-1} + a_{n-1} -1 \\
& = b_{n-1} -1 + a_{n-1} -1 \\
& = b_{n} -2 \\
& = \frac{(n-1)(n^2+n + 6) } {6} \\
& \text{ } \cdots (1)
\end{aligned}
最終トラップ
これで終わったとほっとしていると、設問が持つ最後のトラップに、いきなり足元をすくわれます。
n \geqq 5 のときは良いのですが、問題は n = 4 のときです。既存の平面が３枚しかないため、上記のロジックが使えません。
b_4 = 15, c_4=14 であり、上記の式(1)に n = 4 を代入すると13になります。一方、分割数が12と言うのがあり得るのは、上のほうで示しているので、 n = 4 のときに分割数13があり得るのかどうかが、ポイントです。
まず、 T(H_1, H_2,H_3) = 8 の場合です。 T(H_1, H_2,H_3,H_4) = 13 となるためには、新たに追加する平面 H_4 を既存3平面との3交線が5分割する必要があります。ところが3直線で平面を5分割することはできないので、 T(H_1, H_2,H_3) = 8 の場合は13分割できないことがわかりました。
次に、 T(H_1, H_2,H_3) = 7 の場合です。 T(H_1, H_2,H_3,H_4) = 13 となるためには、新たに追加する平面 H_4 を既存3平面との3交線が6分割する必要があります。ところがこうなるためには、3交線のうち2交線が平行になり、もう1本は平行でない配置になっていなければなりません。しかし、図3からわかるように、3本とも平行になるか、3本とも平行にならないかのどちらかしかありません。
図3の状況では、各平面が構成する3つの交線の方向ベクトルはすべて同じで、各平面の法線ベクトルはそれと直交します。ここで新たに追加する平面 H_4 を、既存の2平面 H_1, H_2 の交線と平行に配置しようとすると、 H_4 の法線ベクトルは H_1, H_3 の交線ベクトルとも直交し、それはすなわち H_1, H_3 の交線と平行であるということを意味するので、 H_1 と H_1, H_2,H_3 との交線はすべて、平行になります。
したがって、 T(H_1, H_2,H_3) = 7 の場合も13分割できないことがわかりました。
最後に T(H_1, H_2,H_3) \leqq 6 の場合ですが、この場合、新たに追加する平面によって増加する空間の最大値は6なので、 T(H_1, H_2,H_3,H_4) \leqq 12 となり、やはり13分割できません。
以上の考察により、 d_4 =12 であることがわかりました。
なお、 n = 3 のときは、式(1)は6になるので、そのまま使えることがわかります。以上をまとめると、
d_n = \left \{
\begin{aligned}
& \frac{(n-1)(n^2+n + 6)} {6} \\
& \text{ } (n=3,n\geqq 5)\\
\\
& 12 \\
& \text{ } (n=4)
\end{aligned}
\right.
となります。
まとめ
本問は解答に至るまでの道筋が非常に見えにくいため、難易度が高くなります。この手の問題では、いきなり3次元で考えるのではなく、より簡単な2次元以下で考えてみることが、ポイントです。
小問3で n=4 の特殊処理が必要なのは、凶悪なトラップです。気が付かなくても大きな減点につながらないと思いますが、漸化式を立てるときに n の条件（ n \geqq 5 ）に注意すれば、気付けるチャンスがあります。漸化式を立てるときには n が満たすべき条件について、気を付けてください。