数学シール問題の解答

id:hyuki:20050428#quiz こんな問題を結城さんが出題されていたので、解答を考えてみました。
問題は、[0][1][2][3][4][5][6][7][8][9]の10種類の数字が書かれたシールがたくさんある。このシールを貼って数を作ることにする。この時、1から1000までの整数(1, 2, 3, ..., 999, 1000)を作るのに、[3]のシールは全部で何枚必要か？というもの。
解答としては、300枚です。
解答を考える前に、まずは簡単のために1〜100で考えます。その時、100を00として1桁の数字を頭に0をつけて全て2桁にして考えることにします。[3]の数を考えるのでこのような変更をしても枚数に違いはないので問題ないです。そうすると、[0][0]〜[9][9]の100個の数字の組ができますが同じ数字の組は存在しません。そのため数字のシールが10種類しかなく100組の異なる数字の組ができていることから、[3]を使っている数字の組は以下の２通りが考えられることになります。

[3][A]

1番目の数字が[3]の場合

[B][3]

2番目の数字が[3]の場合

A、Bにはそれぞれ[0]〜[9]が入るのでそれぞれ10通り存在しますので、結局[3]のシールは20枚必要になります。さて、次に1〜1000で考えることにします。この場合も同じような変更をすることで3桁の数字の組と考えられるので、以下の３通りの場合を考えればいいことになります。

[3][X][Y]

1番目の数字が[3]の場合

[X][3][Y]

2番目の数字が[3]の場合

[X][Y][3]

3番目の数字が[3]の場合

よって、[X][Y]にはそれぞれ[0]〜[9]が入るのでそれぞれ100通り存在します。結局[3]のシールは3*100枚必要となります。

これを拡張すると、1〜10^nまで(nは正整数)の場合には、[3]のシールは n*10^(n-1)枚必要となることが分かります。