京都大学 文系 2017年度 第2問 解説
問題編
問題
次の問に答えよ。ただし、 $0.3010 \lt \log_{10}2 \lt 0.3011$ であることは用いてよい。
(1) 100桁以下の自然数で、2以外の素因数を持たないものの個数を求めよ。
(2) 100桁の自然数で、2と5以外の素因数を持たないものの個数を求めよ。
考え方
(1)はよくあるパターンです。 $2^n$ の形でかけるものがいくつあるか数えればいいですね。
(2)は、かなり難しいです。(1)では「100桁以下」となっていたところが「100桁」となっていることにまず注意しましょう。
3桁の場合ならどうなるかを、少し書き出してみましょう。5のべき乗が少ないものが手前に来ていて、2のべき乗が少ないものがさらに手前に来るように並べています。
- 128, 256, 512, 160, 320, 640, 100, 200, 400, 800, 125, 250, 500, 625
- 128, 256, 512, 125, 625
- 160, 320, 640, 250
- 100, 200, 400, 800, 500
- 1行目：「2以外の素因数を持たない3桁の自然数」「5以外の素因数を持たない3桁の自然数」
- 2行目：「2以外の素因数を持たない2桁の自然数」「5以外の素因数を持たない2桁の自然数」
- 3行目：「2以外の素因数を持たない1桁の自然数」「5以外の素因数を持たない1桁の自然数」
これを縦に足せば、「2以外の素因数を持たない3桁 "以下" の自然数」と「5以外の素因数を持たない3桁 "以下" の自然数」が出てきます。この形になると、(1)が使えそうですね。
解答編
問題
次の問に答えよ。ただし、 $0.3010 \lt \log_{10}2 \lt 0.3011$ であることは用いてよい。
(1) 100桁以下の自然数で、2以外の素因数を持たないものの個数を求めよ。
(2) 100桁の自然数で、2と5以外の素因数を持たないものの個数を求めよ。
解答
(1)
2以外の素因数を持たない自然数は、0以上の整数 n を用いて $2^n$ とかける。これが100桁以下の自然数となることは\[ 2^n \lt 10^{100} \]が成り立つことと同値である。両辺について、10を底とする対数を考えると
\begin{eqnarray}
n \log_{10}2 \lt 100 \\[5pt]
n \lt \frac{100}{\log_{10}2} \\[5pt]
\end{eqnarray}となる。ここで $\dfrac{100}{0.3010} = 332.2\cdots$, $\dfrac{100}{0.3011} = 332.1\cdots$ なので、上の不等式は、 n が0以上332以下の整数のときに成り立つことがわかる。よって、条件を満たす自然数は、333個ある。
(2)
2と5以外の素因数を持たない自然数に対し、一の位から連続して0が並ぶ個数を k （ k は0から99までの整数）とすると、この自然数は、 k と 0以上の整数 n, m を用いて $10^k \cdot 2^n \cdot 5^m$ とかける。ただし、n, m のどちらかは0である。これが100桁の自然数となることは\[ 10^{99} \leqq 10^k \cdot 2^n \cdot 5^m \lt 10^{100} \]が成り立つことと同値である。
$m=0$ のときを考える。 このとき、上の条件式は\[ 10^{99-k} \leqq 2^n \lt 10^{100-k} \]となる。 k を固定したとき、これを満たす n の個数は「$(100-k)$ 桁の自然数で、2以外の素因数を持たないものの個数」と同じである。これを k について足し合わせると、「100桁以下の自然数で、2以外の素因数を持たないものの個数」となり、(1)から333個となることがわかる。
$n=0$ のときも同様である。上の条件式は\[ 10^{99-k} \leqq 5^m \lt 10^{100-k} \]となる。 k を固定したとき、これを満たす m の個数は「$(100-k)$ 桁の自然数で、5以外の素因数を持たないものの個数」と同じである。これを k について足し合わせると、「100桁以下の自然数で、5以外の素因数を持たないものの個数」となる。(1)と同様にして
\begin{eqnarray}
a
&\lt&
\frac{100}{\log_{10}5} \\[5pt]
&=&
\frac{100}{1-\log_{10}2} \\[5pt]
\end{eqnarray}を満たす0以上の整数 a の個数を求めればよい。ここで
\begin{eqnarray}
\frac{100}{1-0.301} &=& 143.06\cdots \\[5pt]
\frac{100}{1-0.3011} &=& 143.08\cdots \\[5pt]
\end{eqnarray}であることから、「100桁以下の自然数で、5以外の素因数を持たないものの個数」は、0から143までの整数の個数と一致するので、144個である。
また、 $n=m=0$ のとき、\[ 10^{99} \leqq 10^k \cdot 2^n \cdot 5^m \lt 10^{100} \]を満たすのは、 $k=99$ のときのみである。上の数え方では、これを2回数えている。
以上から、\[ 333+144-1=476 \]個となる。
（終）
解説
(2)は、結果的に、数字の右側にある0を取り除いて考えていることになります。対象となる自然数は、 $10^{k}\cdot 2^n$, $10^{k}\cdot 5^m$ の形で書けるものしかなく、 $100-k$ 桁の自然数で $2^n$ の形で書けるものを考え、それを k について足し合わせれば、(1)の結果が使えるようになる、ということですね。
ただし、 $10^{99}\cdot 2^0 \cdot 5^0$ だけは二重で数えているので、これをあとで取り除く必要があります。
(1)はよく見かける問題ですが、(2)はあまり見かけない上、考え方が思いつきにくく、難しい問題です。