[答940] 12桁の数

[答940] 12桁の数


　432123234567 のように、数字の 0 を含まず、隣り合う数字の差が１である 12桁の数の個数は？


[解答1]

　隣り合う数字の差が１であるｎ桁の数で末位がｋのものの個数を a(n，k) とし、

　a(n，0)＝a(n，10)＝0 と定義すれば、a(n＋1，k)＝a(n，k－1)＋a(n，k＋1) なので、

　単純に 表を作れば 上記のようになり 9400個です。

　もちろん、a(n，k)＝a(n，10－k) を利用すれば、もう少し能率よくなります。


[解答2]

　首位が偶数で末位が奇数のものと、首位が奇数で末位が偶数のものとがありますが、

　逆に並べることにより１対１に対応しますので、首位が偶数で末位が奇数のものだけを考え、

　２倍すると求める個数が得られます。

　条件に合う 奇数桁で首位が偶数のものは末位も偶数ですが、

　ｎを自然数として、首位が偶数で(2n－1)桁のものの個数を求めます。

　4321232 と 6789878 のように、各位の数字の和が 10 になるように対応させることにより、

　末位が 2 のものと 末位が 8 のものは同数で、末位が 4 のものと 末位が 6 のものは同数です。

　末位が 2，4，6，8 のものの個数をそれぞれ 、a_n，b_n，b_n，a_n とします。

　末位が 2 のものの下３桁は、212，232，432 だから、a_n+1＝2a_n＋b_n ……(1) 、

　末位が 4 のものの下３桁は、234，434，454，654 だから、b_n+1＝a_n＋3b_n ……(2) です。

　(1)より b_n＝a_n+1－2a_n となり、(2)に代入して、a_n+2－2a_n+1＝a_n＋3(a_n+1－2a_n) 、a_n+2＝5a_n+1－5a_n 、

　(2)より a_n＝b_n+1－3b_n となり、(1)に代入して、b_n+2－3b_n+1＝2(b_n+1－3b_n)＋b_n 、b_n+2＝5b_n+1－5b_n 、

　ここで、a_n＋b_n＝c_n とおけば、首位が偶数で(2n－1)桁のものの個数は 2c_n で、c_n+2＝5c_n+1－5c_n です。

　また、(a₁，b₁)＝(1，1) より (a₂，b₂)＝(3，4) 、c₁＝a₁＋b₁＝2 ，c₂＝a₂＋b₂＝7 です。

　よって、c₃＝5c₂－5c₁＝25 ，c₄＝5c₃－5c₂＝90 ，c₅＝5c₄－5c₃＝325 ，c₆＝5c₅－5c₄＝1175 です。

　条件に合う12桁の数は、首位も末位も偶数の11桁の 2c₆ 個に対し、

　首位の前に１違いの奇数を付加するか、末位の後に１違いの奇数を付加すると得られるので、

　4･2c₆＝8c₆＝8･1175＝9400 個です。


[参考]

　c₁＝2 ，c₂＝7 ，c_n+2＝5c_n+1－5c_n を解きます。

　a＝(5＋√5)/2 ，b＝(5－√5)/2 とおけば、a＋b＝5 ，ab＝5 ，a－b＝√5 ，

　a³＝25＋10√5＝(5√5)(√5＋2)＝(5√5)(7－2b)＝(5√5)(c₂－bc₁) ，

　b³＝25－10√5＝－(5√5)(－√5＋2)＝－(5√5)(7－2a)＝－(5√5)(c₂－ac₁) になります。

　c_n+2＝(a＋b)c_n+1－abc_n より

　c_n+2－bc_n+1＝a(c_n+1－bc_n) 、c_n+1－bc_n＝a^n-1(c₂－bc₁)＝aⁿ⁺²/(5√5) 、

　c_n+2－ac_n+1＝b(c_n+1－ac_n) 、c_n+1－ac_n＝b^n-1(c₂－ac₁)＝－bⁿ⁺²/(5√5) 、

　差をとって、(a－b)c_n＝(aⁿ⁺²＋bⁿ⁺²)/(5√5) 、(√5)c_n＝(aⁿ⁺²＋bⁿ⁺²)/(5√5) 、c_n＝(aⁿ⁺²＋bⁿ⁺²)/25 です。

　結局、a＝(5＋√5)/2 ，b＝(5－√5)/2 ，c_n＝(aⁿ⁺²＋bⁿ⁺²)/25 として、

　(2n)桁のものは 8c_n 個 ，(2n＋1)桁のものは　2c_n+1＋8c_n 個です。

.