AMC 10 · 2010 · #23

학년 8 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

legendre-formulachinese-remainder-theoremeulers-theoremmodular-arithmeticfactorial identify-subproblems ↑ 선수 지식: modular-arithmetic

📏 긴 풀이 💡 4 개 인사이트

문제

거대한 계승의 끝에 0이 줄지어 있고, 그 바로 앞 두 자리를 묻는다. 그 두 자리를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #9 (더 쉬운 문제로 줄이기): 90! 전체를 계산하는 것은 불가능하므로, 훨씬 작은 나머지 문제로 바꾼다. 0이 아닌 마지막 두 자리는 N mod 100인데, 여기서 N은 90!에서 끝의 0을 떼어낸 수다. 도구 #7 (작은 문제로 쪼개기): 100 = 4 × 25이고 4와 25는 공통인수가 없으므로, 하나의 어려운 나머지를 쉬운 N mod 4와 조금 어려운 N mod 25로 나눈 뒤 다시 합친다. 도구 #5 (패턴 찾기): mod 25에서 연속한 25개의 깨끗한 묶음마다 같은 흔적이 남고, 2의 거듭제곱은 짧은 주기로 반복된다 — 이 패턴들이 거대한 곱을 몇 단계로 줄여 준다.

1STEP 1

끝의 0을 세어 떼어내기

끝의 0은 21개다.

⌊ 90/5 ⌋ + ⌊ 90/25 ⌋ = 18 + 3 = 21, N = 90!/10²¹

2STEP 2

목표를 4-시계와 25-시계로 나누기

100은 서로소인 두 시계로 나뉜다.

100 = 4 · 25, gcd(4,25)=1; #(인수 2) = 86, 86-21 = 65 ≥ 2 → N ≡ 0 (mod 4)

3STEP 3

묶음별로 5를 떼어내기 (mod 25)

2가 충분히 남아 작은 시계는 0을 가리킨다.

(1 · 2 · 3 · 4)(6 · 7 · 8 · 9)(11 · 12 · 13 · 14) ≡ (-1)(-1)(-1) ≡ -1; (-1)⁴ ≡ 1 (mod 25)

4STEP 4

5의 배수에서 5를 벗겨내기

묶음으로 나누면 큰 시계가 다뤄진다.

1 · 2… 18 (5의 배수 제외)≡ 4 · 1 · 2 · 3= 6 · 1₃단계 = 24 ≡ -1 (mod 25)

5STEP 5

주기적인 거듭제곱으로 2 나누기

주기적인 거듭제곱이 남은 2를 되돌린다.

2¹⁰ ≡ -1, 2²¹ ≡ 2, 2⁻¹ ≡ 13 (mod 25); N ≡ (-1) · 13 ≡ 12 (mod 25)

6STEP 6

두 시계를 붙이기

시계를 붙이면 12, 보기 (A).

N ≡ 0 (mod 4), N ≡ 12 (mod 25) → N ≡ 12 (mod 100); n = 12 (A)

정답

두 확인은 서로 독립적이므로 둘 다 통과하면 강한 근거가 된다. mod 4: 12는 4의 배수라 N ≡ 0에 맞는다. mod 25: 되짚어 보면 A ≡ -1이고 2²¹≡ 2로 나누면 -1 · 13 = -13 ≡ 12이다. 모든 보기(12,32,48,52,68)가 4의 배수라 우리의 mod 4 결과와 일치하므로, 실제로 답을 고르는 것은 mod 25 단계다. 그 중 ≡ 12 (mod 25)인 것은 12뿐이다 (32≡ 7, 48≡ 23, 52≡ 2, 68≡ 18). 이 유일한 일치가 (A)를 확정한다.

💡핵심 정리

거대한 계승의 0이 아닌 마지막 자리를 찾으려면, 끝의 0을 떼어낸 뒤 그 수를 4-시계와 25-시계로 따로 추적하고 두 눈금을 다시 붙이면 된다.

끝의 0을 세어 떼어내기
목표를 4-시계와 25-시계로 나누기
묶음별로 5를 떼어내기 (mod 25)
5의 배수에서 5를 벗겨내기
주기적인 거듭제곱으로 2 나누기
두 시계를 붙이기