AMC 10 · 2015 · #23

학년 6 arithmetic

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

legendre-formulafactorialfloor-function casework ↑ 선수 지식: factoriallegendre-formula

📏 긴 풀이 💡 4 개 인사이트

문제

n! 같은 계승은 끝에 0이 여러 개 붙는다. n!의 끝자리 0의 개수를 k라고 하자. 우리가 찾는 것은 (2n)!의 끝자리 0이 정확히 3k개, 즉 n!의 세 배가 되는 모든 자연수 n ＞ 4이다. 그런 n 중 가장 작은 네 개를 더해 s를 구하고, s의 각 자리 숫자의 합을 답하면 된다.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 추측하고 확인하기

답을 한 번에 내주는 깔끔한 공식은 없지만, 끝자리 0을 세는 법만 알면 후보 n 하나하나는 쉽게 확인할 수 있다. 그래서 도구 #6(추측하고 확인하기)이 탐색을 이끈다: n=5,6,7,…을 순서대로 시험해 조건에 맞는 것만 남긴다. 시험 전에 도구 #16(관점 바꾸기)이 각 확인을 값싸게 만든다. 10의 인수를 쫓는 대신 5의 인수만 세는 것이다. 5는 2보다 드물어서 0의 개수를 결정하기 때문이다. 도구 #2(빠짐없이 나열하기)는 n, k, (2n)!의 0 개수를 작은 표로 정리해, 빠뜨림 없이 네 개의 당첨자를 또렷이 드러낸다.

1STEP 1

오직 5만 센다

0 하나에는 2와 5가 짝으로 필요한데 5가 2보다 먼저 동나므로, 계승의 0 개수는 그 안의 5의 개수와 같다.

m!의 끝자리 0의 개수 = (m! 안의 5의 인수 개수)

2STEP 2

5를 세는 방법

m! 안의 5의 개수는 m 이하의 5의 배수를 세고, 다음으로 25의 배수를 더하고, 이런 식으로 이어 간다.

m! 안의 5의 개수 = ⌊ m/5⌋ + ⌊ m/25⌋ + …

3STEP 3

조건을 식으로 쓴다

m!의 0 개수를 Z(m)이라 하면, 각 n의 확인은 Z(2n)이 Z(n)의 세 배인지 보는 것뿐이다.

Z(2n)=3 Z(n)

4STEP 4

n을 5부터 9까지 시험

n=5,6,7은 (2n)!의 0이 2개뿐이라 실패하고, n=8,9는 Z(16)=Z(18)=3이라 8과 9가 처음 두 당첨자다.

Z(8)=1, Z(16)=3; Z(9)=1, Z(18)=3

5STEP 5

n을 10부터 14까지 시험

n=10,11,12는 0이 4개뿐이라 실패하고, 25가 여분의 5를 더해 Z(26)=Z(28)=6이 되어 13,14가 다음 당첨자다.

Z(13)=2, Z(26)=6; Z(14)=2, Z(28)=6

6STEP 6

더하고 각 자리 숫자를 합한다

네 당첨자 8,9,13,14의 합은 s=44이고, 각 자리 숫자는 4+4=8이다.

s=8+9+13+14=44; 4+4=8

정답

당첨자들은 {8,9}와 {13,14} 두 쌍으로 나오는데, 각각 (2n)!의 5 개수가 뛰는 지점(16,18과 26,28) 바로 뒤에 자리 잡아 Z(2n)=3Z(n)을 갑자기 만족하는 이유와 맞아떨어진다. 건너뛴 10,11,12는 두 배 해도 0이 4개에 그치는데 6개가 필요하므로 옳게 실패한다. 8+9+13+14=44와 각 자리 합 8은 모두 작고 확인하기 쉬운 계산이며, 8은 보기 중 하나다.

💡핵심 정리

끝자리 0은 오직 5의 인수에서만 생기므로 5를 센 다음, n을 순서대로 넣어 보고 (2n)!의 0이 세 배인 것만 남기면 된다.

오직 5만 센다
5를 세는 방법
조건을 식으로 쓴다
n을 5부터 9까지 시험
n을 10부터 14까지 시험
더하고 각 자리 숫자를 합한다