Evolton

東京大学 2000年度 前期日程 第2次学力試験理系数学 第5問

次の条件を満たす正の整数全体の集合をSとおく。

「各けたの数字はたがいに異なり,どの2つのけたの数字の和も9にならない。」

ただし,Sの要素は10進法で表す。
また,1けたの正の整数はSに含まれるとする。
このとき次の問いに答えよ。

(1) Sの要素でちょうど4けたのものは何個あるか。

(2) 小さい方から数えて2000番目のSの要素を求めよ。

難易度7/ 10計算量7/ 10目安30分

場合の数、整数 数え上げ、場合分け、計算整理

方針

和が9になる数字の組 {0,9},{1,8},{2,7},{3,6},{4,5} に分けると、条件は各組から高々1個の数字を使うことになる。k けたの個数は、使用する組を選び、各組から数字を1つ選び、並べる。ただし先頭が 0 のものを除く。(2)では1けたから3けたまでの総数を引き、4けたの中で何番目かを求め、千の位、百の位、十の位の順にブロック数で絞り込む。

解答

(1)
2つの数字の和が9になる組は {0,9},{1,8},{2,7},{3,6},{4,5} である。条件は、これら5組の各組から高々1つの数字を使うことと同値である。

4けたの数を作るには、まず5組から4組を選び、各組から1つずつ数字を選び、それら4つを並べる。先頭が0であるものも含めて数えると 5C424⋅4! 通りである。

ここから先頭が 0 のものを除く。先頭に 0 を使うには組 {0,9} を使い、残り3けたには他の4組から3組を選ぶ。各組から1つずつ数字を選び、残り3つの位置に並べるので 4C323⋅3! 通りである。したがって、求める個数は5C424⋅4!−4C323⋅3!=5⋅16⋅24−4⋅8⋅6=1728である。

(2)
まず3けた以下の個数を数える。1けたの正の整数は 1 から 9 までの9個である。

2けたのものは、先頭0を除いて 5C222⋅2!−4C12⋅1!=80−8=72 個である。3けたのものは5C323⋅3!−4C222⋅2!=480−48=432個である。よって3けた以下は 9+72+432=513 個である。

したがって2000番目の数は、4けたの数の中で 2000−513=1487 番目である。

千の位を1つ固定する。千の位は0ではなく、その数字が属する組はもう使えない。残り4組から3組を選び、各組から1つ選んで残り3けたに並べるので、千の位を固定したときの個数は 4C323⋅3!=192 である。7⋅192=1344、8⋅192=1536 だから、1487番目の千の位は 8 である。8 で始まる数の中では 1487−1344=143 番目である。

千の位が 8 のとき、使えない組は {1,8} である。百の位に使える数字は小さい順に 0,2,3,4,5,6,7,9 である。百の位を1つ固定すると、残り2けたは、残り3組から2組を選び、各組から1つ選んで並べるので 3C222⋅2!=24 個である。5⋅24=120、6⋅24=144 だから、百の位は 6 である。86 で始まる数の中では 143−120=23 番目である。 86 で始まるとき、使えない組は {1,8} と {3,6} である。十の位に使える数字は小さい順に 0,2,4,5,7,9 である。十の位を1つ固定すると、一の位は残り2組から1つを選び、その中の数字を1つ選ぶので4通りである。5⋅4=20、6⋅4=24 だから、十の位は 9 である。869 で始まる数の中では 23−20=3 番目である。 869 で始まるとき、残る組は {2,7} と {4,5} である。一の位に使える数字は小さい順に 2,4,5,7 であり、3番目は 5 である。よって小さい方から数えて2000番目の S の要素は 8695 である。

別解

解法2(残り組数の数え上げ表)

方針

数字を和が9の5組にまとめ、残り r 組から m 桁を埋める個数 N(r,m)=rCm2mm! を基本ブロックとする。桁を左から固定し、各候補のブロック数を表にして2000番目を追跡する。

解答

(1)
数字を{0,9},{1,8},{2,7},{3,6},{4,5}の5組に分ける。1つの組から使える数字は高々1個である。
5組から4組を選び、数字を選んで並べた総数から先頭0の場合を引くと5⋅24⋅4!−4⋅23⋅3!=1920−192=1728.(2)
同じ計算により、1桁、2桁、3桁の個数は順に9,10⋅4⋅2!−4⋅2=72,10⋅8⋅3!−6⋅4⋅2!=432.したがって2000番目は、4桁の中の2000−(9+72+432)=1487番目である。

先頭の数字を固定すると、残り4組から3組を使うので1ブロックは4⋅23⋅3!=192個である。1487番目は、先頭1から7までの 7⋅192=1344 個の次なので、
千の位は8、ブロック内では143番目である。

8を使うと、百の位の候補は0,2,3,4,5,6,7,9である。1候補につき残りは3⋅22⋅2!=24個だから、143=5⋅24+23 より百の位は6、残りは23番目となる。

86の後の十の位候補は0,2,4,5,7,9であり、1候補につき一の位は4通りである。23=5⋅4+3 より十の位は9。
残る一の位候補 2,4,5,7 の3番目は5である。よって求める数は8695.

総評

難度7、計算量7。和が9の5組から高々1個という構造に置き換えると、桁数別の個数と辞書順の順位を同じ原理で処理できる。先頭0を除く補正と、2000番目を4桁内の1487番目へ直す操作が誤りやすい。各接頭辞のブロック数を再計算し、8695を独立に確認した。 2つの解法は着眼点を分け、必要性・十分性、端点、等号条件を省略せず記述した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の場合の数の問題で問題集を作る

出典: 東京大学 2000年度 前期 理科 第5問。問題文はHTML表示のために再入力・数式組版しています。