|
ある８ケタの整数があります。
この整数を、左から何ケタ目で区切ったとしても、区切りの左側の整数は、左から偶数番目の整数の合計と、奇数番目の整数の合計について、その差が１以下になっている。
例えば４ケタの数であれば、例えば１２２１は、区切る位置が、
左から１ケタ目のとき → １ なので成立
左から２ケタ目のとき → １２ なので、２−１＝１で成立
左から３ケタ目のとき → １２２ なので、（１＋２）ー２＝１で成立
左から４ケタ目のとき → １２２１なので、（１＋２）ー（２＋１）＝０で成立
というわけで、条件を満たします。
では、このような８ケタの整数は、何通り考えられるでしょうか。
掲示板の漸化式がわからない。
|
No.23204 2025/05/29(Thu) 21:04:26
|
☆ Re: 奇数偶数に関係なく交代和のみで漸化式を？ / らすかる |
|
|
|
n桁の整数で「右から」奇数番目の桁の合計をO、
偶数番目の桁の合計をEとしたとき、
O-E=-1となる整数の個数をa[n]
O-E=0となる整数の個数をb[n]
O-E=1となる整数の個数をc[n]
とすると
a[n]個に含まれる整数に0を追加するとc[n+1]個に含まれる整数となり、
a[n]個に含まれる整数に1以上を追加すると条件を満たさず、
b[n]個に含まれる整数に0を追加するとb[n+1]個に含まれる整数となり、
b[n]個に含まれる整数に1を追加するとc[n+1]個に含まれる整数となり、
b[n]個に含まれる整数に2以上を追加すると条件を満たさず、
c[n]個に含まれる整数に0を追加するとa[n+1]個に含まれる整数となり、
c[n]個に含まれる整数に1を追加するとb[n+1]個に含まれる整数となり、
c[n]個に含まれる整数に2を追加するとc[n+1]個に含まれる整数となり、
c[n]個に含まれる整数に3以上を追加すると条件を満たさない。
またa[1]=b[1]=0,c[1]=1だから、
a[1]=b[1]=0, c[1]=1
a[n+1]=c[n]
b[n+1]=b[n]+c[n]
c[n+1]=a[n]+b[n]+c[n]
という漸化式が立てられる。
これにより順次計算すると
左からn:a[n],b[n],c[n]として
1:0,0,1
2:1,1,1
3:1,2,3
4:3,5,6
5:6,11,14
6:14,25,31
7:31,56,70
8:70,126,157
よって求める答えは
70+126+157=353通り。
|
No.23205 2025/06/02(Mon) 16:22:45
|
|
