7150:10個の異なる数の最小値が最大になる場合...

イメージ 2

問題7150・・・浮浪さんの「浮浪の館」http://www.geocities.jp/hagure874/ より Orz~

イメージ 1


































解答

上記サイトより Orz~

イメージ 3


・わたしの…

難しかったぁ…^^;

67*10+45=715 なので…
A=66
714-660=54
54-9=45
45を異なる9個への分け方…1通り…
53-2*8=37の異なる8個への分け方…45-9=36 なので…1通り
54-3-3*7=30の異なる7個への分け方…36-8=28 なので…2通り
54-6-4*6=24の6個への分け方…28-7=21 なので…3通り
54-10-5*5=19の5個への分け方…21-6=15なので…5通り
54-15-6*4=15の4個への分け方…15-5=10なので…6通り
54-21-7*3=12の3個への分け方…10-4=6なので…7通り
54-28-8*2=10の2個への分け方…6-3=3なので…4通り
54-36-9*1=9 の1個への分け方…3-2=1なので…1通り
合計=30


・なかさんのもの Orz~

a=67 では 714を超えます。
a=66 のとき、
最小の10個の和は、66+67+68+.......+75 = 705
であと9余裕があります。
単調非減少の9個の自然数の和が9となるのは、
以下のように30通りあると思いますが?

( 1 ) 0 0 0 0 0 0 0 0 9 
( 2 ) 0 0 0 0 0 0 0 1 8 
( 3 ) 0 0 0 0 0 0 0 2 7 
( 4 ) 0 0 0 0 0 0 0 3 6 
( 5 ) 0 0 0 0 0 0 0 4 5 
( 6 ) 0 0 0 0 0 0 1 1 7 
( 7 ) 0 0 0 0 0 0 1 2 6 
( 8 ) 0 0 0 0 0 0 1 3 5 
( 9 ) 0 0 0 0 0 0 1 4 4 
( 10 ) 0 0 0 0 0 0 2 2 5 
( 11 ) 0 0 0 0 0 0 2 3 4 
( 12 ) 0 0 0 0 0 0 3 3 3 
( 13 ) 0 0 0 0 0 1 1 1 6 
( 14 ) 0 0 0 0 0 1 1 2 5 
( 15 ) 0 0 0 0 0 1 1 3 4 
( 16 ) 0 0 0 0 0 1 2 2 4 
( 17 ) 0 0 0 0 0 1 2 3 3 
( 18 ) 0 0 0 0 0 2 2 2 3 
( 19 ) 0 0 0 0 1 1 1 1 5 
( 20 ) 0 0 0 0 1 1 1 2 4 
( 21 ) 0 0 0 0 1 1 1 3 3 
( 22 ) 0 0 0 0 1 1 2 2 3 
( 23 ) 0 0 0 0 1 2 2 2 2 
( 24 ) 0 0 0 1 1 1 1 1 4 
( 25 ) 0 0 0 1 1 1 1 2 3 
( 26 ) 0 0 0 1 1 1 2 2 2 
( 27 ) 0 0 1 1 1 1 1 1 3 
( 28 ) 0 0 1 1 1 1 1 2 2 
( 29 ) 0 1 1 1 1 1 1 1 2 
( 30 ) 1 1 1 1 1 1 1 1 1 

和がmとなる、1以上k以下の自然数の足し算が a(m,k) 通りあるとします。
ただし、足し算の順番だけが異なるものは区別しないこととします。

便宜上、a(0,k)=1 () とします
a(m,1)=1 (m)です。

a(1,1)=1 (1)
a(2,1)=1 (1+1)
a(2,2)=2 (1+1),(2)
a(3,1)=1 (1+1+1)
a(3,2)=2 (1+1+1),(2+1) という具合です。

さて、a(7,4)の例を考えて見ましょう、(下図の丸囲み数字参照)
 4 を使わないものが,a(7,3) = 8
 4 を使うものが,a(7-4,4) = 3、合わせて 11通りです。

一般に
 ⅰ) m<k のとき a(m,k)=a(m,k-1)
 ⅱ) m≧k のとき a(m,k)=a(m,k-1)+a(m-k,k)
となります。

a(m,k)の表は下のようになります。行が「和」です。

イメージ 4
a(9,9)=30 です。ちなみに、 a(9,8) が 29でした。


*a(n,n)はいわゆる整数分割数そのものですよね?
a(n,n+k)=a(n,n) になるしかないし...
[LINK]分割数より...
p(1) = 1
p(2) = 2
p(3) = 3
p(4) = 5
p(5) = 7
p(6) = 11
p(7) = 15
p(8) = 22
p(9) = 30
p(10) = 42
p(100) = 190,569,292
p(200) = 3,972,999,029,388
p(1000) = 24,061,467,864,032,622,473,692,149,727,991

今のところ数えるしかないのですよね?
この表は使えますね♪
関連記事
スポンサーサイト



コメント

No title

スモークマン

解答をアップさせていただきました ^^
非公開コメント

トラックバック