解説

方針・初手

和が $9$ になる数字の組は

$$ (0,9),\ (1,8),\ (2,7),\ (3,6),\ (4,5)

$$

の $5$ 組である。したがって、条件は「この $5$ 組の各組から高々 $1$ 個ずつ数字を選ぶ」と言い換えられる。

桁数ごとに個数を数え、(2) では $2000$ 番目が何桁の数かを先に決めてから、上の桁から順に確定する。

解法1

（1） ちょうど $4$ 桁のものを数える。

$4$ 桁の数に使う数字は、上の $5$ 組から $4$ 組を選び、それぞれの組から $1$ 個ずつ数字を選べばよい。したがって、条件を満たす $4$ 個の数字の集合は

$$ {}_5 \mathrm{C}_{4} \cdot 2^4=80

$$

通りである。

このうち $0$ を含むものを数える。$0$ を含むには、組 $(0,9)$ から $0$ を選び、残り $4$ 組から $3$ 組を選んで、それぞれ $1$ 個ずつ数字を選べばよい。よって

$$ {}_4 \mathrm{C}_{3} \cdot 2^3=32

$$

通りである。

したがって、$0$ を含まない数字集合は

$$ 80-32=48

$$

通りである。

$0$ を含まない場合は $4!$ 通りに並べられる。$0$ を含む場合は、全体の並べ方 $4!$ 通りから、先頭が $0$ になる $3!$ 通りを除くので、並べ方は $4!-3!$ 通りである。

よって、ちょうど $4$ 桁のものの個数は

$$ 48\cdot 4!+32\cdot(4!-3!) =48\cdot24+32\cdot18 =1152+576 =1728

$$

である。

次に （2） を考える。

まず、$1$ 桁、$2$ 桁、$3$ 桁の個数を数える。

$1$ 桁の正の整数はすべて $S$ に含まれるので、

$$ 9

$$

個である。

$2$ 桁の場合、十の位は $1$ から $9$ の $9$ 通りである。十の位を決めると、一の位には「同じ数字」と「和が $9$ になる数字」を使えないので、残りは $8$ 通りである。よって

$$ 9\cdot 8=72

$$

個である。

$3$ 桁の場合、使う $3$ 個の数字の集合は

$$ {}_5 \mathrm{C}_{3}\cdot 2^3=80

$$

通りである。このうち $0$ を含むものは

$$ {}_4 \mathrm{C}_{2}\cdot 2^2=24

$$

通りである。

したがって、$0$ を含まないものは $80-24=56$ 通りである。$0$ を含まない場合は $3!$ 通り、$0$ を含む場合は $3!-2!$ 通りに並べられるので、$3$ 桁の個数は

$$ 56\cdot 3!+24\cdot(3!-2!) =56\cdot6+24\cdot4 =336+96 =432

$$

である。

よって、$3$ 桁以下の $S$ の要素数は

$$ 9+72+432=513

$$

である。したがって、$2000$ 番目の要素は $4$ 桁であり、$4$ 桁の中では

$$ 2000-513=1487

$$

番目である。

ここから、$4$ 桁の数を小さい順に考える。

まず千の位を固定する。千の位を $1$ つ決めると、その数字と和が $9$ になる数字を使えないので、残りは他の $4$ 組から $3$ 組を選び、それぞれ $1$ 個ずつ選んで並べることになる。したがって、千の位を固定したときの個数は

$$ {}_4 \mathrm{C}_{3}\cdot 2^3\cdot 3! =4\cdot8\cdot6 =192

$$

個である。

千の位が $1,2,\dots,7$ のものは

$$ 7\cdot192=1344

$$

個であり、

$$ 1344<1487\le 1536

$$

だから、$1487$ 番目の $4$ 桁の数の千の位は $8$ である。

千の位が $8$ の中では、

$$ 1487-1344=143

$$

番目を求めればよい。

千の位が $8$ のとき、百の位に使える数字は

$$ 0,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 9

$$

である。百の位を $1$ つ固定すると、残り $2$ 桁は他の $3$ 組から $2$ 組を選び、それぞれ $1$ 個ずつ選んで並べるので、

$$ {}_3 \mathrm{C}_{2}\cdot 2^2\cdot 2! =3\cdot4\cdot2 =24

$$

個である。

百の位が $0,2,3,4,5$ のものは

$$ 5\cdot24=120

$$

個であり、

$$ 120<143\le 144

$$

だから、百の位は $6$ である。

この中では

$$ 143-120=23

$$

番目を求めればよい。

千の位と百の位が $86$ のとき、残っている組は

$$ (0,9),\ (2,7),\ (4,5)

$$

である。十の位に使える数字は小さい順に

$$ 0,\ 2,\ 4,\ 5,\ 7,\ 9

$$

である。

十の位を $1$ つ固定すると、一の位には残りの $2$ 組から $1$ 個選べばよいので、各場合 $4$ 通りである。

十の位が $0,2,4,5,7$ のものは

$$ 5\cdot4=20

$$

個であり、

$$ 20<23\le 24

$$

だから、十の位は $9$ である。

この中では

$$ 23-20=3

$$

番目を求めればよい。

千の位、百の位、十の位が $869$ のとき、一の位に使える数字は

$$ 2,\ 4,\ 5,\ 7

$$

である。このうち小さい方から $3$ 番目は $5$ である。

したがって、$2000$ 番目の $S$ の要素は

$$ 8695

$$

である。

解説

この問題の本質は、数字を

$$ (0,9),\ (1,8),\ (2,7),\ (3,6),\ (4,5)

$$

の $5$ 組に分けることである。和が $9$ になる組を同時に使えないので、各組から高々 $1$ 個ずつ選ぶ問題になる。

(1) では、先に「使う数字の集合」を数え、その後で「先頭に $0$ が来ない並べ方」を数えるのが安全である。

(2) では、桁数ごとの個数を先に数え、$2000$ 番目が $4$ 桁であることを確定してから、千の位、百の位、十の位、一の位の順に決める。数を小さい順に並べる問題では、このように上の桁から固定して個数を削っていくのが典型的である。

答え

**(1)**

$$ 1728

$$

**(2)**

$$ 8695

$$