AMC 10 · 2010 · #24

학년 8 number-theory

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

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

📏 긴 풀이 💡 4 개 인사이트

문제

90! (곱 1 · 2 · 3… 90)을 적으면 끝에 0이 여러 개 이어진다. 그 끝의 0들을 무시하고, 바로 앞의 두 자리를 읽는다. 이 두 자리가 이루는 수를 n이라 할 때 n을 구하라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #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의 개수는 인수 5의 개수와 같아 ⌊90/5⌋+⌊90/25⌋ = 21. 떼어내면 N = 90!/10²¹, 구할 것은 N mod 100이다.

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

2STEP 2

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

100 = 4 × 25이니 mod 4와 mod 25로 나눠 푼다. 인수 2는 86인데 21만 빠져 N ≡ 0 (mod 4)이다.

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

3STEP 3

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

25 구간마다 5와 서로소인 수들의 곱은 -1인데, 그런 구간이 넷이라 (-1)⁴ ≡ 1 (mod 25)이다.

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

4STEP 4

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

5의 배수마다 5를 하나씩, 25의 배수는 하나 더 벗기면 4와 6만 남아 A ≡ 24 ≡ -1 (mod 25)이다.

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

5STEP 5

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

N = A/2²¹인데 2¹⁰ ≡ -1이라 2²¹ ≡ 2이고 그 역원은 13이니 N ≡ (-1) · 13 ≡ 12 (mod 25)이다.

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

6STEP 6

두 시계를 붙이기

100 미만에서 ≡ 0 (mod 4)과 ≡ 12 (mod 25)를 동시에 만족하는 값은 하나뿐이라 n = 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 나누기
두 시계를 붙이기