[math]1991年東京工業大学後期数学問題1

問題
方針
解答
解説
関連問題
関連リンク

問題

$10$進法表示の$n$桁の正の整数で、隣り合う桁の数字が互いに相異なるような数の個数を$a_n$とするとき、次の問いに答えよ。
$(1)$ $a_n$を求めよ。
$(2)$ 上の数のうちで、$1$の位の数字が$0$である数の個数を$b_n$とするとき、$\displaystyle \lim_{n\to\infty}{\frac{b_n}{a_n}}$を求めよ。

方針

$(2)$ 漸化式を立てる。

解答

$(1)$ 一番上の位は$1$から$9$までの中から一つ選び、それ以降の桁は$0$から$9$までの中から、一つ上の位と異なる数字を選べば良いので、$a_n = 9\cdot 9^{n-1} = \underline{9^n}$である。

$(2)$ $n+2$桁の数で、隣り合う桁の数字が互いに相異なり、$1$の位が$0$のもので、$100$の位が$0$かどうかで場合分けして考える。
$(i)$ $100$の位が$0$のとき、$10$の位と$1$の位の数を無視して考えると、このような$n$桁の数は$b_n$個あり、$10$の位に$1$から$9$までの数で好きなもの、$1$の位に$0$を置くと$b_{n+2}$が構成できる。$$\begin{eqnarray}&& 14350\bigcirc\bigcirc\\ && 143503\bigcirc \\ &&1435030\end{eqnarray}$$上の例では、$100$の位が$0$である数の、$10$の位に$3$を置き、$1$の位に$0$を置いて$b_{n+2}$を構成している。このような数の個数は$9b_n$個ある。
$(ii)$ $100$の位が$0$以外のとき、$10$の位は無視して、$1$の位に$0$を置く。このような数の作り方は$b_{n+1}$通りである。$10$の位に、$100$の位と異なる数字を選び入れると、これは$b_{n+2}$を構成している。このような数の個数は$8b_{n+1}$個である。

$(i), (ii)$から、$b_{n+2} = 8b_{n+1}+9b_{n}$が分かる。また、$1$桁の数で隣り合う桁が異なり、末尾が$0$のものはないので、$b_1 = 0$である。$2$桁の数で隣り合う桁が異なり、$1$の位が$0$のものは$10, 20, \cdots, 90$の$9$個であるから、$b_2 = 9$である。$b_{n+2} = 8b_{n+1}+9b_n$の特性方程式$t^2=8t+9$を解くと、$t = -1, 9$であるから、$b_n = \alpha(9)^{n-1}+ \beta(-1)^{n-1}$と置ける。$$\begin{cases}b_1 = \alpha+\beta = 0\\ b_2 = 9\alpha-\beta = 9\end{cases}$$だから、$\displaystyle \alpha = \frac{9}{10}, \beta = -\frac{9}{10}$である。したがって、$\displaystyle b_n = \frac{9^n+9\cdot (-1)^n}{10}$である。以上から、$\displaystyle \lim_{n\to\infty}{\frac{b_n}{a_n}} = \underline{\frac{1}{10}}$となる。

解説

桁数の問題では頭かお尻、つまり一番高い位か低い位に着目すると良い。この問題の場合、$1$の位が$0$だと$10$の位は$0$にならないので、$100$の位まで考える必要があり、三項間漸化式を持ち出すことになる。三項間漸化式の解き方と特性方程式については、関連問題の東京医科歯科大学の問題を参照すると良い。