場合の数について

大学受験の数学の問題でわからないものがありました。
2000年の東京大学の入試問題です。


次の条件を満たす正の整数全体の集合をＳとおく。
各桁の数字は互いに異なり、どの２つの桁の数字の和も９にならない。
ただし、Ｓの要素は１０進法で表す。また、１桁の正の整数はＳに含まれるものとする。
(１)Ｓの要素でちょうど４桁のものは何個あるか。
(２)小さい方から数えて2000番目のＳの要素を求めよ。


解答は、
(１)1728個
(２)8695
です。
解説は(１)について、「9・8・6・4個」と書いてありました。

考えてみたもののわかりません。
考え方を教えてください。
よろしくお願いします。

No.1 ベストアンサー 回答者： cosomos_th 回答日時： 2008/09/27 23:39

この考え方がスマートかどうかは分かりませんが、一応やり方を考えてみました。

（１）について

４桁整数の、千の位に来る可能性のある数は1～9の「9」種類

４桁整数の、百の位に来る可能性のある数は0～9の10種類のうち、
　　千の位と同じ数と、千の位の数との和が9になる数はダメなので、10-2で「8」種類

４桁整数の、十の位に来る可能性のある数は0～9の10種類のうち、
　　千の位と同じ数と、千の位の数との和が9になる数、
　　百の位と同じ数と、百の位の数との和が9になる数はダメなので、10-4で「6」種類

４桁整数の、一の位に来る可能性のある数は0～9の10種類のうち、
　　千の位と同じ数と、千の位の数との和が9になる数、
　　百の位と同じ数と、百の位の数との和が9になる数、
　　十の位と同じ数と、十の位の数との和が9になる数はダメなので、10-6で「4」種類

よって4桁のものは、9×8×6×4で「1728」個


（２）について

1桁の小さいかずから順を追って考えていきます。

[1]　1桁の整数で条件に合うものは1～9のうち9を除いた「8」個。
　　(9を入れるか除くかは迷いましたが、除かないと答えが合わないので除きました。）

[2]　2桁の整数で条件に合うものは(1)の考え方に基づきます。十の位に来る可能性のある数は9種類で、1の

位にくる可能性のある数は0～9の十種類のうち、十の位と同じ数と十の位の数との和が9になる数を抜かした

8種類で、合計で9×8で「72」個。　

---　[1]と合わせて、ここまで「80」個　---

[3]　3桁の整数で条件に合うものは、やはり(1)と同じ考え方をして9×8×6で「432」個。

　　　　---　[1][2]と合わせて、ここまで「512」個　---

[4]　4桁の整数で条件に合うものは、(1)で導き出した「1728」個。

　　　　---　同じく、ここまで「2240」個　---

おっと、2000番目を越してしまいましたから、4桁の整数の中に答えがあります。
　　　　ここからは、1000番台、2000番台・・・と順にやっていきます。

[5]　1000番台（1000～1999）の中で条件に合うものは、(1)の考え方を利用して、千の位は決まっているの

で、百と十と一の位を掛けた数(8×6×4)の192個。

　　　　--- [1][2][3]と合わせて、ここまで「704」個　---

[6]　同じようにして7000番台まで合計すると「1856」個になります。8000番台まで合計すると「2048」個に

なり2000を越してしまうので、8000番台の途中に答えがあることになります。

　ここからは、8000番台、8100番台・・・と順にやっていきます。

[7] 8000番台（8000～8099）で条件に合うものは、6×4で「24」個。
　　8100番台は飛ばします。8と1を足すと9になるからです。
　　8200番台、8300番台・・・8500番台まで加算すると「1976」個。8600番台まで加算すると行きすぎなので、

8600番台の途中に答えはあります。

[8] 8600番台、8620番台・・・と順に加算します。足していく数は4です。8610番台、8630番台、8660番台、

8680番台は、同じ数が使われているか、足して9になる桁があるので飛ばします。そうすると8670番台まで、

「1996」個になります。あとは、8690番台のあたまから条件に合う数をカウントしていきます。あと４つ足

すと2000番目なので、４番目が答えです。8690、8692、8694、8695。

よって8695が答え。

この回答へのお礼

詳しいご解説、ありがとうございました。
すっきりしました。
ポイントは回答の早かった順につけさせていただきました。

お礼日時：2008/11/24 14:20

No.4 回答者： cosomos_th 回答日時： 2008/09/28 07:10

No.1です。

当方に間違えがあったようなので、訂正します。
No.2さんありがとう。間違えを見つけるけっかけとなりました。

1桁の数字「9」は条件に合うものとして考えた方が自然なようです。

よって、途中の合計が各々1づつ足されるのと、
最後の4行を以下のように訂正します。

＞「1996」個になります。あとは、8690番台のあたまから条件に合う数をカウントしていきます。
＞あと４つ足すと2000番目なので、４番目が答えです。
＞8690、8692、8694、8695。
＞よって8695が答え。

「1997」個になります。あとは、8690番台のあたまから条件に合う数をカウントしていきます。
あと３つ足すと2000番目なので、３番目が答えです。8692、8694、8695。

よって8695が答え。

No.3 回答者： orcus0930 回答日時： 2008/09/27 23:51

No2です。

No1の方と途中が違いますね。
計算ミスしたかもしれません。
どちらを信用するかは、自分で計算してみてくださいね。
基本的な考え方は変わりありませんので。

No1の方へ

1桁の数は4桁の数で9を使用した数を使用できることを考慮すると、
1～9の9個とすべきではないでしょうか。

No.2 回答者： orcus0930 回答日時： 2008/09/27 23:42

さて、まず東大という名前にビビるのはやめましょうね。

これは、基本問題を難しく言ってるだけです。
問題文を分解して解釈していきましょうか。


ただし、Ｓの要素は１０進法で表す。→ 使用できる数が0,1,2,3,4,5,6,7,8,9であるということ

各桁の数字は互いに異なり、→ 同じ数字の複数使用はできない
どの２つの桁の数字の和も９にならない。→ これがポイントかもしれませんね。

(0,9)(1,8)(2,7)(3,6)(4,5)がペアでどちらか一方を選んだらもう一方は選べないということ。つまりは１つを選ぶと選んだ数とそのペアになる数の合計二つが減るということ。

以上をおさえたうえで、問題を解きましょうか。
(1)
セオリー通り４桁目から決めていきましょう。
4桁目：0以外のすべての数字が入ることができるので　9通り
3桁目：4桁目で選んだ数とそのペアになる数の2つが選べないので　8通り
2桁目：4桁目と3桁目の数とそのペアの数の4つが選べないので　6通り
1桁目：同様にして　4通り

よって　9*8*6*4=1728個

(1)
重要なことはSの要素には１桁の数、２桁の数、３桁の数もあるということです。
１桁の数　1～9の9個
２桁の数　9*8=72個
３桁の数　9*8*6=432個

なので２０００番目は
2000-(9+72+432)=1487
から４桁の数の１４８７番目の数ということになる。

では４桁の１４８７番目を求めていきましょう。
まず、4桁目を固定しましょう。たとえば1
4桁目が1の4桁の数は、(1)を参考にして、4桁目の選べる数が1つになるだけなので
1*8*6*4=192個
４桁目が2～9のときもそれぞれ１９２個あることになる。

1487/192=7あまり143
なので、
4桁目が1～7の数は　192*7=1344個であることから
4桁目は8と分かる。
4桁目が8の数の中で143番目ということ。

次に3桁目を固定する。同様のことをすればいいので
4桁目3桁目を固定した数は　6*4=24個
143/24=5あまり23　…(*)
なので3桁目は6
おそらくはここが最大のポイント
(*)での5が示すものは、3桁目として選ぶことができる数の6番目が3桁目であるということ
今選ぶことができる数は4桁目に8を選んでいるので1を選ぶことができないことを考慮して、

0,2,3,4,5,6,7,9を選ぶことができるので6番目は6
なので3桁目が6に決まる。

86○○という数字で23番目を選べばいい
上記より、24番目が86○○という数の中で一番大きい数ということ。
なので24番は8697
よって23番目は8695になる。

以上からSのうち2000番目は8695　ということ

いくつか注意しなければならないポイントはあるが、絶対にとけないという問題ではない。
問題をしっかり自分なりの言葉で解釈していくことが重要