AMC 10 · 2013 · #19

학년 6 number-theory

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

base-conversiondivisor-countprime-factorization convert-to-algebrasystematic-enumeration ↑ 선수 지식: base-conversion

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

문제

$10$ 진법에서 수 $2013$ 은 숫자 $3$ 으로 끝난다. 반면에 $9$ 진법에서 같은 수는 $(2676)_{9}$ 로 표현되며 숫자 $6$ 으로 끝난다. $2013$ 의 $b$ 진법 표현이 숫자 $3$ 으로 끝나게 하는 양의 정수 $b$ 는 몇 개인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $2013$을 $b$진법으로 나타내면 어떤 숫자열이 된다. 이 $b$진법 표현의 마지막 자리 숫자가 $3$이 되는 양의 정수 $b$가 몇 개인지 센다.

주어진 것: 다루는 수는 $2013$ (10진법에서의 값)이다.; 10진법에서는 $3$으로 끝나고, 9진법에서는 $(2676)_9$로 써서 $6$으로 끝난다.; $2013$을 $b$진법으로 썼을 때의 마지막(일의) 자리 숫자를 본다.; 선택지: (A) $6$, (B) $9$, (C) $13$, (D) $16$, (E) $18$

구하는 것: $2013$의 $b$진법 마지막 자리 숫자가 $3$이 되게 하는 양의 정수 $b$의 개수.

이해

문제 재정리: $2013$을 $b$진법으로 나타내면 어떤 숫자열이 된다. 이 $b$진법 표현의 마지막 자리 숫자가 $3$이 되는 양의 정수 $b$가 몇 개인지 센다.

계획

주요 도구: #13 대수로 바꾸기

보조 도구: #2 빠짐없이 나열하기, #3 가능성 지우기

"$3$으로 끝난다"는 말에는 깔끔한 산술 사실이 숨어 있다. $b$진법에서 수의 마지막 자리 숫자는 그 수를 $b$로 나눈 나머지와 같다. 도구 #13 (대수로 바꾸기)로 "$2013$이 $b$진법에서 $3$으로 끝난다"를 합동식 $2013 \equiv 3 \pmod{b}$로 바꾸면, 이는 "$b$가 $2010$을 나눈다"로 정리된다. 진법 표현 문제가 약수를 세는 문제로 바뀌는 것이다. 이어서 도구 #2 (빠짐없이 나열하기)로 $2010$의 소인수분해에서 약수의 개수를 세고, 도구 #3 (가능성 지우기)로 숫자 $3$을 쓰기에 너무 작은 밑을 걸러낸다.

실행 — 정답: C

#13 대수로 바꾸기 4.NBT.B.6 단계 1

마지막 자리는 나머지

수를 $b$진법으로 쓸 때, 마지막(일의) 자리 숫자는 그 수를 $b$로 나눈 나머지이다.
예를 들어 $2013 = 9 \cdot 223 + 6$이고, 실제로 $(2013)_{10} = (2676)_9$는 $6$으로 끝난다.
따라서 "$2013$이 $b$진법에서 $3$으로 끝난다"는 것은 $2013$을 $b$로 나눈 나머지가 $3$이라는 뜻이다.

$$2013 \text{이 } 3\text{으로 끝남 (}b\text{진법)} \iff 2013 \equiv 3 \pmod{b}$$

💡 일의 자리 숫자는 $b$짜리 묶음을 모두 빼낸 뒤 남는 것, 즉 나머지이다.

#13 대수로 바꾸기 4.OA.B.4 단계 2

나눗셈 조건으로 바꾸기

나머지가 $3$이라는 것은 $2013$이 $b$의 배수보다 정확히 $3$만큼 크다는 뜻이다.
그 $3$을 빼면 $2013 - 3 = 2010$이 $b$의 온전한 배수여야 한다.
그래서 조건은 "$b$가 $2010$의 약수이다"가 된다.
$2013$을 $3$으로 끝나게 하는 모든 밑은 $2010$의 약수이고, $2010$의 모든 약수는 나머지를 $3$으로 만든다.

$$2013 \equiv 3 \pmod{b} \iff b \mid (2013 - 3) = 2010$$

💡 남는 $3$을 떼어내면 나머지 $2010$이 $b$로 딱 나누어떨어져야 한다.

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

2010의 약수 개수 세기

$2010$을 소인수분해하면 $2010 = 2 \cdot 3 \cdot 5 \cdot 67$이다.
각 소수가 한 번씩만 나오므로, 약수는 네 소수 각각을 넣을지 말지 독립적으로 정해서 만든다 — 소수마다 $2$가지 선택.
따라서 $2 \cdot 2 \cdot 2 \cdot 2 = 16$개의 약수가 있다: $1, 2, 3, 5, 6, 10, 15, 30, 67, 134, 201, 335, 402, 670, 1005, 2010$.

$$2010 = 2 \cdot 3 \cdot 5 \cdot 67 \;\Rightarrow\; (1+1)^4 = 16 \text{개의 약수}$$

💡 중복된 소수가 없으니 각 소수는 켜고 끄는 스위치라서 약수 개수가 네 번 두 배가 된다.

#3 가능성 지우기 6.EE.B.5 단계 4

숫자 3을 못 담는 작은 밑 지우기

각 자리 숫자는 밑보다 작아야 하므로, 숫자 $3$은 $b > 3$일 때만 존재할 수 있다.
$16$개의 약수 중에서 이 조건은 $b = 1$, $b = 2$, $b = 3$을 제외한다.
이 밑들에서는 "숫자 $3$"이 불가능하다 (밑 $1$은 제대로 된 위치 진법이 아니고, 밑 $2$와 $3$은 최대 $2$까지의 숫자만 쓴다).
나머지 약수인 $5$부터 $2010$까지는 모두 유효하다.

$$b > 3 \;\Rightarrow\; b \in \{1, 2, 3\} \text{ 제외}$$

💡 숫자가 $0$부터 $b-1 < 3$까지만 있는 밑에서는 숫자 $3$을 쓸 수 없다.

#3 가능성 지우기 4.OA.B.4 단계 5

최종 개수

$2010$의 약수 $16$개에서 시작해 금지된 작은 밑 $3$개($1, 2, 3$)를 뺀다.
그러면 $16 - 3 = 13$개의 유효한 밑이 남는다: $5, 6, 10, 15, 30, 67, 134, 201, 335, 402, 670, 1005, 2010$.
따라서 $2013$은 정확히 $13$개의 밑에서 숫자 $3$으로 끝나며, 답은 $\textbf{(C)}$이다.

$$16 - 3 = 13 \;\Rightarrow\; \textbf{(C)}\ 13$$

💡 전체 약수에서 쓸 수 없는 작은 밑 세 개를 뺀다.

[1] #13 4.NBT.B.6 수를 $b$진법으로 쓸 때, 마지막(일의) 자리 숫자는 그 수를 $b$로 나눈 나머지이다. 예를 들어 $2013 = 9 \cdot 223 + 6

[2] #13 4.OA.B.4 나머지가 $3$이라는 것은 $2013$이 $b$의 배수보다 정확히 $3$만큼 크다는 뜻이다. 그 $3$을 빼면 $2013 - 3 = 2010$이

[3] #2 4.OA.B.4 $2010$을 소인수분해하면 $2010 = 2 \cdot 3 \cdot 5 \cdot 67$이다. 각 소수가 한 번씩만 나오므로, 약수는 네 소

[4] #3 6.EE.B.5 각 자리 숫자는 밑보다 작아야 하므로, 숫자 $3$은 $b > 3$일 때만 존재할 수 있다. $16$개의 약수 중에서 이 조건은 $b = 1$,

[5] #3 4.OA.B.4 $2010$의 약수 $16$개에서 시작해 금지된 작은 밑 $3$개($1, 2, 3$)를 뺀다. 그러면 $16 - 3 = 13$개의 유효한 밑이

검토

합리성 확인: 유효한 목록의 양 끝을 확인해 본다. 밑 $5$: $2013 = 5 \cdot 402 + 3$, 나머지 $3$ — $3$으로 끝난다. 밑 $2010$: $2013 = 2010 \cdot 1 + 3$이므로 $(2013)_{10} = (1\,3)_{2010}$ — $3$으로 끝난다. 약수가 아닌 $b = 4$는 $2013 = 4 \cdot 503 + 1$, 나머지 $1$이라 제대로 제외된다. 제외한 세 약수 $1, 2, 3$은 바로 숫자 $3$이 불가능한 밑들이므로 $16$에서 $3$을 빼는 것이 옳다. 개수 $13$은 (C)와 일치하고, 원래 약수 개수 $16$과 더 작은 오답들 사이에 자연스럽게 놓인다.

대안 접근: 도구 #2 (빠짐없이 나열하기)만으로도 풀 수 있다. $b \mid 2010$을 세운 뒤 $2010$의 약수 쌍을 직접 나열한다 — $(1,2010), (2,1005), (3,670), (5,402), (6,335), (10,201), (15,134), (30,67)$ — 이것으로 약수가 $16$개임을 보이고, $1, 2, 3$을 손으로 지워 $13$에 이른다. 지수에 $1$을 더해 곱하는 약수 개수 공식을 쓰지 않고도 같은 답이 나온다.

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

4.NBT.B.6 네 자리 이하 피제수의 몫과 나머지 구하기 ($2013$의 $b$진법 마지막 자리 숫자가 $2013$을 $b$로 나눈 나머지임을 알아내어, "$3$으로 끝난다"를 나머지 $3$으로 해석하는 데 사용.)
4.OA.B.4 약수 쌍을 모두 찾고 배수를 알아보며 소수·합성수 판별하기 (조건을 $b \mid 2010$으로 바꾸고, $2010 = 2 \cdot 3 \cdot 5 \cdot 67$로 소인수분해하여 약수 $16$개를 세고, 마지막 약수 개수를 정리하는 데 사용.)
6.EE.B.5 방정식이나 부등식을 참으로 만드는 값을 찾는 과정으로 이해하기 (부등식 $b > 3$ (자리 숫자는 밑보다 작아야 함)을 적용해 어떤 약수가 유효한 밑이고 어떤 것을 버려야 하는지 판단하는 데 사용.)

⭐ $b$진법에서 수의 마지막 자리 숫자는 $b$로 나눈 나머지일 뿐이다. "$3$으로 끝난다"는 것은 $b$가 $2013 - 3 = 2010$을 나눈다는 뜻이고, $2010$은 약수가 $16$개이므로 숫자 $3$을 담기엔 너무 작은 밑 $1, 2, 3$을 빼면 $\textbf{(C)}\ 13$이 남는다.