陥没地帯 (234) - ノリの悪い日記

$1996$ 年の京大理系の問題.

【問】
与えられた自然数 $k$ に対し, 数列 $\{a_n\}$ を

$a_1 = 0$ , $\displaystyle{a_n = \left\lfloor \frac{a_{n-1} + k}{3}\right\rfloor}$ $(n \geq 2)$

によって定める. ただし実数 $t$ に対し, $\lfloor t \rfloor$ は $t$ を超えない最大の整数を表す.

$(1)$ $k = 8$ および $k = 9$ のとき, 数列 $\{a_n\}$ を求めよ.

$(2)$ すべての自然数 $n$ に対し, 次の $2$ つの不等式

$\displaystyle{a_n \leq \frac{k - 1}{2}}$ , $a_n \leq a_{n + 1}$

が成り立つことを示せ.

$(3)$ $a_n = a_{n + 1}$ ならば, $n$ 以上のすべての整数 $m$ に対し, $a_n = a_m$ であることを示し, このときの $a_n$ の値を求めよ.

【解】
$(1)$
$k = 8$ のとき:

$a_1= 0$ ,
$\displaystyle{a_2 = \left\lfloor \frac{8}{3}\right\rfloor = 2}$ ,
$\displaystyle{a_3 = \left\lfloor \frac{10}{3}\right\rfloor = 3}$ ,
$\displaystyle{a_4 = \left\lfloor \frac{11}{3}\right\rfloor = 3}$

$n \geq 3$ のとき, $a_n = 3$

$k = 9$ のとき:

$a_1= 0$ ,
$\displaystyle{a_2 = \left\lfloor \frac{9}{3}\right\rfloor = 3}$ ,
$\displaystyle{a_3 = \left\lfloor \frac{12}{3}\right\rfloor = 4}$ ,
$\displaystyle{a_4 = \left\lfloor \frac{13}{3}\right\rfloor = 4}$

$n \geq 3$ のとき, $a_n = 4$

$(2)$
まず, $a_n \leq a_{n+1}$ が成立することを数学的帰納法で示す. なお, $f(x) = \lfloor x \rfloor$ は, 単調増加関数である. (なぜなら, $x_2 > x_1$ であれば,

$\begin{align} \lfloor x_2\rfloor &> x_2-1\\&> x_1-1 \\&\geq \lfloor x_1 \rfloor -1\end{align}$

から, $\lfloor x_2\rfloor + 1 > \lfloor x_1 \rfloor$ となり, $\lfloor x_1\rfloor$ , $\lfloor x_2\rfloor$ は整数なので, $\lfloor x_2\rfloor \geq \lfloor x_1 \rfloor$ となるからである.)

$k$ は自然数だから,

$\displaystyle{0 < \frac{k}{3}}$

で, したがって,

$\displaystyle{0 \leq \left\lfloor \frac{k}{3} \right\rfloor}$

となる. つまり, $a_1 \leq a_2$ が成立する.

$a_k \leq a_{k+1}$ と仮定すると,

$\displaystyle{\frac{a_k + k}{3} \leq \frac{a_{k+1} + k}{3}}$

から,

$\displaystyle{ \left\lfloor\frac{a_k + k}{3} \right\rfloor \leq \left\lfloor \frac{a_{k+1} + k}{3} \right\rfloor}$

となる. したがって, $a_{k + 1} \leq a_{k + 2}$ が成立する.

以上から, $a_n \leq a_{n+1}$ が成立する.

次に,

$\displaystyle{a_n > \frac{k - 1}{2}}$ ( $k$ は自然数)

となる自然数 $n$ がある $k$ で存在したと仮定し, その最小のものを $n'$ ( $> 1$ ) とする. 先ほどの結論から,

$\displaystyle{a_{n'} \leq a_{n'+1} = \left\lfloor \frac{a_{n'} + k}{3} \right\rfloor}$

であるが,

$\begin{align} \left\lfloor \frac{a_{n'} + k}{3} \right\rfloor \leq \frac{1}{3}(a_{n'} + k) \end{align}$

から,

$\begin{align} a_{n'} \leq \frac{1}{3}(a_{n'} + k) \end{align}$

となり, これと仮定から,

$k-1 < 2a_{n'} \leq k$

となる. $2a_{n'}$ は整数だから,

$2a_{n'} = k$

とわかる ( $k$ は偶数である).

ところが,

$\begin{align} a_{n'} &= \left\lfloor \frac{a_{n'-1} + k}{3}\right\rfloor\\ &\leq \frac{1}{3}(a_{n' -1} + k) \end{align}$

から,

$\begin{align} \frac{k}{2} \leq \frac{1}{3}(a_{n' -1} + k) \end{align}$

で,

$\displaystyle{a_{n'-1} \geq \frac{k}{2} > \frac{k - 1}{2}}$

となり, $n'$ は, $a_n > (k - 1)/2$ となる自然数の最小値であったことに矛盾する. したがって, 任意の自然数 $n$ に対して, $a_n \leq (k - 1)/2$ となる.

$(3)$
$i$ を自然数とし, $m = n + i$ とおく.

$i = 1$ のとき, 問の条件から, $a_{n +1} = a_{n}$ が成立.

$i = j$ で $a_{n + j} = a_n$ と仮定すると,

$\begin{align} a_{n + j + 1} &= \left\lfloor \frac{a_{n+ j} + k}{3} \right\rfloor\\ &= \left\lfloor \frac{a_n + k}{3} \right\rfloor\\ &= a_{n +1} \\ &= a_{n} \end{align}$