第250問の解答
1.問題 [場合の数]
10個の異なる整数があり、その和は322になっています。
いま、この10個の整数の中で最も小さい数をn1とします。
n1が最も大きくなるようにするとき、10個の整数の組は何通り考えられるでしょうか。
2.解答例1(AUさん、高田修成さん、小杉原啓さん、Mikiさん、Taroさん、ミミズクはくず耳さん、あんみつさん、TORAさん、トトロ@Nさん、中村明海さん、BossFさん、他多数)
10個の整数をn1、n2、n3、・・・、n10(ただし、n1<n2<n3<・・・<n10)とします。
n2≧n1+1
n3≧n2+1≧(n1+1)+1≧n1+2
n4≧n3+1≧(n2+2)+1≧n1+3
・・・
n10≧n9+1≧(n1+8)+1≧n1+9
一般式としては、ni≧n1+(i-1)(ただし、1≦i≦10)が成り立ちます。ここで、ni=n1+(i-1)+miとおくと、上記より、mi≧0。
また、ni+1-ni={n1+i+mi+1}-{n1+(i-1)+mi}=mi+1-mi+1が成り立ち、
ni+1-ni≧1より、mi+1-mi≧0(ただし、1≦i≦9)さて、題意より、
Σ(i=1..10)ni
=Σ(i=1..10){n1+(i-1)+mi}
=10n1+Σ(i=1..10){i-1}+Σ(i=1..10){mi}
=10n1+45+Σ(i=1..10){mi}よって、
322=10n1+45+Σ(i=1..10){mi}
10n1=277-Σ(i=1..10){mi}≦277
従って、n1≦27.7となり、n1の最大値は、27と分かります。よって、Σ(i=1..10){mi}=322-(27×10+45)=7となります。・・・(1)
(1)は、求める整数の組が、7を整数の和に分割する場合の数(分割数)に該当することを表しています。
そこで、m10=7、6、・・・、1のときと順に数え上げれば、下表のとおりとなり、合計15通りと分かります。
表1 |
図1 |
なお、図1は分割後の整数をタイルの数で表したもので、Youngの図(またはFerres図形)と呼ばれています。
また、Youngの図では、図2でNo.1⇔No.15、No.2⇔No.14のように、-45度の直線を対称軸として折り返したものとの対応を考えることができます。
答:15通り
以上
その他の解答例
・n1の最大値が27であることに着目して数え上げ ・・・
圭太さん、ちえんかん#2期さん、ゆんななこさん、mhayashiさん、DrKさん、Hossieさん、他多数
(参考)帰納法的に数え上げる方法
整数nの分割数をS(n)、整数nをk個の整数に分割する場合の数をT(n、k)とすると、
S(n)=Σ(k=1..n)T(n、k)
と表すことができます。従って、T(n、k)を求めれば、S(n)を数えることができます。
次式は、容易に分かります。
T(n、1)=1、T(n、n-1)=1、T(n、n)=1 ・・・ (1)また、図3より、次式が成り立つことが分かります。
k>n/2のとき:T(n、k)=T(n-1、k-1) ・・・ (2)
k≦n/2のとき:T(n、k)=T(n-1、k-1)+T(n-k、k) ・・・ (3)(1)、(2)、(3)を用いて、次々とT(n、k)を下表のように求めることができます。