AMC 10 · 2010 · #24
학년 8 number-theory90!의 0이 아닌 마지막 두 자리 숫자로 이루어진 수가 n이다. n은 얼마인가?
답을 골라 클릭하세요.
AMC 10 2010 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + CCSS 풀이
이해
문제 재정리: $90!$ (곱 $1\cdot 2\cdot 3\cdots 90$)을 적으면 끝에 $0$이 여러 개 이어진다. 그 끝의 $0$들을 무시하고, 바로 앞의 두 자리를 읽는다. 이 두 자리가 이루는 수를 $n$이라 할 때 $n$을 구하라.
주어진 것: $90! = 1\cdot 2\cdot 3\cdots 90$; 끝에 이어지는 $0$들을 제외한, $0$이 아닌 마지막 두 자리를 취한다; 보기: (A) $12$, (B) $32$, (C) $48$, (D) $52$, (E) $68$
구하는 것: $90!$의 $0$이 아닌 마지막 두 자리가 이루는 두 자리 수 $n$
이해
문제 재정리: $90!$ (곱 $1\cdot 2\cdot 3\cdots 90$)을 적으면 끝에 $0$이 여러 개 이어진다. 그 끝의 $0$들을 무시하고, 바로 앞의 두 자리를 읽는다. 이 두 자리가 이루는 수를 $n$이라 할 때 $n$을 구하라.
주어진 것: $90! = 1\cdot 2\cdot 3\cdots 90$; 끝에 이어지는 $0$들을 제외한, $0$이 아닌 마지막 두 자리를 취한다; 보기: (A) $12$, (B) $32$, (C) $48$, (D) $52$, (E) $68$
계획
주요 도구: #9 더 쉬운 문제로 줄이기
보조 도구: #7 작은 문제로 쪼개기, #5 패턴 찾기
도구 #9 (더 쉬운 문제로 줄이기): $90!$ 전체를 계산하는 것은 불가능하므로, 훨씬 작은 나머지 문제로 바꾼다. $0$이 아닌 마지막 두 자리는 $N \bmod 100$인데, 여기서 $N$은 $90!$에서 끝의 $0$을 떼어낸 수다. 도구 #7 (작은 문제로 쪼개기): $100 = 4\times 25$이고 $4$와 $25$는 공통인수가 없으므로, 하나의 어려운 나머지를 쉬운 $N \bmod 4$와 조금 어려운 $N \bmod 25$로 나눈 뒤 다시 합친다. 도구 #5 (패턴 찾기): $\bmod 25$에서 연속한 $25$개의 깨끗한 묶음마다 같은 흔적이 남고, $2$의 거듭제곱은 짧은 주기로 반복된다 — 이 패턴들이 거대한 곱을 몇 단계로 줄여 준다.
실행 — 정답: A
5.NBT.A.2 단계 1 끝의 0을 세어 떼어내기
- 수 끝의 $0$은 그 안에 들어 있는 인수 $10 = 2\times 5$ 하나마다 하나씩 생긴다.
- $90!$에는 인수 $2$가 인수 $5$보다 훨씬 많으므로, 끝의 $0$ 개수는 인수 $5$의 개수와 같다.
- $90$ 이하의 $5$의 배수를 세면 ($18$개), 여기에 $25$의 배수 $25,50,75$마다 $5$를 하나씩 더 세면 ($3$개 추가) 된다.
- 따라서 $90!$은 끝에 정확히 $21$개의 $0$을 가진다.
- 이를 떼어내어 $N = 90!/10^{21}$이라 하자.
- $90!$의 $0$이 아닌 마지막 두 자리는 $N$의 마지막 두 자리, 즉 $N \bmod 100$이다.
💡 끝의 $0$은 모두 $2$ 하나와 $5$ 하나의 짝인데, 더 귀한 쪽인 $5$를 세면 $0$의 개수가 나온다.
6.NS.B.4 단계 2 목표를 4-시계와 25-시계로 나누기
- $100 = 4\times 25$이고 $4$와 $25$는 공통인수가 없으므로, $N \bmod 4$와 $N \bmod 25$를 알면 $N \bmod 100$이 유일하게 정해진다.
- $\bmod 4$ 부분은 쉽다: $90!$에는 인수 $2$가 $45+22+11+5+2+1 = 86$개 있고, $0$을 떼면서 그중 $21$개만 없어져 $65$개가 남는다.
- $65 \ge 2$이므로 $N$은 $4$로 나누어떨어진다.
- 즉 $N \equiv 0 \pmod 4$이다.
- 진짜 일은 $\bmod 25$ 부분이다.
💡 서로소인 두 시계 — 4-시계와 25-시계 — 는 $0$부터 $99$까지 각 값에 서로 다른 눈금을 주므로, 두 답을 합치면 마지막 두 자리가 복원된다.
4.OA.C.5 단계 3 묶음별로 5를 떼어내기 (mod 25)
- $A = 90!/5^{21}$, 즉 $90!$에서 인수 $5$를 모두 나눈 수를 다룬다 (나중에 $2$도 나눈다).
- 먼저 $1$부터 $90$까지 중 $5$의 배수가 아닌 수들을 처리한다.
- 패턴은 이렇다: 연속한 $25$개의 정수 묶음에서 $5$와 서로소인 것들의 곱은 $-1 \pmod{25}$이다 (윌슨 정리 유형의 사실).
- 묶음 $1$–$25$, $26$–$50$, $51$–$75$가 각각 $-1$을 주고, 남은 $76$–$90$도 $-1$을 준다.
- 따라서 $5$의 배수가 아닌 수들의 곱은 모두 합쳐 $(-1)^4 \equiv 1 \pmod{25}$이다.
💡 $25$개짜리 깨끗한 묶음마다 똑같이 $-1$이라는 흔적을 남기므로, 묶음이 몇 개인지만 세면 된다.
4.OA.B.4 단계 4 5의 배수에서 5를 벗겨내기
- $5$부터 $90$까지의 $5$의 배수는 $5\cdot 1, 5\cdot 2, \ldots, 5\cdot 18$이다.
- 각각에서 $5$를 하나씩 빼면 $5$를 $18$개 쓰고 $1\cdot 2\cdots 18 = 18!$이 남는다.
- 그런데 $18!$ 안에도 아직 $5$의 배수($5,10,15$)가 숨어 있으므로, 그 셋에서 $5$를 하나씩 더 빼면 ($3$개 추가, 합 $21$개) 원래의 $25,50,75$에서 온 $1\cdot 2\cdot 3$이 남는다.
- 이제 남은 것들을 $\bmod 25$로 줄인다: $1$–$18$ 중 $5$와 서로소인 수들의 곱은 $4$, 그리고 $1\cdot 2\cdot 3 = 6$이다.
- 3단계의 $1$과 합치면 $A \equiv 1\cdot 4\cdot 6 = 24 \equiv -1 \pmod{25}$이다.
💡 $5$의 배수마다 $5$를 하나씩 벗겨내면 무서운 곱이 손으로 끝낼 수 있는 작은 계승으로 바뀐다.
8.EE.A.1 단계 5 주기적인 거듭제곱으로 2 나누기
- $0$을 뗄 때 $2$도 함께 뗐으므로 $N = A/2^{21}$이고, $\bmod 25$에서는 $A$에 $2^{21}$의 역원을 곱하는 것과 같다.
- $\bmod 25$에서 $2$의 거듭제곱에 지수 규칙을 쓰면 $2^{10} = 1024 \equiv -1$이므로 $2^{20} \equiv 1$, $2^{21} \equiv 2 \pmod{25}$이다.
- $\bmod 25$에서 $2$의 역원은 $13$이다 (왜냐하면 $2\cdot 13 = 26 \equiv 1$).
- 따라서 $N \equiv A\cdot 13 \equiv (-1)\cdot 13 \equiv -13 \equiv 12 \pmod{25}$이다.
💡 $\bmod 25$에서 $2$의 거듭제곱은 $20$단계마다 반복되므로, 거대한 지수도 곧바로 읽을 수 있는 작은 지수로 줄어든다.
6.NS.B.4 단계 6 두 시계를 붙이기
- 이제 $100$보다 작으면서 $N \equiv 0 \pmod 4$ (2단계)와 $N \equiv 12 \pmod{25}$ (5단계)를 동시에 만족하는 $N$이 필요하다.
- $12$를 확인해 보자: $12 = 3\cdot 4$이므로 $12 \equiv 0 \pmod 4$이고, 당연히 $12 \equiv 12 \pmod{25}$이다.
- 두 조건이 모두 성립하고, $4$와 $25$가 서로소이므로 $\bmod 100$에서의 답은 유일하다.
- 따라서 $N \equiv 12 \pmod{100}$이다.
- $90!$의 $0$이 아닌 마지막 두 자리는 $12$이고, $n = 12$, 즉 보기 (A)이다.
💡 $0$–$99$ 중에서 4-시계로 $0$, 25-시계로 $12$를 동시에 가리키는 수는 오직 $12$뿐이다.
5.NBT.A.2 수 끝의 $0$은 그 안에 들어 있는 인수 $10 = 2\times 5$ 하나마다 하나씩 생긴다. $90!$에는 인수 $2$가 인수 $5$보다 6.NS.B.4 $100 = 4\times 25$이고 $4$와 $25$는 공통인수가 없으므로, $N \bmod 4$와 $N \bmod 25$를 알면 $N \bm 4.OA.C.5 $A = 90!/5^{21}$, 즉 $90!$에서 인수 $5$를 모두 나눈 수를 다룬다 (나중에 $2$도 나눈다). 먼저 $1$부터 $90$까지 4.OA.B.4 $5$부터 $90$까지의 $5$의 배수는 $5\cdot 1, 5\cdot 2, \ldots, 5\cdot 18$이다. 각각에서 $5$를 하나씩 8.EE.A.1 $0$을 뗄 때 $2$도 함께 뗐으므로 $N = A/2^{21}$이고, $\bmod 25$에서는 $A$에 $2^{21}$의 역원을 곱하는 것과 6.NS.B.4 이제 $100$보다 작으면서 $N \equiv 0 \pmod 4$ (2단계)와 $N \equiv 12 \pmod{25}$ (5단계)를 동시에 만 검토
합리성 확인: 두 확인은 서로 독립적이므로 둘 다 통과하면 강한 근거가 된다. $\bmod 4$: $12$는 $4$의 배수라 $N \equiv 0$에 맞는다. $\bmod 25$: 되짚어 보면 $A \equiv -1$이고 $2^{21}\equiv 2$로 나누면 $-1\cdot 13 = -13 \equiv 12$이다. 모든 보기($12,32,48,52,68$)가 $4$의 배수라 우리의 $\bmod 4$ 결과와 일치하므로, 실제로 답을 고르는 것은 $\bmod 25$ 단계다. 그 중 $\equiv 12 \pmod{25}$인 것은 $12$뿐이다 ($32\equiv 7$, $48\equiv 23$, $52\equiv 2$, $68\equiv 18$). 이 유일한 일치가 (A)를 확정한다.
대안 접근: 묶음-윌슨 지름길 대신, 오일러 정리로 $A \bmod 25$를 직접 밀어붙일 수도 있다. $5$를 떼어 $A = 90!/5^{21}$을 얻으면, $25$와 서로소인 인수들은 $x^{20} \equiv 1 \pmod{25}$를 만족하므로, 곱을 완전잉여계 묶음과 나머지 항으로 나누면 똑같이 $A \equiv -1$이 나온다. 이를 $2^{21} \equiv 2$로 나누고 $N \equiv 0 \pmod 4$와 중국인의 나머지 정리로 합치면 다시 $12$가 된다.
사용된 CCSS 표준 (최저 학년 8)
5.NBT.A.2Explain patterns in number of zeros and placement of decimal point (끝의 $0$이 $2\times 5$ 짝에서 생김을 알아보고, 인수 $5$를 세어 떼어낼 $0$의 개수를 구하는 데 사용.)6.NS.B.4Find greatest common factor and least common multiple of two numbers ($\bmod 100$을 서로소인 $\bmod 4$와 $\bmod 25$로 나누고 유일하게 다시 합치는 데 사용.)4.OA.C.5Generate a number or shape pattern following a given rule ($5$와 서로소인 $25$개짜리 묶음마다 곱이 $-1 \pmod{25}$이 되는 패턴을 알아보는 데 사용.)4.OA.B.4Find all factor pairs and recognize multiples; determine prime or composite ($5$의 배수마다 $5$를 하나씩 인수로 빼내어 큰 곱을 작은 계승으로 줄이는 데 사용.)8.EE.A.1Know and apply the properties of integer exponents ($2$의 거듭제곱의 짧은 주기를 이용해 $2^{21}$을 $\bmod 25$로 줄이고 나누는 데 사용.)
⭐ 거대한 계승의 $0$이 아닌 마지막 자리를 찾으려면, 끝의 $0$을 떼어낸 뒤 그 수를 4-시계와 25-시계로 따로 추적하고 두 눈금을 다시 붙이면 된다.
⭐ 거대한 계승의 $0$이 아닌 마지막 자리를 찾으려면, 끝의 $0$을 떼어낸 뒤 그 수를 4-시계와 25-시계로 따로 추적하고 두 눈금을 다시 붙이면 된다.
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.