AMC 10 · 2014 · #12

학년 6 number-theory

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

prime-factorizationfactorsdivisor-count complementary-counting ↑ 선수 지식: prime-factorization

📏 중간 풀이 💡 2 개 인사이트

문제

$2,014,000,000$ 의 가장 큰 약수는 그 자신이다. 이 수의 다섯 번째로 큰 약수는 무엇인가?

답을 골라 클릭하세요.

(A)

125, 875, 000

(B)

201, 400, 000

(C)

251, 750, 000

(D)

402, 800, 000

(E)

503, 500, 000

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 수 $2{,}014{,}000{,}000$ 에는 많은 약수가 있고, 가장 큰 약수는 자기 자신이다. 이 수의 다섯 번째로 큰 약수를 구하여라.

주어진 것: $N = 2{,}014{,}000{,}000$; $N$ 의 가장 큰 약수는 $N$ 자기 자신이다; 선택지: (A) $125{,}875{,}000$, (B) $201{,}400{,}000$, (C) $251{,}750{,}000$, (D) $402{,}800{,}000$, (E) $503{,}500{,}000$

구하는 것: $N$ 의 다섯 번째로 큰 약수

이해

문제 재정리: 수 $2{,}014{,}000{,}000$ 에는 많은 약수가 있고, 가장 큰 약수는 자기 자신이다. 이 수의 다섯 번째로 큰 약수를 구하여라.

계획

주요 도구: #16 관점 바꾸기

보조 도구: #7 작은 문제로 쪼개기, #2 빠짐없이 나열하기

$N$ 의 거대한 약수들을 큰 것부터 하나씩 나열하는 것은 번거롭다. 도구 #16(관점 바꾸기)은 문제를 뒤집는다. $N$ 의 모든 약수 $d$ 는 짝이 되는 $N/d$ 와 한 쌍을 이루고, 두 수의 곱은 $N$ 이다. $d$ 가 가장 작은 약수 $1, 2, 4, 5, \dots$ 를 지나갈 때, 짝 $N/d$ 는 가장 큰 약수 $N, N/2, N/4, \dots$ 를 같은 순서로 지나간다. 따라서 다섯 번째로 큰 약수는 단지 $N$ 을 다섯 번째로 작은 약수로 나눈 값이며, 훨씬 다루기 쉬운 목표가 된다. 도구 #7(작은 문제로 쪼개기)로 밑작업을 한다. $N$ 을 소인수분해하여 어떤 작은 수들이 $N$ 을 나누는지 정확히 파악한다. 그다음 도구 #2(빠짐없이 나열하기)로 가장 작은 약수들을 차례대로 짚어 다섯 번째 약수를 찾고, 나눗셈 한 번으로 마무리한다.

실행 — 정답: C

#16 관점 바꾸기 4.OA.B.4 단계 1

가장 큰 약수를 가장 작은 약수로 뒤집기

약수는 짝을 이룬다.
$d$ 가 $N$ 을 나누면 $N/d$ 도 $N$ 을 나누고, $d \cdot (N/d) = N$ 이다.
가장 작은 약수 $1$ 은 가장 큰 약수 $N$ 과 짝이 되고, 두 번째로 작은 약수는 두 번째로 큰 약수와 짝이 되는 식이다.
그러므로 약수를 큰 쪽부터 세는 것은 작은 쪽부터 세는 것과 같다.
다섯 번째로 큰 약수는 $N$ 을 다섯 번째로 작은 약수로 나눈 값이다.

$$d \cdot \dfrac{N}{d} = N \;\Longrightarrow\; (\text{다섯 번째로 큰 약수}) = \dfrac{N}{(\text{다섯 번째로 작은 약수})}$$

💡 약수는 곱이 $N$ 이 되는 짝끼리 늘어서므로, 위에서부터 세는 것이 아래에서부터 세는 것과 거울처럼 대응한다.

#7 작은 문제로 쪼개기 5.NBT.A.2 단계 2

10의 거듭제곱 떼어내기

$N$ 을 작은 수와 $10$ 의 거듭제곱의 곱으로 쓴다.
$2{,}014{,}000{,}000 = 2014 \times 1{,}000{,}000$ 이고, 끝의 $0$ 여섯 개는 $1{,}000{,}000 = 10^6 = (2 \cdot 5)^6 = 2^6 \cdot 5^6$ 을 뜻한다.
$0$ 하나마다 $2$ 하나와 $5$ 하나가 붙는다.

$$N = 2014 \times 10^6 = 2014 \times 2^6 \cdot 5^6$$

💡 끝의 $0$ 하나는 곧 $10 = 2 \times 5$ 하나이므로, $0$ 여섯 개가 $2^6 \cdot 5^6$ 을 공짜로 준다.

#7 작은 문제로 쪼개기 6.NS.B.4 단계 3

N 을 소인수분해하기

$2014$ 를 마저 분해한다.
짝수이므로 $2014 = 2 \cdot 1007$ 이고, $1007 = 19 \cdot 53$ 이다($19$ 와 $53$ 은 모두 소수).
$10$ 의 거듭제곱과 합치면 $N$ 의 완전한 소인수분해가 나온다.
$N$ 의 소인수는 오직 $2, 5, 19, 53$ 뿐이며, 특히 $3$ 과 $7$ 은 $N$ 을 나누지 못한다.

$$N = 2 \cdot 19 \cdot 53 \cdot 2^6 \cdot 5^6 = 2^7 \cdot 5^6 \cdot 19 \cdot 53$$

💡 소수 벽돌을 알고 나면 어떤 작은 수들이 $N$ 을 나눌 수 있는지 정확히 알 수 있다.

#2 빠짐없이 나열하기 4.OA.B.4 단계 4

가장 작은 다섯 약수 나열하기

정수를 차례대로 짚으며 $N$ 을 나누는 것만 남긴다.
$1$ 은 된다.
$2$ 는 된다($N$ 은 짝수).
$3$ 은 안 된다(각 자리 합 $2{+}0{+}1{+}4 = 7$ 이 $3$ 의 배수가 아님).
$4 = 2^2$ 는 된다($N$ 에 $2^7$ 이 있음).
$5$ 는 된다($N$ 이 $0$ 으로 끝남).
$6 = 2\cdot 3$ 은 안 되고($3$ 이 없음), $7$ 도 안 된다(소수 벽돌이 아님).
$8 = 2^3$ 은 된다.
따라서 가장 작은 약수는 차례로 $1, 2, 4, 5, 8$ 이고, 다섯 번째로 작은 약수는 $8$ 이다.

$$1,\; 2,\; 4,\; 5,\; 8 \;\Rightarrow\; \text{다섯 번째로 작은 약수} = 8$$

💡 $N$ 에 없는 소수($3$ 이나 $7$)를 가진 수는 건너뛰면, 약수 사다리가 저절로 세워진다.

#7 작은 문제로 쪼개기 6.NS.B.2 단계 5

N 을 8 로 나누기

1단계의 뒤집기에 따라 다섯 번째로 큰 약수는 $N \div 8$ 이다.
$8 = 2^3$ 으로 나누는 것은 $2$ 를 세 개 떼어내는 것일 뿐이다.
$N = 2^7 \cdot 5^6 \cdot 19 \cdot 53$ 이 $2^4 \cdot 5^6 \cdot 19 \cdot 53$ 이 된다.
계산하면 $2^4 \cdot 5^6 = 16 \cdot 15625 = 250000$ 이고 $19 \cdot 53 = 1007$ 이므로, 값은 $250000 \cdot 1007 = 251{,}750{,}000$ 이다.
이는 선택지 (C)와 일치한다.

$$\dfrac{N}{8} = \dfrac{2^7 \cdot 5^6 \cdot 19 \cdot 53}{2^3} = 2^4 \cdot 5^6 \cdot 19 \cdot 53 = 251{,}750{,}000 \;\Rightarrow\; \textbf{(C)}$$

💡 $8$ 로 나누는 것은 소인수분해에서 $2$ 세 개를 벗겨내는 것과 같다.

[1] #16 4.OA.B.4 약수는 짝을 이룬다. $d$ 가 $N$ 을 나누면 $N/d$ 도 $N$ 을 나누고, $d \cdot (N/d) = N$ 이다. 가장 작은 약수

[2] #7 5.NBT.A.2 $N$ 을 작은 수와 $10$ 의 거듭제곱의 곱으로 쓴다. $2{,}014{,}000{,}000 = 2014 \times 1{,}000{,}00

[3] #7 6.NS.B.4 $2014$ 를 마저 분해한다. 짝수이므로 $2014 = 2 \cdot 1007$ 이고, $1007 = 19 \cdot 53$ 이다($19$ 와

[4] #2 4.OA.B.4 정수를 차례대로 짚으며 $N$ 을 나누는 것만 남긴다. $1$ 은 된다. $2$ 는 된다($N$ 은 짝수). $3$ 은 안 된다(각 자리 합 $

[5] #7 6.NS.B.2 1단계의 뒤집기에 따라 다섯 번째로 큰 약수는 $N \div 8$ 이다. $8 = 2^3$ 으로 나누는 것은 $2$ 를 세 개 떼어내는 것일 뿐

검토

합리성 확인: 가장 큰 약수부터 나열하면 답이 확인된다. $N$(가장 큼), 그다음 $N/2 = 1{,}007{,}000{,}000$, $N/4 = 503{,}500{,}000$(선택지 E), $N/5 = 402{,}800{,}000$(선택지 D), 그리고 $N/8 = 251{,}750{,}000$(선택지 C)이다. 선택지 (D)와 (E)는 각각 네 번째, 세 번째로 큰 약수이므로 급하게 푼 사람은 그쪽으로 빠질 수 있지만, 다섯 번째로 큰 약수는 (C)이다. 다시 곱해 보면 $251{,}750{,}000 \times 8 = 2{,}014{,}000{,}000 = N$ 이므로 실제로 약수가 맞다.

대안 접근: $N$ 을 가장 작은 약수들로 하나씩 나누어 큰 약수를 직접 나열한다. $N/1, N/2, N/4, N/5, N/8$. 네 번째는 약수 $5$ 를 쓰고($3$ 은 건너뜀), 다섯 번째는 약수 $8$ 을 써서($6$ 과 $7$ 은 건너뜀) $N/8 = 251{,}750{,}000$ 에 도달한다. 완전한 소인수분해를 쓰지 않고도 같은 답 (C)를 얻는다.

사용된 CCSS 표준 (최저 학년 6)

4.OA.B.4 약수 쌍을 모두 찾고 배수를 인식하기; 소수·합성수 판별하기 (약수 쌍 $d$ 와 $N/d$ 를 이용해 '다섯 번째로 큰 약수'를 'N 을 다섯 번째로 작은 약수로 나눈 값'으로 바꾸고, 나누어떨어짐을 적용해 가장 작은 약수 목록을 만드는 데 사용.)
5.NBT.A.2 0의 개수와 소수점 위치의 규칙 설명하기 ($N$ 끝의 $0$ 여섯 개를 $10^6 = 2^6 \cdot 5^6$ 으로 읽어 $N = 2014 \times 10^6$ 으로 분리하는 데 사용.)
6.NS.B.4 두 수의 최대공약수와 최소공배수 구하기 ($2014 = 2 \cdot 19 \cdot 53$ 을 통해 $N = 2^7 \cdot 5^6 \cdot 19 \cdot 53$ 으로 소인수분해하여 소수 벽돌을 찾는 데 사용.)
6.NS.B.2 표준 알고리즘으로 여러 자리 수를 능숙하게 나누기 (다섯 번째로 큰 약수를 얻기 위해 $N \div 8 = 251{,}750{,}000$ 을 계산하는 데 사용.)

⭐ 약수는 항상 곱이 전체가 되는 짝끼리 오기 때문에, 다섯 번째로 큰 약수는 그 수를 다섯 번째로 작은 약수로 나눈 값일 뿐이다.