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


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

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

解答

 総和が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)の取り得る組み合わせは全部で108通りである。そしてa=2022-(b+c+d+e)である事から、aは各(b,c,d,e)の組に対して一意に定まりかつ、108通り全てについて4桁の自然数となる為問題文の条件を満たす。

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

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

 a~eのうち、4桁となる2数の選び方は5C2 = 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)の総数は重複組み合わせの考え方から26C4 = 14950通りであり(玉22個と仕切り4つ)、a’,b’,c,d,eはいずれも2桁以下の非負整数である (3桁以上の非負整数が存在すれば各数の総和は22より大きくなる)。

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

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

コメント

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

投稿者: matsubushi

趣味で数学など

重複組み合わせの応用題 (2022年JJMO予選 第7問)」に2件のコメントがあります

  1. 初めて見にきました。中盤までの中で7番が際立って難しい気がしていて困っていましたがとてもわかりやすい解説で解けなかった自分を叱りたいくらいです…
    本当にありがとうございます!助かります!!

    1. 自分もこの答案に行き着くまでに色々試行錯誤しました。時間制限のある試験場で解き切るのは思いのほか厳しそうな気がしますね。

焼肉定食 へ返信する コメントをキャンセル

モバイルバージョンを終了