## 정답

④ $65$

## 해설

맨 왼쪽 숫자가 $1$인 자연수 $N$에는 $10^j\le N<2\cdot10^j$를 만족시키는 정수 $j$가 있다. $N=2^m$인 경우에는 오른쪽 부등식을 $2$로 나누어
$$
2^{m-1}<10^j\le 2^m
$$
을 얻는다. 즉, $2^{m-1}$을 두 배 하여 십진 자릿수가 늘어났을 때 $2^m$의 맨 왼쪽 숫자가 $1$이다.

같은 지수의 다른 수 $5^m$도 이 기준으로 볼 수 있을까? 두 수의 곱이 $10^m$이므로 $5^m=10^m/2^m$이다. 따라서
$$
10^j\le 5^m<2\cdot10^j
\quad\Longleftrightarrow\quad
2^m\le 10^{m-j}<2^{m+1}.
$$
양의 정수 지수에서 $2$의 거듭제곱은 $10$의 거듭제곱과 같을 수 없다. 그러므로 $5^m$의 맨 왼쪽 숫자가 $1$인 것은 $2^m$을 두 배 하여 자릿수가 늘어나는 것과 같다.

이제 네 수를 함께 보자. $2^n$은 $2^{n-1}$에서 $2^n$ 사이, $5^n$과 $2^{n+1}$은 **둘 다** $2^n$에서 $2^{n+1}$ 사이, $5^{n+1}$은 $2^{n+1}$에서 $2^{n+2}$ 사이의 자릿수 변화를 알려 준다. 결국 $n$이 조건에서 탈락하는 것은
$$
2^{n-1}<10^k<2^{n+2}
$$
인 정수 $k$가 있는 경우이다. $n=1$에서도 왼쪽 끝 $2^0=1$은 포함되지 않는다.

하나의 $10^k$ 때문에 몇 개의 $n$이 탈락할까? $2^{i-1}<10^k<2^i$라면 $n=i-2,i-1,i$가 탈락한다. 이때 서로 다른 $10^k$로 인해 같은 $n$을 두 번 빼는 일은 없다. 위 구간의 오른쪽 끝은 왼쪽 끝의 $8$배이고, 서로 다른 $10$의 거듭제곱은 적어도 $10$배 차이 나기 때문이다.

이제 양 끝에서 실제로 몇 개씩 빼는지 확인하자. 첫 경계는 $2^3<10<2^4$에 있다. 또 $\alpha=\log_{10}2$라 하면 주어진 범위에서
$$
198<660\alpha<661\alpha<199<662\alpha<200
$$
이다. 따라서 $10^1$부터 $10^{198}$까지의 경계는 모두 $2^{660}$보다 작아서 각각 세 개의 $n$을 제외한다. 마지막 경계 $10^{199}$는 $2^{661}$과 $2^{662}$ 사이에 있다. 이 경계가 제외하는 $660,661,662$ 중 범위에 드는 것은 $660$ 하나이다. 그러므로 구하는 개수는
$$
660-(3\times198+1)=\boxed{65}
$$
이다.

## 풀이 선택의 근거

| 선택 | 그때 아는 정보와 이 선택이 주는 정보 | 근거 |
|---|---|---|
| 네 수 중 맨 왼쪽 숫자가 $1$인 수가 있는 $n$을 세어 뺀다. | 맨 왼쪽 숫자가 $1$이라는 조건은 $10^j\le N<2\cdot10^j$라는 한 구간으로 나타낼 수 있다. 그 여집합이 발문에서 세는 대상이다. | 격차 지침 Ⅰ·Ⅲ-4, 십진 자릿값. |
| $2^m$에서 한 지수 앞을, $5^m$에서 한 지수 뒤를 본다. | 첫째 자리 조건의 오른쪽 끝에 $2$가 있다. $2^m$에서는 이 인수가 $2^{m-1}$을 드러낸다. 같은 지수의 $5^m$에는 $2^m5^m=10^m$을 쓰면 같은 십진 경계를 이용할 수 있고, 이번에는 $2^{m+1}$이 나타난다. | 격차 지침 Ⅱ·Ⅲ-2·Ⅳ, [12대수01-03] 지수법칙. |
| 세 번의 두 배 변화로 네 조건을 합친다. | $5^n$과 $2^{n+1}$은 같은 한 경계를 묻는다. 양옆의 두 조건까지 모으면 $2^{n-1}$에서 $2^{n+2}$ 사이에 자릿수 변화가 있는지만 판정하면 된다. | 격차 지침 Ⅳ·Ⅴ. 양의 지수에서 $2^m$과 $10^k$의 소인수가 달라 내부 끝점에서 등호가 생기지 않는다. |
| 개별 $n$ 대신 $10^k$ 하나가 제외하는 $n$을 센다. | 목표는 $n$의 목록이 아니라 개수이다. 경계가 어느 한 번의 두 배 변화에 놓이면 제외되는 지수는 연속한 세 개이고, 세 번을 두 배 해도 $8<10$이어서 다른 경계와 중복되지 않는다. | 격차 지침 Ⅰ·Ⅳ·Ⅶ. 중복 없이 세기 전에 한 $n$이 두 경계를 포함할 수 없음을 확인한다. |
| 처음과 마지막에서만 경계가 놓인 지수를 확인한다. | 중간 경계는 정확한 위치를 몰라도 같은 개수를 제외한다. 다만 처음 또는 마지막 경계가 주어진 지수 범위를 벗어나면 세 개 모두를 뺄 수 없다. $2^i$와 $10^k$의 비교를 $i\alpha$와 $k$의 비교로 바꾸면 이 차이를 확인할 수 있다. | 격차 지침 Ⅲ-3·Ⅶ, [12대수01-04·05] 로그의 성질과 상용로그, [12대수01-06] 증가성. |

**다른 풀이.** $D_i=\lfloor i\log_{10}2\rfloor$라 하면 $2^i$의 자릿수는 $D_i+1$이다. 네 수가 모두 조건에 맞으려면 $2^{n-1}$과 $2^{n+2}$의 자릿수가 같아야 한다. 두 수의 비가 $8<10$이므로 $D_{n+2}-D_{n-1}$은 $0$ 또는 $1$이다. 이를 모두 더하면 탈락하는 $n$의 개수가 되는데, 중간 항이 소거되어 $D_{660}+D_{661}+D_{662}-(D_0+D_1+D_2)=198+198+199$이다.

**수치와 선지 점검.** 원안의 상한 $100$을 $660$으로 바꾸고 로그의 범위를 마지막 경계의 위치가 결정되는 정밀도로 주었다. 처음 열 개 지수에서 본 결과가 열 개마다 반복된다고 하면 $66$개를 고르게 된다. 실제로 처음 $100$개에서 관찰되는 $1,11,\ldots,91$ 다음에 조건에 맞는 지수는 $101$이 아니라 $104$이다. 로그의 소수부분이 해당하는 구간의 길이에 비례한다고 가정해도 $660(1-3\log_{10}2)\approx63.96$으로 반올림하면 $64$이다. 마지막 경계까지 세고 모두 세 번씩 빼면 $63$이다. 세 값 모두 정답과 다른 선지에 있다. 뒷부분의 계산은 지수함수의 그래프 추론이 아니라 유한한 범위의 중복 없는 계수다.
