重複組み合わせの応用題 (2022年JJMO予選 第7問)

　仮にa,b,c,d,eが単なる非負整数であった場合、互いに区別できない2022個の玉と4つの仕切りを一列に並べる重複組み合わせの考えにより、答えは₂₀₂₆C₄通りと即座に立式する事が出来ます(但し計算は大変)。

　しかしながら本問は各非負整数の取り得る桁数に制約があり、重複組み合わせの考え方をそのまま使うことは出来ません。

解答

　総和が2022である事から非負整数a,b,c,d,eの桁数はいずれも4以下であり、桁数が4であるものの個数は高々2つである(4桁であるものが3つ以上存在した場合、各数の総和は2022より大きくなる)。

　加えて各数とも3桁の自然数ではない事から, a,b,c,d,eのうち少なくとも1つは桁数が4となるものが存在する(全て2桁か1桁の非負整数とした場合, 総和は2022より小さくなる)。従ってa,b,c,d,eのうち桁数が4であるものの個数は1つまたは2つである。

(i) 4桁であるものが1つの場合

　例えばaが4桁の自然数となる場合、残る b,c,d,eはいずれも2桁以下の非負整数である。従ってb,c,d,eが取り得る値は0から99までの100通りであり、(b,c,d,e)の取り得る組み合わせは全部で10⁸通りである。そしてa=2022-(b+c+d+e)である事から、aは各(b,c,d,e)の組に対して一意に定まりかつ、10⁸通り全てについて4桁の自然数となる為問題文の条件を満たす。

　b,c,d,eが4桁となる場合も同様に考える事が出来る為、(i)に対応する非負整数の組(a,b,c,d,e)の総数は5×10⁸ = 500000000通りである。

(ii) 4桁であるものが2つの場合

　a~eのうち、4桁となる２数の選び方は₅C₂ = 10通りである。

　まずa及びbが4桁となる場合を考え、a’=a-1000 及び b’=b-1000と置く。この時a’及びb’は非負整数であり、更に以下の式(※)を満たす。

a+b+c+d+e=2022 ⇔ a’+b’+c+d+e = 22 … (※)

　式(※)を満たす非負整数の組(a’,b’,c,d,e)の総数は重複組み合わせの考え方から₂₆C₄ = 14950通りであり(玉22個と仕切り4つ)、a’,b’,c,d,eはいずれも2桁以下の非負整数である (3桁以上の非負整数が存在すれば各数の総和は22より大きくなる)。

　従って₂₆C₄通りの(a’,b’,c,d,e)と一対一に対応する(a,b,c,d,e)の組はいずれも問題文の条件を満たす。他の場合についても同様に考えられるため、(ii)に対応する非負整数の組(a,b,c,d,e)の総数は₅C₂×₂₆C₄ = 149500通りとなる。

以上より条件を満たす非負整数の組(a,b,c,d,e)の総数は500149500通りである。

コメント

　結論だけ見てしまうと難しさを感じにくいですが、適切な場合分けと数え上げを行う為には相応の演習が必要です。