|
ある8ケタの整数があります。
この整数を、左から何ケタ目で区切ったとしても、区切りの左側の整数は、左から偶数番目の整数の合計と、奇数番目の整数の合計について、その差が1以下になっている。
例えば4ケタの数であれば、例えば1221は、区切る位置が、
左から1ケタ目のとき → 1 なので成立 左から2ケタ目のとき → 12 なので、2−1=1で成立 左から3ケタ目のとき → 122 なので、(1+2)ー2=1で成立 左から4ケタ目のとき → 1221なので、(1+2)ー(2+1)=0で成立
というわけで、条件を満たします。
では、このような8ケタの整数は、何通り考えられるでしょうか。 掲示板の漸化式がわからない。
|
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
|
|