トップ› 東京大学› 2000年› 理系第5問

東京大学 2000年理系第5問解説

方針・初手

各桁に使える数字は $0, 1, 2, \dots, 9$ の 10 個である。条件「どの 2 つのけたの数字の和も 9 にならない」は、和が 9 になるペア $\{0, 9\}, \{1, 8\}, \{2, 7\}, \{3, 6\}, \{4, 5\}$ の 5 組について、同じ組に含まれる 2 つの数字を同時に使うことができないことを意味する。

また「各けたの数字はたがいに異なる」という条件と合わせると、ある桁に数字を 1 つ定めると、以降の桁では「その数字」と「和が 9 になる数字」の 2 つが使えなくなる。この性質を利用し、上の位から順に数字を決めていくことで場合の数を計算する。

解法1

(1)

4 桁の整数について、上の位から順に選べる数字の個数を考える。

千の位の数字の選び方は、0 を除く 1 から 9 までの 9 通りである。

百の位の数字の選び方は、全 10 個の数字から、千の位で選んだ数字とそのペアの数字の合計 2 個を除いた 8 通りである。

十の位の数字の選び方は、百の位までの決定によって使えなくなった 2 組（4 個）の数字を除く 6 通りである。

一の位の数字の選び方は、十の位までの決定によって使えなくなった 3 組（6 個）の数字を除く 4 通りである。

したがって、求める 4 桁の要素の個数は

$$ 9 \times 8 \times 6 \times 4 = 1728 $$

よって、1728 個である。

(2)

まず、$S$ の要素を桁数ごとに分類し、それぞれの個数を求める。（1）と同様の考え方で計算する。

1 桁の要素は、正の整数であるから 0 は含まれず、1 から 9 までの 9 個である。

2 桁の要素の個数は

$$ 9 \times 8 = 72 $$

よって、72 個である。

3 桁の要素の個数は

$$ 9 \times 8 \times 6 = 432 $$

よって、432 個である。

ここまでの累計個数は

$$ 9 + 72 + 432 = 513 $$

となる。2000 番目の要素は 514 番目以降であるため、4 桁の数である。 4 桁の数の中で、小さい方から $2000 - 513 = 1487$ 番目の要素を求めればよい。

次に、千の位を固定したときの 4 桁の数の個数を考える。千の位を 1 つ決めると、下 3 桁の決め方は百の位から順に $8 \times 6 \times 4 = 192$ 通りある。千の位が 1 から 7 までの 4 桁の数の総数は

$$ 192 \times 7 = 1344 $$

であるから、4 桁の数の中で 1487 番目の要素は、千の位が 8 である数のうち、小さい方から $1487 - 1344 = 143$ 番目の数となる。

千の位が 8 のとき、使えない数字は 8 とそのペアの 1 であるから、百の位以降で使える数字は小さい順に $0, 2, 3, 4, 5, 6, 7, 9$ の 8 個である。百の位の数字をこの中から 1 つ固定したとき、下 2 桁の決め方は $6 \times 4 = 24$ 通りある。

$$ 143 = 24 \times 5 + 23 $$

であるため、百の位の数字が小さい方から 1 番目から 5 番目（$0, 2, 3, 4, 5$）である数は合計 $24 \times 5 = 120$ 個ある。したがって求める要素は、百の位が小さい方から 6 番目の 6 である数のうち、小さい方から 23 番目の数となる。

千の位が 8、百の位が 6 のとき、使えない数字は $8, 1, 6, 3$ であるから、十の位以降で使える数字は小さい順に $0, 2, 4, 5, 7, 9$ の 6 個である。十の位の数字をこの中から 1 つ固定したとき、一の位の決め方は 4 通りある。

$$ 23 = 4 \times 5 + 3 $$

であるため、十の位の数字が小さい方から 1 番目から 5 番目（$0, 2, 4, 5, 7$）である数は合計 $4 \times 5 = 20$ 個ある。したがって求める要素は、十の位が小さい方から 6 番目の 9 である数のうち、小さい方から 3 番目の数となる。

千の位が 8、百の位が 6、十の位が 9 のとき、使えない数字は $8, 1, 6, 3, 9, 0$ であるから、一の位として使える数字は小さい順に $2, 4, 5, 7$ の 4 個である。この中で小さい方から 3 番目の数字は 5 である。

以上より、条件を満たす要素の各桁の数字は順に 8, 6, 9, 5 と確定する。

解法2

（1）の別解

各桁に使える数字の集合を、和が 9 になるペア同士で 5 つのグループに分ける。 $A=\{0, 9\}, B=\{1, 8\}, C=\{2, 7\}, D=\{3, 6\}, E=\{4, 5\}$ 条件より、各グループから選べる数字は高々 1 つである。

4 桁の整数をつくるには、これら 5 つのグループから 4 つを選び、選んだ各グループから数字を 1 つずつ選び、それら 4 つの数字を一列に並べればよい。ただし、最高位（千の位）は 0 であってはならないため、これに注意して場合分けを行う。

（i）グループ $A$ を選ばない場合

グループ $B, C, D, E$ の 4 つをすべて選ぶ。各グループから数字を 1 つずつ選ぶ方法は $2^4 = 16$ 通りある。選んだ 4 つの数字の中に 0 は含まれないため、並べ方は自由に $4! = 24$ 通りある。この場合の整数は

$$ 16 \times 24 = 384 \text{ 個} $$

（ii）グループ $A$ を選ぶ場合

残りの 4 グループ $B, C, D, E$ から 3 つを選ぶ。選び方は ${}_4\mathrm{C}_{3} = 4$ 通りある。選んだ 4 つのグループから数字を 1 つずつ選ぶ方法は $2^4 = 16$ 通りある。この $4 \times 16 = 64$ 通りの数字の組合せのうち、0 を含むものが 32 通り、9 を含むものが 32 通りある。

0 を含む 32 通りの組合せについて、0 は千の位に置けないため、千の位の選び方は 3 通り、残り 3 桁の並べ方は $3! = 6$ 通りである。よって並べ方は $3 \times 6 = 18$ 通りとなり、この場合の整数は

$$ 32 \times 18 = 576 \text{ 個} $$

9 を含む 32 通りの組合せについて、0 は含まれないため並べ方は $4! = 24$ 通りある。この場合の整数は

$$ 32 \times 24 = 768 \text{ 個} $$

（i）,（ii）より、求める 4 桁の要素の個数は

$$ 384 + 576 + 768 = 1728 $$

よって、1728 個である。

解説

条件を「互いに素なペアからの選択」と言い換えることがポイントである。（1）では、解法1 のように「上の位から順に決めていく」方法が最も簡明である。最高位の 0 の扱いも自然に処理できる。解法2 のように組み合わせから考えると少し計算が煩雑になるが、数え上げの定石として知っておきたい。（2）は辞書式配列の考え方を用いる典型問題である。各桁ごとに使える数字の候補が変動することに注意しながら、商と余りを使って効率よく桁の数字を絞り込むとよい。