AMC 10 · 2006 · #22

학년 8 number-theory

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

legendre-formulap-adic-valuationfloor-functionfactorial extreme-principlework-backwards ↑ 선수 지식: legendre-formulafactorial

📏 긴 풀이 💡 4 개 인사이트

문제

세 양의 정수의 합이 2006이고, 그 계승들을 모두 곱한다. 그 곱이 끝에 가질 수 있는 가장 적은 0의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

489

(B)

492

(C)

495

(D)

498

(E)

501

풀이 과정

전략 극단의 원리

최솟값을 묻는 문제이므로 도구 #14(극단의 원리)가 풀이 전체의 뼈대를 정합니다. 어떤 삼중항도 뚫을 수 없는 하한을 증명하고, 그 하한 위에 정확히 서는 삼중항을 실제로 제시하는 것입니다. 두 절반 모두 필수이며, 앞쪽을 빠뜨리는 것이 이 문제를 틀리는 전형적인 방식입니다. 도구 #16(관점 바꾸기)은 애초에 셈을 가능하게 만듭니다. 인수 10을 직접 좇는 것은 가망이 없지만 10 = 2 · 5이고 계승에는 5보다 2가 훨씬 많으므로, n은 결국 5의 개수일 뿐입니다. 도구 #7(작은 문제로 쪼개기)은 그 5들을 거듭제곱 단위로 하나씩 셉니다 — 5의 배수, 다음은 25, 다음은 125, 다음은 625. 도구 #15(다르게 정리하기)는 최적화의 문을 여는 결정적인 수입니다. 열두 개의 항을 변수별이 아니라 분모별로 묶는데, 조건 a + b + c = 2006을 적용할 수 있는 배열은 그것뿐이기 때문입니다. 도구 #4(변수 도입하기)로 나머지에 이름을 붙여 각 줄이 지키는 하나의 부등식을 증명합니다. 이 부등식이 풀이 전체를 떠받치는 핵심 주장이므로 작은 예에서 눈으로 읽어내지 않고 나눗셈의 몫과 나머지로부터 증명합니다. 이어서 도구 #11(거꾸로 풀기)로 등호 조건을 거꾸로 따라가 네 줄이 동시에 등호가 되려면 a, b, c가 어떤 모양이어야 하는지 알아내고, 도구 #6(추측하고 확인하기)으로 그 삼중항을 직접 계산해 확인합니다.

1STEP 1

10이 아니라 5를 센다

더 드문 5만 세면 된다.

n = min(v₂(N), v₅(N)) = v₅(N) = v₅(a!) + v₅(b!) + v₅(c!)

2STEP 2

계승 하나에 들어 있는 5를 센다

표준 공식이 한 계승 안의 5를 세어 준다.

v₅(k!) = ⌊ k/5 ⌋ + ⌊ k/25 ⌋ + ⌊ k/125 ⌋ + ⌊ k/625 ⌋ (k ＜ 3125)

3STEP 3

열두 항을 분모별로 묶는다

분모로 묶으면 항들이 네 줄로 정리된다.

v₅(a!) + v₅(b!) + v₅(c!) &= ⌊ a/5⌋ + ⌊ b/5⌋ + ⌊ c/5⌋ ; &+ ⌊ a/25⌋ + ⌊ b/25⌋ + ⌊ c/25⌋ ; &+ ⌊ a/125⌋ + ⌊ b/125⌋ + ⌊ c/125⌋ ; &+ ⌊ a/625⌋ + ⌊ b/625⌋ + ⌊ c/625⌋

4STEP 4

모든 줄이 지키는 부등식 하나

각 줄이 버림 때문에 많아야 둘을 잃는다.

⌊ a/k ⌋ + ⌊ b/k ⌋ + ⌊ c/k ⌋ = ⌊ (a+b+c)/k ⌋ - ⌊ (r_a + r_b + r_c)/k ⌋ ≥ ⌊ (a+b+c)/k ⌋ - 2

5STEP 5

네 줄을 더해 단단한 하한을 얻는다

줄을 더하면 단단한 하한 492가 나온다.

401 + 80 + 16 + 3 = 500 ⟹ n ≥ 500 - 4 · 2 = 492

6STEP 6

거꾸로 따라가 등호가 되는 삼중항 찾기

거꾸로 따라가면 모든 등호를 만족하는 삼중항이 나온다.

a = b = 624 = 5⁴ - 1, c = 2006 - 2 · 624 = 758

7STEP 7

삼중항을 확인하고 n을 읽어낸다

확인하면 492가 맞는다, 보기 (B).

v₅(624!) + v₅(624!) + v₅(758!) = 152 + 152 + 188 = 492 → (B) 492

정답

492

다섯 보기 중 둘은 일반적인 이유만으로 탈락하는데, 이는 하한의 크기가 맞다는 좋은 신호입니다. 나머지 논증을 반대 방향으로 돌리면 ⌊ a/k ⌋ + ⌊ b/k ⌋ + ⌊ c/k ⌋ ≤ ⌊ 2006/k ⌋이므로 모든 삼중항에 대해 n ≤ 500이고, 보기 (E) 501은 그 자체로 불가능합니다. 5단계는 n ≥ 492를 주므로 보기 (A) 489도 불가능합니다. 남은 셋은 모두 도달 가능한 구간 492 ≤ n ≤ 500 안에 있어 크기만으로는 가릴 수 없고, 결국 구성을 해야 합니다. 보기 (C) 495가 이 문제가 겨냥한 함정입니다. 2006을 가능한 한 고르게 나누면 a = b = 669, c = 668이 되는데, 669와 668 각각에 대해 133 + 26 + 5 + 1 = 165이므로 합은 정확히 495입니다. 직관적인 '균등 분할' 답이 보기에 들어 있고, 실제 최솟값보다 3만큼 큽니다. 여기서는 수를 고르게 맞추는 것이 잘못된 본능이고, 나머지를 최대로 키우는 것이 옳은 본능입니다. 최적해가 유일하지 않다는 점도 알아 둘 만합니다. 운 좋은 한 삼중항만 믿기 전에 확인해 보면, (133, 624, 1249)도 성립합니다. v₅(133!) = 26 + 5 + 1 = 32, v₅(624!) = 152, v₅(1249!) = 249 + 49 + 9 + 1 = 308이고 합은 32 + 152 + 308 = 492입니다. 네 줄을 모두 등호로 만드는 삼중항은 모두 최적이며 그런 삼중항은 아주 많습니다. 확정된 것은 특정한 분할이 아니라 값 492입니다.

💡핵심 정리

끝의 0은 사실 5의 개수이고, 2006을 세 조각으로 나눌 때 5의 각 거듭제곱마다 많아야 5 두 개를 버린다 — 그러니 잃는 양이 결코 여덟을 넘지 못함을 증명한 뒤, 624처럼 모든 거듭제곱에서 한꺼번에 최대로 버리는 수를 고르면 된다.

10이 아니라 5를 센다
계승 하나에 들어 있는 5를 센다
열두 항을 분모별로 묶는다
모든 줄이 지키는 부등식 하나
네 줄을 더해 단단한 하한을 얻는다
거꾸로 따라가 등호가 되는 삼중항 찾기
삼중항을 확인하고 n을 읽어낸다