AMC 10 · 2004 · #25

학년 9 number-theorycounting

유형 Pair-Sum Invariant └ 세부 유형 Universe Total Minus Known

place-valuedigit-countingcomplementary-countingleading-digit complementary-countingpattern-recognition ↑ 선수 지식: place-value

📏 긴 풀이 💡 4 개 인사이트

문제

2의 2004제곱은 604자리이고 첫 자리 숫자가 1이다. 0제곱부터 2003제곱까지 2004개의 거듭제곱 중 첫 자리 숫자가 4인 것의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

194

(B)

195

(C)

196

(D)

197

(E)

198

풀이 과정

전략 관점 바꾸기

"첫 자리 숫자가 d이다"는 사실 그 수가 10의 거듭제곱 구간의 어느 조각에 들어가는지에 대한 이야기이므로, 먼저 그렇게 바꿔 쓴다. 그러면 두 배 하기가 그 조각들을 정해진 패턴으로 옮긴다. 첫 자리가 1인 수 다음에는 첫 자리가 2나 3인 수가, 그다음에는 4부터 7까지인 수가 온다. 이 패턴이 2004개의 지수를 크기를 세기 쉬운 몇 개의 부류로 나누고, 첫 자리가 4인 부류는 남은 부류에서 한 번 더 두 배 하면 닿는다.

1STEP 1

"첫 자리 숫자"를 구간으로 바꾸기

첫 자리 숫자는 사실 숫자가 아니라 범위에 관한 말이다.

10^j ≤ N ＜ 10^j+1 이고 d · 10^j ≤ N ＜ (d+1) · 10^j ⇔ N은 j+1자리이고 첫 자리가 d

2STEP 2

각 구간에는 첫 자리가 1인 거듭제곱이 정확히 하나

각 범위에는 1로 시작하는 거듭제곱이 정확히 하나씩 있고 건너뛰는 범위는 없다.

2^k-1 ＜ 10^j ≤ 2^k ⟹ 10^j ≤ 2^k ＜ 2 · 10^j

3STEP 3

1로 시작하는 개수 세기

주어진 사실이 그 개수를 603으로 만든다.

5 · 10⁶⁰² ≤ 2²⁰⁰³ ＜ 10⁶⁰³ ⟹ #{k ≤ 2003 : 2^k 는 1 로 시작} = 603

4STEP 4

두 배 사슬 따라가기

두 배가 1로 시작하는 거듭제곱을 다른 두 부류와 일대일로 대응시킨다.

1 ⟶ {2,3} ⟶ {4,5,6,7} ⟶ {8,9} 또는 1

5STEP 5

밀어도 집합 밖으로 나가지 않는지 확인

밀어낸 지수를 확인하면 모두 집합 안에 머문다.

#{2,3} = #{4,5,6,7} = #{1} = 603

6STEP 6

여집합 세기

그래서 남은 부류는 195개다.

#{8,9} = 2004 - 3 · 603 = 195

7STEP 7

한 번 더 밀어 첫 자리 4로 가기

한 번 더 반으로 나누면 그 부류가 첫 자리 4와 짝지어져 195, 보기 (B).

2^k 가 8 또는 9 로 시작 ⇔ 2^k-1 가 4 로 시작 ⟹ #{4} = 195

정답

195

먼저 크기를 어림해 보자. 2의 거듭제곱이 4로 시작하는 것은 앞부분이 [4,5)에 놓일 때이고, 이는 한 구간에서 log₁₀ 5/4 ≈ 0.0969의 비율이므로 대략 0.0969 · 2004 ≈ 194.2개가 예상된다. 답 195는 바로 그 자리에 있다. 그런데 194와 196도 마찬가지로 그 근처에 있어서 어림값만으로는 결정할 수 없고, 그래서 정확한 구간 논증이 필요하다. 다음으로 작은 범위에서 직접 확인해 보자. 2⁰부터 2²⁰까지의 첫 자리 숫자는 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1이다. k = 0부터 19까지에서 첫 자리가 4인 것은 정확히 두 개(k = 2, k = 12)이고 8이나 9로 시작하는 것도 정확히 두 개(k = 3, k = 13)이며, 각 8은 4 바로 다음 자리에 있다. 마지막 단계에서 쓴 짝짓기가 손으로 확인된 셈이다. 같은 목록에서 1로 시작하는 것은 k = 0, 4, 7, 10, 14, 17, 20이므로, 1로 시작하는 수가 구간마다 한 번씩만 나오고 건너뛰지도 겹치지도 않음을 볼 수 있다.

💡핵심 정리

첫 자리 숫자는 사실 범위를 다르게 말한 것이고 두 배 하기는 그 범위를 정해진 순환으로 옮긴다. 그래서 거대한 거듭제곱을 하나도 적지 않고도 첫 자리를 셀 수 있다.

"첫 자리 숫자"를 구간으로 바꾸기
각 구간에는 첫 자리가 1인 거듭제곱이 정확히 하나
1로 시작하는 개수 세기
두 배 사슬 따라가기
밀어도 집합 밖으로 나가지 않는지 확인
여집합 세기
한 번 더 밀어 첫 자리 4로 가기