入試数学コンテスト第1回第5問解答解説

第5問は数列と極限の分野からの出題です。(1)(2)ともに難易度が高い問題です。まずは問題文の意味を正確に理解し, どうしたら2回の操作でボールの並びが元の並びと同じになるのか実験しながら法則を理解しましょう。

まずは(1)です。漸化式を組み立てる前に, 問題文で紹介されている「操作」の意味を理解しましょう。

以下の操作 $\sigma$

$$\sigma = \left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 3 & 1 \end{array}\right)$$

を2回行ったとき, ボールがどのように動くかを紙にかいて追ってみましょう。

左端（[1]と表す）のボールに注目します。1回目の操作 $\sigma$ で[1]のボールは[2]に移ります。[2]のボールは2回目の操作 $\sigma$ で[3]に移ります。つまり, 左端のボールは操作 $\sigma$ を2回行うと左端（[1]）から右端（[3]）に移ります。

このとき, 操作 $\sigma$ は「ちょうど2回行うとボールの並びが元の並びと同じになる」という条件を満たしていないことがわかります。

同様に考えると, 以下の操作 $\tau$ は上記の条件を満たしていることがわかります。

$$\tau = \left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 1 & 3 \end{array}\right)$$

ボールはそれぞれ次のように移動しています。

• [1] $\to$ [2] $\to$ [1]
• [2] $\to$ [1] $\to$ [2]
• [3] $\to$ [3] $\to$ [3]

ここまでで「操作」の意味は理解できましたね。

$a_n$ はボールが $n$ 個並んでいるときに, 「ちょうど2回行うとボールの並びが元の並びと同じになる」という条件を満たす操作の個数を表します。

(1)の問題文では, 「$a_n$ を $a_{n-1}$ と $a_{n-2}$ を用いて表せ」となっているので,

• ボールが $n$ 個並んでいるとき
• ボールが $n-1$ 個並んでいるとき
• ボールが $n-2$ 個並んでいるとき

という3つの状況にどのような関連性があるのかに注目しましょう。

(1)の解答を進めるための第一歩は, 「左端の1個のボール（に限らず, 任意のある1個）を固定したらどうなるんだろう？」という着想を得ることです。

そうすると $a_n$ と $a_{n-1}$ に以下の関係性があることが直ちにわかります。

$$a_n = a_{n-1} + \text{固定しない場合}$$

ここを足がかりにして,

$$c_n = (n-1) \cdot a_{n-2}$$

を求めることができれば正解できたでしょう。

次に(2)です。これは上記の「操作」とは独立した問題で, 以下のように言い換えることができます。

$a_1 = 1, a_2 = 2$ は(1)の段階で（実験用として）手計算できていると望ましいです。具体的には,

• $n=1$の場合

$$\sigma = \left(\begin{array}{ccc} 1 \\ 1 \end{array}\right)$$

• $n=2$の場合

$$\sigma = \left(\begin{array}{ccc} 1 & 2 \\ 1 & 2 \end{array}\right), \left(\begin{array}{ccc} 1 & 2 \\ 2 & 1 \end{array}\right)$$

の操作が条件$(*)$を満たします。

さて, (2)は難問です。

• そもそも漸化式は綺麗に解けるのか？
• どうして $\log$ が出てくるのか？

などの疑問が湧いてきます。

いろいろな方法を試してみるとわかりますが, どうやら漸化式 $a_n$ を綺麗な形で解くことは相当難しそうです。

そこで $a_n$ を何かしらの関数で上下から評価して, 「はさみうちの原理」によって極限を求めることはできないか？と考えてみましょう。

はさみうちの原理は, 数列（あるいは関数）の極限を求める手法として, 入試問題でも頻出です。

その証明は大学数学の範囲ですが, 興味がある方は以下の記事を読んで勉強しておくと良い学びになるでしょう。→はさみうちの原理の証明

さて, (2)の解答の最難関ポイントは, $a_n$ を評価できる「いい感じの数列」を自分で見つけることです。

そこで $a_n$ を評価するために, 答えにある程度の目処を付けてしまいましょう。

すなわち, $a_n$ と $n!$ はどれくらい値が近い（or 遠い）のかを調べてみます。

極限

$$\lim_{n \to \infty} \dfrac{\log a_n}{\log n!}$$

を求めるのですから, $a_n$ と $n!$ の関係に注目するのは自然な発想です。

そこで, 仮に一定の値 $c$ に収束するとしたら, $c$ はどんな関係式を満たすのかを考えてみます。

極限を実数 $c$ とすると, 十分大きい $n$ に対して $$\begin{aligned} \dfrac{\log a_n}{\log n!} \fallingdotseq c \\ \iff a_{n} \fallingdotseq (n!)^c \end{aligned}$$

のような「粗い」関係が期待されそうです。

もっと言うと, $n$ 個の区別できるボールが横一列に並んでいるとき, その並び替えの方法は全部で $n!$ 通りなので,

$$a_n \leq n!$$

が成り立ちます。よって $c$ は（存在するとしたら） $0 \leq c \leq 1$ の不等式を満たす実数です。

さて, このような実数 $c$ は存在するのでしょうか？

粗い計算でしたが, どうやら $c = \dfrac{1}{2}$ を用いると, $a_{n} \fallingdotseq (n!)^c$ が期待できそうです。

もし厳密に $a_{n} = (n!)^{\frac{1}{2}} = \sqrt{n!}$ が成り立つとすると

$$\lim_{n \to \infty} \dfrac{\log a_n}{\log n!} = \dfrac{1}{2}$$

です。答えに近づいてきました。

実際の答案では, 上記のような粗い評価と計算では点数を見込めないでしょう。

最終的に「はさみうちの原理」を用いて

$$\lim_{n \to \infty} \dfrac{\log a_n}{\log n!} = \dfrac{1}{2}$$

に答案を着地させられるような関数（評価）を見つけてきましょう。

まず, 下側は $\sqrt{n!}$ で評価できそうです。なぜなら

• $\sqrt{1!} = 1, a_1 = 1$
• $\sqrt{2!} = \sqrt{2}, a_2 = 2$

より, $\sqrt{n!} \leq a_n$ が期待できるからです。

$$\dfrac{1}{2} = \lim_{n \to \infty} \dfrac{\log \sqrt{n!}}{\log n!} \leq \lim_{n \to \infty} \dfrac{\log a_n}{\log n!}$$

なので, $\sqrt{n!} \leq a_n$ は示せたら嬉しいです。

上側はどうでしょうか？

$a_n \leq f(n) \sqrt{n!}$ が成り立つような「うまい」関数 $f(n)$ があると仮定すると,

$$\lim_{n \to \infty} \dfrac{\log a_n}{\log n!} \leq \lim_{n \to \infty} \dfrac{\log \left\{ f(n) \sqrt{n!} \right\}}{\log n!} = \dfrac{1}{2} + \lim_{n \to \infty} \dfrac{\log f(n)}{\log n!}$$

となるので,

$$\begin{cases} a_n \leq f(n) \sqrt{n!} \\ \dfrac{\log f(n)}{\log n!} \to 0 \quad (n \to \infty) \end{cases}$$

のような $f(n)$ が見つかれば嬉しいです。

さらに, 下段の式の分母 $\log n!$ に注目して,

$$\log n! = \sum_{k=1}^{n} \log k \geq \int_{1}^{n} \log x \, dx = n \log n - n + 1$$

までわかってしまえば,

$$\dfrac{\log f(n)}{\log n!} \leq \dfrac{\log f(n)}{n \log n - n + 1} \to 0 \quad (n \to \infty)$$

が言えるような　$f(n)$ を探したくなります。

そこで $\log f(n)$ が $n$ の一次式になるような $f(n)$ から検討しましょう。

$f(n) = e^n, 2^n, 2^{\frac{n}{2}}$ のような形が思い浮かぶでしょう。

制限が強い関数のほうが（数学的帰納法で強い仮定を使えるので）示しやすいことがあるため, とりあえず　$f(n) = 2^{\frac{n}{2}}$ を採用してみましょう。

$f(n) = 2^{\frac{n}{2}}$ でうまくいきましたね！

一発でうまい評価を思いつくとは限らないので, とりあえず $f(n) = 2^{n}$ を採用してみて, （評価が緩くて）うまくいかないと思ったら $f(n) = 2^{\frac{n}{2}}$ に書き換える、くらいの粘り強さが必要です。（※$f(n) = 2^{n}$ を採用しても証明は可能です。）

(2)の答案の流れは以下のようになっています。

1. （下準備）極限は $\dfrac{1}{2}$ であると目処をつける。
2. はさみうちの原理を使う前提で, $a_n$ を上下から評価できるうまい関数を探す。
3. 不等式の成立を証明する。
4. はさみうちの原理を適用する。

特にステップ1,2が難しいです。ある程度の「慣れ」が必要でしょう。

答案の途中では

$$n \sqrt{(n-1)!} = \sqrt{n} \sqrt{n!}$$

などのやや見慣れない変形を何回も用いて評価を証明していますし、

$$\sum_{k=1}^{n} \log k \geq \int_{1}^{n} \log x \, dx$$

という不等式も（有名ではあるものの）当たり前のように用いています。

いずれも「言われればそうだけど…」という等式（不等式）ではあるものの, いかにこうした引き出しを多く持っているかが試された問題であるとも言えます。

厳密な答案を作成できた方は相当な実力者です。自信を持って良いでしょう。

厳密な答案にはならなかったけれど, 答えは $\dfrac{1}{2}$ だと目をつけて正解された方も素晴らしい嗅覚の持ち主です。加えて上記の流れで完璧な答案を作成できるように目指しましょう。

なお, この問題の背景テーマは「置換」という並び替えの操作です。

「置換」は大学に入学後すぐに「線形代数」の授業で扱われるテーマのひとつで, 高校生でもその原理は簡単に理解できます。

「置換」を知っていた方は問題文への抵抗は少なかったはずです。この機会に簡単に知識を仕入れておくと良いでしょう。→置換の基礎（互換・偶置換・奇置換・符号の意味）