第250問の解答


1.問題 場合の数

10個異なる整数があり、その322になっています。

いま、この10個の整数の中で最も小さい数n1とします。

n1最も大きくなるようにするとき、10個の整数の組何通り考えられるでしょうか。

2.解答例1AUさん、高田修成さん、小杉原啓さん、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..10ni
=Σ
(i=1..10{n1+(i-1)+mi}
=10n1
(i=1..10){i-1}+Σ(i=1..10){mi}
=10n1+45+Σ
(i=1..10){mi}

よって、
 32210n1+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)は、求める整数の組が、整数の和に分割する場合の数(分割数)に該当することを表しています。

そこで、m10=7、6、・・・、1のときと順に数え上げれば、下表のとおりとなり、合計15通りと分かります。

表1
参考図2

図1
参考図3

なお、図1は分割後の整数タイルの数で表したもので、Youngの図(またはFerres図形)と呼ばれています。

また、Youngの図では、図2でNo.1⇔No.15、No.2⇔No.14のように、-45度の直線を対称軸として折り返したものとの対応を考えることができます。

参考図4

答:15通り

以上


その他の解答例


・n1の最大値が27であることに着目して数え上げ ・・・
 圭太さん、ちえんかん#2期さん、ゆんななこさん、mhayashiさん、DrKさん、Hossieさん、他多数


(参考)帰納法的に数え上げる方法

整数n分割数S(n)、整数nk個の整数に分割する場合の数をT(n、k)とすると、
 S(n)=Σ(k=1..n)T(n、k)
と表すことができます。

従って、T(n、k)を求めれば、S(n)を数えることができます。

参考図5

次式は、容易に分かります。
 T(n、1)=1、T(n、n-1)=1、T(n、n)=1 ・・・ (1)

参考図6

また、図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)を下表のように求めることができます。

参考図7