【東京工業大学2021年度前期入試数学第3問】素数となるカタラン数

東工大の第3問はカタラン数に関する問題です．これも難しくはないですが，とらえどころのない問題です．

問題

解答解説

(1) の解答

何も考えずに式を書いていけばおしまいです．
\begin{align} n\ {}_{2n}\mathrm{C}_{n} &=\frac{n\times (2n)!}{(n!)^2} = \frac{(2n)!}{(n-1)!\times n!}\\ (n+1)\ {}_{2n}\mathrm{C}_{n-1} &=\frac{(n+1)\times (2n)!}{(n-1)!\times (n+1)!} = \frac{(2n)!}{(n-1)!\times n!} \end{align}
であるので，$n\ {}_{2n}\mathrm{C}_{n} = (n+1)\ {}_{2n}\mathrm{C}_{n-1}$ が成立します．また，${}_{2n}\mathrm{C}_{n-1}$ は整数であるので $n\ {}_{2n}\mathrm{C}_{n}$ は $n+1$ で割り切れるが，$n$ と $n + 1$ は互いに素であるので，${}_{2n}\mathrm{C}_{n}$ は $n + 1$ で割り切れる，すなわち，$n+1$ の倍数になります．

(2) の解答

$a_{n} > n + 2$ を数学的帰納法で証明します．

$a_{4} = \displaystyle\frac{{}_{8}\mathrm{C}_{4}}{5}=\frac{8\times 7\times 6\times 5}{4\times 3\times 2\times 1\times 5}=14 > 6 = 4 + 2$ であるので，$n = 4$ のときは成立します．

$k$ を $4$ 以上の任意の整数として，$a_{k} > k + 2$ が成立しているならば $a_{k+1} > k + 3$ が成立することを示します．
\begin{align} a_{k+1} &= \frac{{}_{2k+2}\mathrm{C}_{k+1}}{k+2}\\ &= \frac{(2k+2)!}{(k+1)!\times (k+1)!\times (k+2)}\\ &= \frac{(2k+2)(2k+1)}{(k+1)(k+2)} \times a_{k}\\ &= \frac{2(2k+1)}{k+2}\times a_{k}\\ &> \frac{2(2k+1)}{k+2}\times (k+2)\ \ \ \ \ \ \left(\frac{2(2k+1)}{k+2}>0\mbox{ かつ }a_{k}>k+2\mbox{ より}\right)\\ &= 2(2k+1)\\ &= 4k + 2 \end{align}
が成立します．$k$ が $4$ 以上の整数であることから，$(4k + 2) - (k + 3) = 3k - 1 > 0$ が言えるので，$a_{k+1} > 4k + 2 > k + 3$ が成立します．

よって，$n$ に関する数学的帰納法により $n \geqq 4$ ならば $a_{n} > n + 2$ が言えました．

(3) の解答

まず，$n$ が $5$以上のときには (2) を使って $a_{n}$ が素数にならないことを示します．

$k$ を $4$ 以上の整数とします．

小問 (2) から $\displaystyle a_{k+1} = \frac{2(2k+1)}{k+2}\times a_{k}$ となります．(1) より $a_{k}$, $a_{k+1}$ は整数であるので，$pq = k+2$であり, $\displaystyle\frac{2(2k+1)}{p}$ と $\displaystyle\frac{a_{k}}{q}$ がともに整数であるような正の整数 $p$, $q$ が存在します．このとき，$\displaystyle a_{k+1} = \frac{2(2k+1)}{p} \times \frac{a_{k}}{q}$ と表されます．

ここで，$k \geqq 4$ であるので，$2(2k+1) - (k+2) = 3k > 0$ かつ $a_{k} > k + 2$ より $\displaystyle\frac{2(2k+1)}{p} \geqq \frac{2(2k+1)}{k+2} > 1$ かつ $\displaystyle\frac{a_{k}}{q} \geqq \frac{a_{k}}{k+2} > 1$ となり，$\displaystyle \frac{2(2k+1)}{p}$ と $\displaystyle\frac{a_{k}}{q}$ はともに $2$ 以上の整数であることから，$a_{k+1}$ は合成数となります．

よって，$n \geqq 5$ のとき $a_{n}$ は素数にはなりません．

あとは $n = 1, 2, 3, 4$ について具体的に値を求めると，
\begin{align} a_{1}&=1,& a_{2}&=2,& a_{3}&=5,& a_{4}&=14 \end{align}
であるので，$a_{n}$ が素数となるのは $n = 2, 3$ のときのみとなります．

感想

問題にある数列 $a_{n}$ がカタラン数というやつで，例えば $n$対の ( と ) からなる正しい系列(カッコ開くとカッコ閉じるが一対一に対応している系列)が $a_{n}$ 通りであることが知られています．

• $n = 1$ のときは ( ) の1通り
• $n = 2$ のときは ( ) ( ) と ( ( ) ) の2通り
• $n = 3$ のときは ( ) ( ) ( )，( ) ( ( ) )，( ( ) ) ( )，( ( ) ( ) )，( ( ( ) ) ) の5通り

カタラン数 (Wikipediaへ)

他にもいろいろとあるようで，場合の数とカタラン数の関係を証明する問題も面白いとは思いますが，今回はカタラン数そのものの性質を問う問題でした．

さて，この問題ですが，(3) の $a_{n}$ が素数となる $n$ を求めさせるのが主問題で，(1) と (2) はそのための誘導問題です．

${}_{2n}\mathrm{C}_{n}$ という数を考えてみると分かると思いますが，$n$ が大きくなると多くの種類の因数を持ちます．ですので，$a_{n}$ が素数となる $n$ は小さい数に限定されることが直感として分かるかと思います．

そう考えれば，(3) の答えも解き方も予想が付くと思います．実際，書き方はいろいろとありそうですが，(2) を使って $n \geqq 5$ のときをまとめて処理するという方針が基本となるでしょう．

全体として，この問題も誘導に沿っていけば難しい問題ではないと思います．しかも，第2問よりも計算量が少ないので，短時間で解答できるでしょう．

小問 (3) がもしかすると悩ましいのかもしれませんが，個人的には難易度の点で歯ごたえのない問題でした．