[答1182] 不等式を満たす整数の組
'
[答1182] 不等式を満たす整数の組
集合S,集合Tを S={0,1,2,3,4,5,6,7,8,9,10},
T={(a,b,c,d)|a∈S,b∈S,c∈S,d∈S,3a≦b+c+d+10} とするとき、
集合Tの要素の個数は?
[参考]
例えば、3つの負でない整数の和が 10以下の場合の数は、
○○○○○○○○○○ の間または両端から重複を許して3個を選び、
そこに区切りを入れれば ○○○|○|○○○○|○○ のようになり、
各区切りまでの○の個数を数えれば 3+1+4 になりますので、11H3 です。
このように、3つの負でない整数の和がn以下の場合の数は、n+1H3=(n+1)(n+2)(n+3)/6 です。
一般に、負でない整数r個の和がn以下になる場合の数は n+1Hr です。
[解答]
全体集合U={(a,b,c,d)|a∈S,b∈S,c∈S,d∈S} とすれば、
Uの要素の個数は 114=14641 個で、
Tの補集合{(a,b,c,d)|(a,b,c,d)∈U,3a>b+c+d+10}の要素の個数を求めます。
b+c+d<3a-10 、b+c+d≦3a-11 ですので、
4≦a≦10 において、負でない整数3個の和が(3a-11)以下になる場合の数は
(3a-10)(3a-9)(3a-8)/6=(a-3)(3a-10)(3a-8)/2 で、
1・2・4/2+2・5・7/2+3・8・10/2+4・11・13/2+5・14・16/2+6・17・19/2+7・20・22/2
=4+35+120+286+560+969+1540=3514 、
b≧11 のとき (b-11)+c+d≦3a-22 ですので、
8≦a≦10 において、負でない整数3個の和が(3a-22)以下になる場合の数は
(3a-21)(3a-20)(3a-19)/6=(a-7)(3a-20)(3a-19)/2 です。
c≧11,d≧11 のときも同様で、11以上の整数を含む場合の数は、3(a-7)(3a-20)(3a-19)/2 で、
3・1・4・5/2+3・2・7・8/2+3・3・10・11/2=30+168+495=693 、
よって、Tの補集合の要素の個数は 3514-693=2821 です。
また、Tの要素の数は、14641-2821=11820 です。
[参考]
S={0,1,2,……,n},T={(a,b,c,d)|a∈S,b∈S,c∈S,d∈S,3a≦b+c+d+n} のとき、
集合Tの要素の個数は [(59n4+226n3+329n2+210n+72)/72] です。
.