AMC 10 · 2011 · #23

학년 8 arithmetic

유형 Modular Cycle Frequency Count └ 세부 유형 Power-Cycle Residue

modular-arithmeticbinomial-theoremplace-value easier-related-problem ↑ 선수 지식: modular-arithmetic

📏 중간 풀이 💡 3 개 인사이트

문제

$2011^{2011}?$ 의 백의 자리 숫자는 무엇인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 10 2011 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 거대한 수 $2011^{2011}$의 백의 자리 숫자를 구하라 — 오른쪽에서 세 번째 자리의 숫자다.

주어진 것: 대상은 $2011^{2011}$ (전부 적기에는 너무 큰 수).; 필요한 것은 단 한 자리, 백의 자리뿐이다.; 선택지: (A) $1$, (B) $4$, (C) $5$, (D) $6$, (E) $9$.

구하는 것: $2011^{2011}$의 백의 자리 숫자, 즉 $2011^{2011} \bmod 1000$의 백의 자리.

이해

문제 재정리: 거대한 수 $2011^{2011}$의 백의 자리 숫자를 구하라 — 오른쪽에서 세 번째 자리의 숫자다.

주어진 것: 대상은 $2011^{2011}$ (전부 적기에는 너무 큰 수).; 필요한 것은 단 한 자리, 백의 자리뿐이다.; 선택지: (A) $1$, (B) $4$, (C) $5$, (D) $6$, (E) $9$.

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #7 작은 문제로 쪼개기, #2 빠짐없이 나열하기, #5 패턴 찾기

$2011^{2011}$은 엄청나게 크지만, 문제는 오른쪽 끝 근처의 한 자리만 묻는다. 도구 #9 (더 쉬운 문제로 줄이기)로 이 거인을 작게 만든다: 백의 자리는 마지막 세 자리로 정해지고, 곱의 마지막 세 자리는 인수의 마지막 세 자리에만 의존하므로 $2011^{2011}$과 $11^{2011}$은 마지막 세 자리가 같다. 이제 $11^{2011} \bmod 1000$만 구하면 된다. 도구 #7 (작은 문제로 쪼개기)로 이를 연다: $11 = 10 + 1$로 쓰고 $(10+1)^{2011}$을 전개하면 거의 모든 항이 $1000$의 배수라 사라지고, 계산할 조각은 셋뿐이다. 도구 #2 (빠짐없이 나열하기)로 그 세 조각을 더한다. 도구 #5 (패턴 찾기)로 독립적인 검산을 한다.

실행 — 정답: D

#9 더 쉬운 문제로 줄이기 5.NBT.A.1 단계 1

거인을 마지막 세 자리로 줄이기

백의 자리는 그 수의 마지막 세 자리에만 관심이 있다.
수를 곱할 때 답의 각 자리는 그 자리 이하의 자리들로만 만들어지므로, 곱의 마지막 세 자리는 인수의 마지막 세 자리에만 의존한다.
$2011$은 $011$로 끝나므로 $2011^{2011}$과 $11^{2011}$은 마지막 세 자리가 같다.
문제는 $11^{2011} \bmod 1000$을 구하는 것으로 바뀐다.

$$2011^{2011} \equiv 11^{2011} \pmod{1000}$$

💡 받아올림은 왼쪽으로만 가므로, 멀리 있는 높은 자리는 백의 자리를 건드리지 못한다.

#7 작은 문제로 쪼개기 8.EE.A.1 단계 2

11을 10 + 1로 다시 쓰기

$11 = 10 + 1$로 쓰면 $11^{2011} = (10 + 1)^{2011}$이다.
이 곱을 전개하는 것은 $(10 + 1)$을 $2011$개 곱하는 것이다.
각 항은 몇 개의 $10$과 몇 개의 $1$의 곱이다.
$10$을 셋 이상 쓴 항은 $10^3 = 1000$이라는 인수를 가지므로 $1000$의 배수가 되어 마지막 세 자리에 아무것도 기여하지 않는다.
$10$을 $0$개, $1$개, $2$개 쓴 항만 살아남는다.

$$11^{2011} = (10+1)^{2011}, \qquad 10^3 = 1000 \equiv 0 \pmod{1000}$$

💡 $1000$ 이상의 $10$의 거듭제곱은 모듈로 $1000$에서 보이지 않으므로, 낮은 거듭제곱만 중요하다.

#7 작은 문제로 쪼개기 6.EE.A.3 단계 3

살아남는 세 조각만 남기기

살아남는 세 종류의 항을 센다.
$10$이 $0$개: 전부 $1$인 항 하나가 $1$을 기여한다.
$10$이 정확히 $1$개: $2011$개의 인수 중 어느 하나가 $10$을 낼지 고르면 $2011$가지이고, $2011 \times 10 = 20110$이며 마지막 세 자리는 $110$이다.
$10$이 정확히 $2$개: $2011$개의 인수 중 $2$개를 고르면 되고, 그 쌍의 개수는 $\tfrac{2011 \times 2010}{2} = 2011 \times 1005 = 2{,}021{,}055$이며, 이만큼의 백은 $2{,}021{,}055 \times 100$이다.
마지막 세 자리는 $2{,}021{,}055$의 일의 자리 $5$에서 나오므로 $500$을 기여한다.

$$1 \;+\; \underbrace{2011\times10}_{\equiv\,110} \;+\; \underbrace{\tfrac{2011\times2010}{2}\times100}_{\equiv\,500} \pmod{1000}$$

💡 거듭제곱 전개는 정리된 세기일 뿐이다: 십이 없는 항 하나, 십이 하나인 항 $n$개, 십이 둘인 항은 인수의 '쌍'.

#2 빠짐없이 나열하기 4.NBT.B.4 단계 4

조각을 더해 자리 읽기

살아남은 세 기여를 모듈로 $1000$으로 더한다: $1 + 110 + 500 = 611$.
따라서 $2011^{2011}$의 마지막 세 자리는 $611$이다.
백의 자리는 $6$이고, 선택지 (D)이다.

$$11^{2011} \equiv 1 + 110 + 500 = 611 \pmod{1000} \;\Rightarrow\; \text{백의 자리} = 6 \;\Rightarrow\; \textbf{(D)}$$

💡 작은 수 셋을 더하면 $611$; 가운데 자리가 답이다.

#5 패턴 찾기 4.OA.C.5 단계 5

독립적인 방법으로 검산하기

$611$을 다른 방법으로 확인한다.
먼저 마지막 두 자리: $1 + (2011 \times 10 \bmod 100) = 1 + 10 = 11$이므로 $2011^{2011}$은 $\ldots11$로 끝난다 — $611$과 일치한다.
다음으로 $11$을 모듈로 $1000$에서 반복 제곱(매 단계 마지막 세 자리만 유지)하는 독립적인 검산도 $611$에 도달한다: $11^2 \equiv 121$, $11^4 \equiv 641$, $11^8 \equiv 881$, 지수의 합이 $2011$이 되도록 거듭제곱들을 결합하면 $611$이 나온다.
두 경로가 일치한다.

$11^{2011} \equiv 11 \pmod{100}$ 이고 반복 제곱 $\Rightarrow 611 \pmod{1000}$

💡 다른 길로도 같은 $611$에 도착하면 계산 실수 가능성이 매우 낮아진다.

[1] #9 5.NBT.A.1 백의 자리는 그 수의 마지막 세 자리에만 관심이 있다. 수를 곱할 때 답의 각 자리는 그 자리 이하의 자리들로만 만들어지므로, 곱의 마지막 세

[2] #7 8.EE.A.1 $11 = 10 + 1$로 쓰면 $11^{2011} = (10 + 1)^{2011}$이다. 이 곱을 전개하는 것은 $(10 + 1)$을 $201

[3] #7 6.EE.A.3 살아남는 세 종류의 항을 센다. $10$이 $0$개: 전부 $1$인 항 하나가 $1$을 기여한다. $10$이 정확히 $1$개: $2011$개의

[4] #2 4.NBT.B.4 살아남은 세 기여를 모듈로 $1000$으로 더한다: $1 + 110 + 500 = 611$. 따라서 $2011^{2011}$의 마지막 세 자리는

[5] #5 4.OA.C.5 $611$을 다른 방법으로 확인한다. 먼저 마지막 두 자리: $1 + (2011 \times 10 \bmod 100) = 1 + 10 = 11$

검토

합리성 확인: 마지막 세 자리 $611$은 $11$로 끝나는데, 이는 여기서 마지막 두 자리가 $11$이 되는 것과 정확히 맞는다. 두 독립적인 계산 — 잘라낸 $(10+1)^{2011}$ 전개와 모듈로 $1000$ 반복 제곱 — 이 모두 $611$을 주므로 백의 자리 $6$은 확실하다. 선택지 중 (D) $6$만 일치하며, 오답 $1, 4, 5, 9$는 흔한 실수(십이 둘인 항 빠뜨리기, $2011 \times 2010$의 절반을 잘못 구하기, 다른 자리를 읽기)에 대응한다.

대안 접근: 중국인의 나머지 정리(CRT)를 쓴다. $1000 = 8 \times 125$로 나눈다. 모듈로 $8$: $11 \equiv 3$이고 $3^2 \equiv 1$이므로 $11^{2011} \equiv 3^{2011} \equiv 3 \pmod 8$. 모듈로 $125$: 오일러 정리($\varphi(125) = 100$)로 $11^{2011} = 11^{2000} \cdot 11^{11} \equiv 11^{11} \pmod{125}$이고, 이는 $611 \bmod 125 = 111$로 줄어든다. $\equiv 3 \pmod 8$이면서 $\equiv 111 \pmod{125}$인 $1000$ 이하의 유일한 나머지는 $611$ — 같은 백의 자리 $6$.

사용된 CCSS 표준 (최저 학년 8)

5.NBT.A.1 한 자리의 숫자가 오른쪽 자리에서 나타내는 값의 10배, 왼쪽 자리에서 나타내는 값의 1/10을 나타냄을 이해하기 (백의 자리가 마지막 세 자리에만 의존함을 보고, 밑 $2011$을 $11$로 바꾸기.)
8.EE.A.1 정수 지수의 성질을 알고 적용하여 동등한 수식을 만들기 ($11^{2011}$을 $(10+1)^{2011}$로 다시 쓰고 $10^3 = 1000 \equiv 0$을 이용해 높은 $10$의 거듭제곱을 버리기.)
6.EE.A.3 연산의 성질을 적용하여 동등한 식 만들기 (분배법칙으로 $(10+1)^{2011}$을 전개하고 살아남는 세 항을 세기.)
4.NBT.B.4 표준 알고리즘으로 여러 자리 자연수를 능숙하게 더하고 빼기 (살아남은 세 기여 $1 + 110 + 500 = 611$을 더하기.)
4.OA.C.5 주어진 규칙을 따르는 수 또는 도형 패턴을 만들고 그 특징을 찾기 (마지막 자리 패턴과 모듈로 $1000$ 반복 제곱으로 $611$을 검산하기.)

⭐ $2011^{2011}$의 백의 자리는 마지막 세 자리만 빼고 다 버리면 된다: $2011$은 $11$이 되고, $(10+1)^{2011}$을 전개하면 조각 셋만 남아 $1 + 110 + 500 = 611$ — 그래서 백의 자리는 $6$이다.