Evolton
方針
和が9になる数字の組 に分けると、条件は各組から高々1個の数字を使うことになる。 けたの個数は、使用する組を選び、各組から数字を1つ選び、並べる。ただし先頭が のものを除く。(2)では1けたから3けたまでの総数を引き、4けたの中で何番目かを求め、千の位、百の位、十の位の順にブロック数で絞り込む。
解答
(1)
2つの数字の和が9になる組は である。条件は、これら5組の各組から高々1つの数字を使うことと同値である。
4けたの数を作るには、まず5組から4組を選び、各組から1つずつ数字を選び、それら4つを並べる。先頭が0であるものも含めて数えると 通りである。
ここから先頭が のものを除く。先頭に を使うには組 を使い、残り3けたには他の4組から3組を選ぶ。各組から1つずつ数字を選び、残り3つの位置に並べるので 通りである。したがって、求める個数はである。
(2)
まず3けた以下の個数を数える。1けたの正の整数は から までの9個である。
2けたのものは、先頭0を除いて 個である。3けたのものは個である。よって3けた以下は 個である。
したがって2000番目の数は、4けたの数の中で 番目である。
千の位を1つ固定する。千の位は0ではなく、その数字が属する組はもう使えない。残り4組から3組を選び、各組から1つ選んで残り3けたに並べるので、千の位を固定したときの個数は である。、 だから、1487番目の千の位は である。 で始まる数の中では 番目である。
千の位が のとき、使えない組は である。百の位に使える数字は小さい順に である。百の位を1つ固定すると、残り2けたは、残り3組から2組を選び、各組から1つ選んで並べるので 個である。、 だから、百の位は である。 で始まる数の中では 番目である。 で始まるとき、使えない組は と である。十の位に使える数字は小さい順に である。十の位を1つ固定すると、一の位は残り2組から1つを選び、その中の数字を1つ選ぶので4通りである。、 だから、十の位は である。 で始まる数の中では 番目である。 で始まるとき、残る組は と である。一の位に使える数字は小さい順に であり、3番目は である。よって小さい方から数えて2000番目の の要素は である。
別解
解法2（残り組数の数え上げ表）
方針
数字を和が9の5組にまとめ、残り 組から 桁を埋める個数 を基本ブロックとする。桁を左から固定し、各候補のブロック数を表にして2000番目を追跡する。
解答
(1)
数字をの5組に分ける。1つの組から使える数字は高々1個である。
5組から4組を選び、数字を選んで並べた総数から先頭0の場合を引くと(2)
同じ計算により、1桁、2桁、3桁の個数は順にしたがって2000番目は、4桁の中の番目である。
先頭の数字を固定すると、残り4組から3組を使うので1ブロックは個である。1487番目は、先頭1から7までの 個の次なので、
千の位は8、ブロック内では143番目である。
8を使うと、百の位の候補はである。1候補につき残りは個だから、 より百の位は6、残りは23番目となる。
86の後の十の位候補はであり、1候補につき一の位は4通りである。 より十の位は9。
残る一の位候補 の3番目は5である。よって求める数は
総評
難度7、計算量7。和が9の5組から高々1個という構造に置き換えると、桁数別の個数と辞書順の順位を同じ原理で処理できる。先頭0を除く補正と、2000番目を4桁内の1487番目へ直す操作が誤りやすい。各接頭辞のブロック数を再計算し、8695を独立に確認した。 2つの解法は着眼点を分け、必要性・十分性、端点、等号条件を省略せず記述した。