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)₉이 되어 숫자 6으로 끝난다. 이제 2013을 b진법으로 나타내자. 여기서 b는 양의 정수이다. 이 b진법 표현이 숫자 3으로 끝나게 하는 b는 몇 개인가?

답을 골라 클릭하세요.

(A)
6
(B)
9
(C)
13
(D)
16
(E)
18

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

풀이 과정
전략 대수로 바꾸기

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

1STEP 1

마지막 자리는 나머지

b진법의 일의 자리는 b로 나눈 나머지다. 즉 3으로 끝난다는 것은 나머지가 3이라는 뜻이다.

2013 이 3으로 끝남 (b진법) ⇔ 2013 ≡ 3 (mod b)
2STEP 2

나눗셈 조건으로 바꾸기

남는 3을 떼어내면 2013 - 3 = 2010이 b의 배수여야 하니, b는 2010의 약수다.

2013 ≡ 3 (mod b) ⇔ b ∣ (2013 - 3) = 2010
3STEP 3

2010의 약수 개수 세기

2010 = 2 · 3 · 5 · 67, 서로 다른 소수 넷이 각각 넣거나 빼는 스위치이니 약수는 16개다.

2010 = 2 · 3 · 5 · 67 → (1+1)⁴ = 16 개의 약수
4STEP 4

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

자리 숫자는 밑보다 작아야 하니 3이 나오려면 b ＞ 3, 약수 1, 2, 3은 버린다.

b ＞ 3 → b ∈ {1, 2, 3} 제외
5STEP 5

최종 개수

약수 16개에서 너무 작은 밑 3개를 빼면 13개의 밑이 남는다 — 답은 (C).

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

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

  • 마지막 자리는 나머지
  • 나눗셈 조건으로 바꾸기
  • 2010의 약수 개수 세기
  • 숫자 3을 못 담는 작은 밑 지우기
  • 최종 개수

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.