Problems and Solutions #006

      Comments Off on Problems and Solutions #006
$2^n$의 첫 네자리의 숫자가 $2018$이 되게 하는 $n$이 존재함을 보여라.

$ $

※ 위 문제는 임의의 $k$자리 양의 정수 $x$에 대하여 $2^n$의 첫 $k$ 자리의 숫자가 $x$가 되게 하는 $n$의 존재성을 증명하는 문제로 확장 가능하다. (또한 이제부터 보일 증명과 같은 방법으로 증명할 수 있다.)

 

풀이. 위 문제는 아래의 부등식을 만족하는 양의 정수 $m,\,n$을 찾는 문제와 같다.

\[ 2018 \cdot 10^m \leq 2^n < 2019 \cdot 10^m \]

위 식의 양변에 밑이 $10$인 로그를 취하면

\[ m + \log 2018 \leq n \log 2 < m + \log 2019 \]

이제 임의의 $x$에 대하여 $\{x\}$를 $x$의 소수부분, 즉, $\{x\} = x - \lfloor x \rfloor$라 정의하자. 그러면 다음의 수열

\[ \{ \log 2 \},\, \{ 2 \log 2 \},\, \{ 3 \log 2 \},\, \ldots \tag*{(1)}\]

은 구간 $[0,\,1)$에서 서로 다른 수로 이루어진 수열이 된다. (만약 적당한 $\alpha < \beta$가 존재하여 $\{ \alpha \log 2 \} = \{ \beta \log 2\}$가 된다고 가정하면, $\beta \log 2 - \alpha \log 2$의 값은 정수가 되는데 이는 $\log 2$가 무리수라는 사실에 모순이다.) 이제 $\frac{1}{N} < \log 2019 - \log 2018$를 만족하는 양의 정수 $N$에 대하여, 구간 $[0,\,1)$을 다음과 같이

\[ \left[ 0,\, \frac{1}{N} \right),\, \left[ \frac{1}{N}\,,\, \frac{2}{N} \right),\, \left[ \frac{2}{N}\,,\, \frac{3}{N} \right),\, \ldots,\, \left[ \frac{N-1}{N}\,,\, 1 \right) \tag*{(2)} \]

의 $N$개의 부분구간으로 나눈다. 그러면 비둘기집 원리(Pigeonhole principle)에 의하여 $(2)$의 부분구간들 중 적어도 하나의 부분구간에는 수열 $(1)$의 두개의 항이 존재하게 된다. 따라서 적당한 양의 정수 $\alpha$, $\beta$, $k$에 대하여 아래 부등식을 만족한다.

\[ \frac{k}{N} \leq \{ \alpha \log 2 \} < \{ \beta \log 2 \} < \frac{k+1}{N} \]

위 부등식을 정리하면

\[ 0< \{ \beta \log 2 \} - \{ \alpha \log 2 \} < \frac{1}{N} \]

를 얻을 수 있고, 이 사실로부터

\[ 0< \{ \abs{\beta - \alpha} \log 2 \} < \frac{1}{N} \quad \text{or} \quad 1 - \frac{1}{N} < \{ \abs{\beta - \alpha} \log 2 \} < 1 \]

을 얻는다. 이제 첫번째 경우를 살펴보자. (두번째 경우도 비슷한 방법으로 증명할 수 있다.) $\frac{1}{N} < \log 2019 - \log 2018$이라는 사실로부터 적당한 양의 정수 $n<N$이 존재하여,

\[ \log 2018 < \{ n \abs{\beta - \alpha} \log 2 \} < \log 2019 \]

가 성립한다. 마지막으로 $m = \lfloor n \abs{\beta - \alpha} \log 2 \rfloor$라 하면

\[ m + \log 2018 < n \abs{\beta - \alpha} \log 2 < m + \log 2019 \]

를 얻을 수 있고, 따라서 $2^{n \abs{\beta - \alpha}}$의 첫 네자리의 숫자가 $2018$이 된다..

Solution
Close