Evolton

京都大学 2011年度 前期日程 第2次学力試験文系数学 第5問

0以上の整数を10進法で表すとき，次の問いに答えよ．
ただし，0は0桁の数と考えることにする．
またnは正の整数とする．

(1) 各桁の数が1または2であるn桁の整数を考える．
それらすべての整数の総和をTnとする．
Tnをnを用いて表せ．

(2) 各桁の数が0，1，2のいずれかであるn桁以下の整数を考える．
それらすべての整数の総和をSnとする．
SnがTnの15倍以上になるのは，nがいくつ以上のときか．
必要があれば，0.301<log⁡102<0.302および
0.477<log⁡103<0.478を用いてもよい．

難易度5/ 10計算量4/ 10目安18分

数列、場合の数、指数・対数　数え上げ、和の計算、範囲評価

方針

各整数を個別に足すのではなく、各桁が総和に何回ずつ寄与するかを数える。(1)では各桁に1と2がそれぞれ 2n−1 回ずつ現れる。(2)では n 桁未満の数も先頭に0を補って n 桁の列として一意に扱うと、各桁に0,1,2がそれぞれ 3n−1 回ずつ現れる。最後は Sn/Tn=(3/2)n−1 に簡約し、15以上となる最小の n を直接比較で決める。

解答

(1)

各桁の数が1または2である n 桁の整数は、全部で 2n 個ある。ある1つの桁に注目すると、その桁が1であるものは残り n−1 桁を自由に選べるので 2n−1 個あり、その桁が2であるものも同じく 2n−1 個ある。したがって、その桁に現れる数字の総和は 1⋅2n−1+2⋅2n−1=3⋅2n−1 である。

一の位、十の位、…、10n−1 の位の重みを合わせると 1+10+⋯+10n−1=10n−19 である。よってTn=3⋅2n−1(1+10+⋯+10n−1)=3⋅2n−1⋅10n−19=2n−1(10n−1)3である。

(2)

各桁の数が0,1,2のいずれかである n 桁以下の整数を、先頭に0を補って n 桁の列として表す。たとえば 12 は n 桁に満たないときも先頭に0を補って表す。この表し方は各整数に対して一意であり、問題文で0を0桁と考えることとも矛盾しない。

このとき、各桁には0,1,2がそれぞれ 3n−1 回ずつ現れる。したがって、ある1つの桁に現れる数字の総和は (0+1+2)3n−1=3n である。よって Sn=3n(1+10+⋯+10n−1)=3n⋅10n−19 となる。

(1) の結果と比をとるとSnTn=3n⋅10n−192n−1(10n−1)3=3n−12n−1=(32)n−1である。したがって、求める条件は (32)n−1≧15 である。

直接比較すると (32)6=72964<15 である。一方、(32)7=2187128 であり、2187>1920=15⋅128 だから (32)7>15 である。よって n−1≧7 が必要十分であり、n≧8 である。

総評

桁ごとの寄与で総和を出す問題で、個々の整数を並べる発想から早く離れられるかが勝負である。(1)は各桁に1と2が同数回現れること、(2)は先頭に0を補っても重複なく数えられることが重要である。Sn と Tn はどちらも 10n−1 を含むため、比を取ると桁の重みが消える。この簡約を見落とすと不必要に対数計算へ進みやすい。目安時間は18分程度。

冊子PDFで見る京大の数列の問題で問題集を作る

出典: 京都大学 2011年度 前期日程 数学（大学公式の問題PDF）。問題文はHTML表示のために再入力・数式組版しています。