素敵な問題

問題15837(友人問)

次の条件を満たすように正の整数の列を書く方法は何通りあるか。

条件：最初に2012を書き、最後に1を書く。

　　　nを書いた次には√n未満の正の整数を書く。

解答

・わたしの...

[√2012]=44

[√44]=6

[√6]=2

so...

43+5+1=49通りね ^^

↑

いい加減でした ^^; Orz...

・再考...^^;

44～1・・・44

44~37=8...6～5...2～1,4～2...1・・・8*(5+2*2+3)=96

36~26=11...5...2～1,4～2...1・・・11*(4+1*2+3)=99

25~17=8...4～2...1・・・8*3=24

16~10=7...2...1・・・7*1=7

9~5=5...2...1・・・5*1=5

4~2=3...1・・・0

1・・・0

so...

44+96+99+24+7+5=275通り...かな ^^;

↑

ミスってますばい ^^; Orz...

↓

・鍵コメT様からのもの Orz～

まず，「44~37=8...6～5…2～1,4～2...1・・・8*(5+2*2+3)=96」は，
2012の直後が44～37のものについて，例えば「44」として，
・44の直後に「1」はカウント済み．
・44の次が6,5,4,3,2でその次が1のものが5通り．
・44の次が6,5で，その次が2のもの(最後は1)が2通り
の7通りだけだから，8*7=56(通り)となると思います．

「36～26」について，例えば2012の直後が36として，
・36の直後に「1」はカウント済み．
・36の次が5,4,3,2でその次が1のものが4通り．
・36の次が5で，その次が2のもの(最後は1)が1通り
の5通りだから，11*5=55(通り)です．

「25～17」について，その次は3通りでよいですが，「9*3=27(通り)」です．
「16～10」について，その次は3もあり得て，「7*2=14(通り)」です．

結局
44+56+55+27+14+5=201(通り)となると思います．

*トレースいただき光栄ですばい ^^; Orz～

私は次のようにしました．

「nの直後は√n未満」を満たす正の整数の列のうち，
最初がaで最後が1を満たすものの個数をx[a]とします．
x[1]=1,x[2]=1,x[3]=1,x[4]=1です．

最初がa(>1)だと，2番目の数は1～[√(a-1)]のいずれかであり，
また，2番目の数がmであるような列はx[m]個あります．
よって，f(a)=f(1)+f(2)+…+f([√(a-1)])です．
(上記のx[2]～x[4]も，この規則で得たものと考えることもできます．)

すると，x[5]～x[9]はすべて，x[1]+x[2]=2,
x[10]～x[16]はすべて，x[1]+x[2]+x[3]=3,
x[17]～x[25]はすべて，x[1]+x[2]+x[3]+x[4]=4,
x[26]～x[36]はすべて，x[1]+x[2]+x[3]+x[4]+x[5]=6,
x[37]～x[49]はすべて，x[1]+x[2]+x[3]+x[4]+x[5]+x[6]=8
となります．以上を用いて，
x[2012]=x[1]+x[2]+…+x[44]=1*4+2*5+3*7+4*9+6*11+8*8=201です．

*なるほどでっす!!

お気に入りぃ～^^♪