[答940] 12桁の数
[答940] 12桁の数
432123234567 のように、数字の 0 を含まず、隣り合う数字の差が1である 12桁の数の個数は?
[解答1]
隣り合う数字の差が1であるn桁の数で末位がkのものの個数を 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]
首位が偶数で末位が奇数のものと、首位が奇数で末位が偶数のものとがありますが、
逆に並べることにより1対1に対応しますので、首位が偶数で末位が奇数のものだけを考え、
2倍すると求める個数が得られます。
条件に合う 奇数桁で首位が偶数のものは末位も偶数ですが、
nを自然数として、首位が偶数で(2n-1)桁のものの個数を求めます。
4321232 と 6789878 のように、各位の数字の和が 10 になるように対応させることにより、
末位が 2 のものと 末位が 8 のものは同数で、末位が 4 のものと 末位が 6 のものは同数です。
末位が 2,4,6,8 のものの個数をそれぞれ 、an,bn,bn,an とします。
末位が 2 のものの下3桁は、212,232,432 だから、an+1=2an+bn ……(1) 、
末位が 4 のものの下3桁は、234,434,454,654 だから、bn+1=an+3bn ……(2) です。
(1)より bn=an+1-2an となり、(2)に代入して、an+2-2an+1=an+3(an+1-2an) 、an+2=5an+1-5an 、
(2)より an=bn+1-3bn となり、(1)に代入して、bn+2-3bn+1=2(bn+1-3bn)+bn 、bn+2=5bn+1-5bn 、
ここで、an+bn=cn とおけば、首位が偶数で(2n-1)桁のものの個数は 2cn で、cn+2=5cn+1-5cn です。
また、(a1,b1)=(1,1) より (a2,b2)=(3,4) 、c1=a1+b1=2 ,c2=a2+b2=7 です。
よって、c3=5c2-5c1=25 ,c4=5c3-5c2=90 ,c5=5c4-5c3=325 ,c6=5c5-5c4=1175 です。
条件に合う12桁の数は、首位も末位も偶数の11桁の 2c6 個に対し、
首位の前に1違いの奇数を付加するか、末位の後に1違いの奇数を付加すると得られるので、
4・2c6=8c6=8・1175=9400 個です。
[参考]
c1=2 ,c2=7 ,cn+2=5cn+1-5cn を解きます。
a=(5+√5)/2 ,b=(5-√5)/2 とおけば、a+b=5 ,ab=5 ,a-b=√5 ,
a3=25+10√5=(5√5)(√5+2)=(5√5)(7-2b)=(5√5)(c2-bc1) ,
b3=25-10√5=-(5√5)(-√5+2)=-(5√5)(7-2a)=-(5√5)(c2-ac1) になります。
cn+2=(a+b)cn+1-abcn より
cn+2-bcn+1=a(cn+1-bcn) 、cn+1-bcn=an-1(c2-bc1)=an+2/(5√5) 、
cn+2-acn+1=b(cn+1-acn) 、cn+1-acn=bn-1(c2-ac1)=-bn+2/(5√5) 、
差をとって、(a-b)cn=(an+2+bn+2)/(5√5) 、(√5)cn=(an+2+bn+2)/(5√5) 、cn=(an+2+bn+2)/25 です。
結局、a=(5+√5)/2 ,b=(5-√5)/2 ,cn=(an+2+bn+2)/25 として、
(2n)桁のものは 8cn 個 ,(2n+1)桁のものは 2cn+1+8cn 個です。
.