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

更新日時 2021/10/30
目次
  • 第5問[数列・極限]

第5問[数列・極限]

第5問

nn 個の区別できるボールが横一列に並んでいるとする。

全ての ii 対し,左から ii 番目にあるボールを左から kik_i 番目にうつすような操作を (123n1nk1k2k3kn1kn) \left(\begin{array}{cccccc} 1 & 2 & 3 & \cdots & n-1 & n\\ k_1 & k_2 & k_3 & \cdots & k_{n-1} & k_n \end{array}\right) と表記する。このような操作を単に「操作」と呼ぶことにする。

例えば,n=3n = 3 のとき, σ=(123231) \sigma = \left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 3 & 1 \end{array}\right) で表される操作 σ\sigma は,左端のボールを中央に,中央のボールを右端に,右端のボールを左端に動かす操作である。

自然数 nn に対し,「ちょうど2回行うとボールの並びが元の並びと同じになる」という条件を満たす操作の個数を ana_n とおく。

例えば,n=3n = 3 のとき, τ=(123213) \tau = \left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 1 & 3 \end{array}\right) で表される操作 τ\tau は条件を満たすが, σ=(123231) \sigma = \left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 3 & 1 \end{array}\right) で表される操作 σ\sigma は条件を満たさない。

(1) n3n \geq 3 のとき,ana_nan1a_{n-1}an2a_{n-2} を用いて表せ。

(2) limnloganlogn! \lim_{n \to \infty} \dfrac{\log a_n}{\log n!}

を求めよ。

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

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

以下の操作 σ\sigma

σ=(123231) \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 は上記の条件を満たしていることがわかります。

τ=(123213) \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]

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

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

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

  • ボールが nn 個並んでいるとき
  • ボールが n1n-1 個並んでいるとき
  • ボールが n2n-2 個並んでいるとき

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

第5問(1)

以下「ちょうど2回行うとボールの並びが元の並びと同じになる」という条件を条件(*)と表す。

条件(*)を満たす操作のうち,

①左端のボールを動かさない操作の個数を bnb_n

②左端のボールを動かす操作の個数を cnc_n

とおくと, an=bn+cna_n = b_n + c_n である。

  • ①について

bnb_n は, 左から22番目〜 nn 番目に並ぶ n1n-1 個のボールについて条件(*)を満たす操作の個数に等しいので,

bn=an1 b_n = a_{n-1} である。

  • ②について

②の場合, 操作 σ\sigma は自然数 m(=2,3,,n)m \, (= 2, 3, \cdots , n) を用いて

σ=(123n1nmk2k3kn1kn) \sigma = \left(\begin{array}{cccccc} 1 & 2 & 3 & \cdots & n-1 & n\\ m & k_2 & k_3 & \cdots & k_{n-1} & k_n \end{array}\right) と表記できる。

2回の操作 σ\sigma に対して, 左端のボールは左から1番目 \to mm 番目 \to kmk_m 番目 と動くので, 操作 σ\sigma が条件(*)を満たすための必要条件は km=1 k_m = 1 である。

すなわち, 操作 σ\sigmaσ=(12m1mm+1nmk2km11km+1kn) \sigma = \left(\begin{array}{cccccc} 1 & 2 & \cdots & m-1 & m & m+1 & \cdots & n\\ m & k_2 & \cdots & k_{m-1} & 1 & k_{m+1} & \cdots & k_n \end{array}\right) と表される。

操作 σ\sigma が条件(*)を満たすための必要十分条件は, 左から1番目と mm 番目を無視した n2n-2 個のボールについて条件(*)を満たすことである。

自然数 mm の選び方が n1n-1 通りあることに注意すると, cnc_n

cn=(n1)an2 c_n = (n-1) \cdot a_{n-2}

と表される。

以上から an=an1+(n1)an2 a_n = a_{n-1} + (n-1)a_{n-2} である。

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

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

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

ここを足がかりにして,

cn=(n1)an2 c_n = (n-1) \cdot a_{n-2}

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

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

(2)言い換え

以下の数列 ana_n

an={1(n=1)2(n=2)an1+(n1)an2(n3) a_n = \begin{cases} 1 \quad (n = 1)\\ 2 \quad (n = 2) \\ a_{n-1} + (n-1)a_{n-2} \quad (n \geq 3) \\ \end{cases}

に対して, 極限

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

を求めよ。

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

  • n=1n=1の場合

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

  • n=2n=2の場合

σ=(1212),(1221) \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\log が出てくるのか?

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

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

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

はさみうちの原理(数列版)

任意の自然数 nn に対して(または十分大きな nn に対して)

anbncn a_n \leq b_n \leq c_n

が成立し,

limnan=limncn=α \lim_{n\to\infty}a_n=\lim_{n\to\infty}c_n=\alpha

なら

limnbn=α \lim_{n\to\infty}b_n=\alpha

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

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

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

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

すなわち, ana_nn!n! はどれくらい値が近い(or 遠い)のかを調べてみます。

極限

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

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

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

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

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

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

ann!a_n \leq n!

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

さて, このような実数 cc は存在するのでしょうか?

(2)下準備(答案には含めない)

nn が十分大きいとき, ある実数 c (0c1)c \ (0 \leq c \leq 1) を用いて

an(n!)can1{(n1)!}can2{(n2)!}c \begin{aligned} & a_{n} \fallingdotseq (n!)^c \\ & a_{n-1} \fallingdotseq \left\{(n-1)!\right\}^c \\ & a_{n-2} \fallingdotseq \left\{(n-2)!\right\}^c \\ \end{aligned}

と表されることを期待する。

このとき

an=an1+(n1)an2{(n1)!}c+(n1){(n2)!}c={(n1)c+(n1)}{(n2)!}c \begin{aligned} a_n &= a_{n-1} + (n-1)a_{n-2} \\ & \fallingdotseq \left\{(n-1)!\right\}^c + (n-1) \left\{(n-2)!\right\}^c \\ & = \left\{(n-1)^c + (n-1) \right\} \left\{(n-2)!\right\}^c \\ \end{aligned}

より,

{(n1)c+(n1)}{(n2)!}c(n!)c    (n1)c+n1nc(n1)c    1+(n1)1cnc \begin{aligned} & \left\{(n-1)^c + (n-1) \right\} \left\{(n-2)!\right\}^c \fallingdotseq (n!)^c \\ & \iff (n-1)^c + n - 1 \fallingdotseq n^c (n-1)^c \\ & \iff 1 + (n - 1)^{1-c} \fallingdotseq n^c \\ \end{aligned}

である。nn が十分大きいので

(n1)1cnc1 (n - 1)^{1-c} \fallingdotseq n^c \gg 1

の関係が成り立っていることを期待すると, 1c=c1-c=cより

c=12 c = \dfrac{1}{2}

であると検討がつく。

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

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

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

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

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

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

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

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

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

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

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

12=limnlogn!logn!limnloganlogn! \dfrac{1}{2} = \lim_{n \to \infty} \dfrac{\log \sqrt{n!}}{\log n!} \leq \lim_{n \to \infty} \dfrac{\log a_n}{\log n!}

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

上側はどうでしょうか?

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

limnloganlogn!limnlog{f(n)n!}logn!=12+limnlogf(n)logn! \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!}

となるので,

{anf(n)n!logf(n)logn!0(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)f(n) が見つかれば嬉しいです。

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

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

までわかってしまえば,

logf(n)logn!logf(n)nlognn+10(n) \dfrac{\log f(n)}{\log n!} \leq \dfrac{\log f(n)}{n \log n - n + 1} \to 0 \quad (n \to \infty)

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

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

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

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

第5問(2)

まず

n!an2n2n!(A) \sqrt{n!} \leq a_n \leq 2^{\frac{n}{2}} \sqrt{n!} \tag{A} を数学的帰納法で示す。

(i) n=1,n=2n=1, n=2 のとき

a1=1,a2=2a_1 = 1, a_2 = 2 に対して, (A)(\mathrm{A}) は成り立つ。

(ii) n2,n1n-2, n-1 (n3n \geq 3) で (A)(\mathrm{A}) が成り立つとき

まず ann!a_n \geq \sqrt{n!} を示す。

仮定より,

an=an1+(n1)an2(n1)!+(n1)(n2)!=(1+n1)(n1)! \begin{aligned} a_n &= a_{n-1} + (n-1)a_{n-2} \\ & \geq \sqrt{(n-1)!} + (n-1)\sqrt{(n-2)!} \\ &= (1+\sqrt{n-1})\sqrt{(n-1)!} \end{aligned}

であり,

(1+n1)2=n+2n1n (1+\sqrt{n-1})^2 = n + 2 \sqrt{n-1} \geq n

であるから,

(1+n1)(n1)!n(n1)!=n! (1+\sqrt{n-1})\sqrt{(n-1)!} \geq \sqrt{n} \sqrt{(n-1)!} = \sqrt{n!}

が成り立つ。よって, ann!a_n \geq \sqrt{n!} が成り立つ。

次に an2n2n!a_n \leq 2^{\frac{n}{2}} \sqrt{n!} を示す。

仮定より,

an=an1+(n1)an22n12(n1)!+(n1)2n22(n2)!=2n22(n1)!(2+n1) \begin{aligned} a_n &= a_{n-1} + (n-1)a_{n-2} \\ & \leq 2^{\frac{n-1}{2}} \sqrt{(n-1)!} + (n-1) \cdot 2^{\frac{n-2}{2}} \sqrt{(n-2)!} \\ &= 2^{\frac{n-2}{2}} \sqrt{(n-1)!} (\sqrt{2} + \sqrt{n-1}) \end{aligned}

であり,

(2n)2(2+n1)2=4n(2+2n1+n1)=3n12n12(n1)2(n1)0 \begin{aligned} & (2\sqrt{n})^2 - (\sqrt{2} + \sqrt{n-1})^2 \\ &= 4n - (2 + \sqrt{2}\sqrt{n-1} + n-1) \\ &= 3n - 1 - \sqrt{2}\sqrt{n-1} \\ & \geq 2(n-1) - \sqrt{2(n-1)} \\ & \geq 0 \end{aligned}

であるから,

2n22(n1)!(2+n1)2n22(n1)!2n=2n2n! \begin{aligned} & 2^{\frac{n-2}{2}} \sqrt{(n-1)!} (\sqrt{2} + \sqrt{n-1}) \\ & \leq 2^{\frac{n-2}{2}} \sqrt{(n-1)!} \cdot 2\sqrt{n} = 2^{\frac{n}{2}} \sqrt{n!} \end{aligned}

が成り立つ。よって, an2n2n!a_n \leq 2^{\frac{n}{2}} \sqrt{n!} が成り立つ。

以上(i)(ii)より, an(n1)a_n \, (n \geq 1) に対して (A)(\mathrm{A}) が成り立つ。

(A)(\mathrm{A}) の辺々に対して自然対数をとると,

n!an2n2n!    12logn!logan12logn!+n2log2    12loganlogn!12+nlog22logn!(B) \begin{aligned} & \sqrt{n!} \leq a_n \leq 2^{\frac{n}{2}} \sqrt{n!} \\ & \iff \dfrac{1}{2} \log n! \leq \log a_n \leq \dfrac{1}{2} \log n! + \dfrac{n}{2} \log 2 \\ & \iff \dfrac{1}{2} \leq \dfrac{\log a_n}{\log n!} \leq \dfrac{1}{2} + \dfrac{n \log 2}{2 \log n!} \tag{B} \end{aligned}

が成り立つ。

ここで, 下図より

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

が成り立つ。

log x の評価

したがって,

logn!=k=1nlogk1nlogxdx=[xlogxx]1n=nlognn+1n(logn1) \begin{aligned} \log n! &= \sum_{k=1}^{n} \log k \\ & \geq \int_{1}^{n} \log x \, dx \\ &= \left[ x \log x - x \right]_{1}^{n} \\ &= n \log n - n + 1 \\ & \geq n (\log n - 1) \end{aligned}

であるから,

limnnlog22logn!limnnlog22n(logn1)=limnlog22(logn1)=0 \begin{aligned} & \lim_{n \to \infty} \dfrac{n \log 2}{2 \log n!} \\ & \leq \lim_{n \to \infty} \dfrac{n \log 2}{2 n (\log n - 1)} \\ &= \lim_{n \to \infty} \dfrac{\log 2}{2 (\log n - 1)} \\ &= 0 \end{aligned}

である。

したがって, (B)(\mathrm{B})nn \to \infty とすると, はさみうちの原理により,

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

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

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

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

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

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

答案の途中では

n(n1)!=nn! n \sqrt{(n-1)!} = \sqrt{n} \sqrt{n!}

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

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

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

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

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

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

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

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

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

配点 25点

(1)

[5点]

an1=p,an2=qa_{n-1} = p, a_{n-2} = q として,

p+nqq p + nq - q pq+nq p - q + nq nq+pq nq + p - q nqq+p nq - q + p q+p+nq -q + p + nq q+nq+p -q + nq + p

(2)

[20点] 12 \dfrac{1}{2}

平均点 (1) (2)
X - - -
Y - - -
Z 8.6 2.0 6.5