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

各桁に1か2がくることを考えると，$2^4 = 16$ 通りである。

偶数であるのは1の位の数が2のときである。そのため，1の位を除く部分 $n-1$ 個は自由に取ることができる。したがって $2^{n-1}$ 通りである。

3の倍数の個数を $a_n$ とおく。

3で割って1余る整数の個数を $b_n$ とおく。3で割って2余る整数の個数もまた $b_n$ になる。（詳細な証明は後述する。）

1と2を合わせて $n+1$ 個並べたものが3の倍数となるのは，3で割って1余る整数の後ろに2を付けたもの場合と，3で割って2余る整数の後ろに1を付けた場合になる。ゆえに $a_{n+1} = b_n + b_n = 2b_n$ が従う。

1と2を合わせて $n+1$ 個並べたものが3で割って1余る整数となるのは，3で割って2余る整数の後ろに2を付けたもの場合と，3の倍数の後ろに1を付けた場合になる。ゆえに $b_{n+1} = b_n + a_n$ が従う。

こうして連立漸化式

$$\begin{aligned}\begin{cases} a_{n+1} = 2b_n\\ b_{n+1} = a_n +b_n \end{cases}\end{aligned}$$ が得られる。なお，1か2を1つ並べたとき，3の倍数は作られず，3で割って1余る整数は1の1通りであることから $a_1 = 0,b_1=1$ が従っている。

1つ目の式を用いることで2つ目の式は $$\dfrac{1}{2} a_{n+2} = a_n + \dfrac{1}{2} a_{n+1}$$ となる。整理すると $$a_{n+2} -a_{n+1} -2 a_n=0$$ が得られる。なお，$a_1 = 0, a_2 = 2$ である。

三項間漸化式を解くと，

$$a_n = \dfrac{2^n + 2\cdot (-1)^n}{3}$$

が得られる。

1が $m$ 個，2が $n-m$ 個並んだ整数 $N$ が3で割って1余る整数のとき，1と2を入れ替えた整数 $N'$ は3で割って2余る整数となることを示す。これを示すことで3で割って1余る整数と3で割って2余る整数が1対1に対応することが従うため，証明が完了する。

正の整数の各位の和を3で割った余りと，元の整数を3で割った余りは一致する。実際，$m$ 桁の整数 $n$ を $\displaystyle n = \sum_{k=0}^m a_{k} 10^{k}$ （ただし各 $a_k$ は0以上9以下の整数）と表される場合， $$\begin{aligned} n &= \sum_{k=0}^m a_{k} 10^{k}\\ &= \sum_{k=0}^m a_{k} \{(10^{k}-1) +1 \}\\ &= \sum_{k=0}^m a_{k} (10^{k}-1) + \sum_{k=0}^m a_k \end{aligned}$$ となる。1項目は3の倍数であるため，$n$ を3で割った余りは2項目，すなわち各位の和を3で割った余りと一致する。

$N$ の各位の和は $m + 2(n-m) = 2n-m$ である。$N'$ の各位の和は $(n-m) + 2m = n+m$ である。$(2n-m) + (n+m) = 3n$ である。

$N$ が3で割って1余るとき，$2n-m$ も3で割って1余る。このとき $n+m$ は3で割って2余整数になる。したがって，$N'$ は3で割って2余る整数となる。以上より証明された。

1と2を $n$ 個並べたときの3で割って2余る整数の個数を $c_n$ とおく。

1と2を合わせて $n+1$ 個並べたものが3の倍数となるのは，3で割って1余る整数の後ろに2を付けたもの場合と，3で割って2余る整数の後ろに1を付けた場合になる。ゆえに $a_{n+1} = b_n + c_n = b_n + c_n$ が従う。

同様に考えることで，次の漸化式が成り立つ。

$$\begin{cases} a_{n+1} = b_n + c_n\\ b_{n+1} = c_n + a_n\\ c_{n+1} = a_n + b_n \end{cases}$$ なお， $a_1 = 0, b_1=1,c_1=1$ である。

数学的帰納法により $b_n=c_n$ を示す。$n=1$ のときはすでに計算されている。

$n=k$ での成立を仮定すると，$b_k = c_k$ となる。漸化式より $b_{k+1} = c_k + a_k = b_k +a_k =c_{k+1}$ が従う。こうして $n=k+1$ のときにも成立することが分かり，任意の $n$ で $b_n = c_n$ となることが示された。

求めるものを $d_n$ とおく。

1の位は1か2であるため，5の倍数が得られることはない。

よって最小の素因数が7以上になるのは，2でも3でも割り切れないときである。したがって $2^n$ から2か3で割り切れる整数の個数を引けばよい。

2で割り切れる整数，すなわち偶数は，(2)より $2^{n-1}$ 通りある。3で割り切れる整数，すなわち3の倍数の個数は(3)で求めた。これらの和から2でも3でも割り切れる整数，すなわち6の倍数の個数を引けば，2か3で割り切れる整数の個数が得られる。

6で割り切れる整数は，3で割り切れる整数のうち，下1桁が2のときである。下1桁を除いた $n-1$ 桁の整数は3で割って1余る整数となる。したがって，1と2を $n$ 個並べた整数のうち6の倍数の個数は，$b_{n-1}= \dfrac{2^n + 2\cdot (-1)^n}{6}$ である。

よって $$\begin{aligned} d_n &= 2^n - \left\{ \left(2^{n-1} + \dfrac{2^n + 2\cdot (-1)^n}{3} \right) -\dfrac{2^n + 2\cdot (-1)^n}{6} \right\}\\ &= 2^{n-1} - \dfrac{2^n + 2\cdot (-1)^n}{6}\\ &= \dfrac{2^{n} - (-1)^{n}}{3} \end{aligned}$$ である。