AMC 10 · 2013 · #25

학년 6 number-theory
유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint
base-conversionmodular-arithmeticplace-value identify-subproblemscasework ↑ 선수 지식: base-conversionmodular-arithmetic
📏 중간 풀이 💡 3 개 인사이트
문제
세 자리 수 N(100부터 999까지)을 5진법과 6진법으로 각각 나타낸다. 이 두 숫자를 보통의 10진수처럼 읽어서 더하면 S가 된다. S의 마지막 두 자리가 2N의 마지막 두 자리와 같아지는 N이 몇 개인지 세어라.

답을 골라 클릭하세요.

(A)
5
(B)
10
(C)
15
(D)
20
(E)
25

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

풀이 과정
전략 변수 도입하기

'마지막 두 자리'라는 말은 mod 100으로 다루라는 신호이고, mod 100은 각 숫자의 마지막 두 자리만 남긴다. 그래서 첫 수는 그 자리들을 변수로 이름 붙이는 것이다. 5진법은 a와 b, 6진법은 c와 d. 그러면 무서운 진법 변환 문제가 하나의 합동식으로 바뀐다. 이어서 그 합동식을 더 쉬운 두 개의 작은 문제, 즉 일의 자리(mod 10)와 십의 자리로 쪼개어 각각 풀고, 마지막에 살아남은 경우의 수를 센다.

1STEP 1

'마지막 두 자리'를 mod 100으로 바꾸기

두 수의 마지막 두 자리가 같다는 것은 mod 100으로 합동이라는 뜻이고, mod 100은 각 표기의 마지막 두 자리만 남긴다.

S ≡ 2N (mod 100)
2STEP 2

각 진법의 마지막 두 자리에 이름 붙이기

5진법 자리는 a = N mod 5, b = N/5의 몫 mod 5, 6진법은 c = N mod 6, d = N/6의 몫 mod 6이다.

(10b+a)+(10d+c)≡ 2N (mod 100)
3STEP 3

일의 자리가 두 진법 일의 자리를 같게 만든다

a + c는 최대 9라 일의 자리는 a + c ≡ 2a (mod 10)이 되어 c = a, 즉 N ≡ a (mod 30)이고 a는 0~4다.

a+c≡ 2a (mod 10) → c=a, N≡ a (mod 30)
4STEP 4

십의 자리가 k에 대한 조건이 된다

N = 30k + a로 쓰면 십의 자리는 b + d ≡ 6k (mod 10)으로 줄고, b = k mod 5, d = 5k mod 6이다.

10(b+d)≡ 60k (mod 100) → b+d≡ 6k (mod 10), b=k mod 5, d=5k mod 6
5STEP 5

좋은 k를 세고 곱하기

이는 k ≡ 0, 1, 12, 13, 24 (mod 30)에서 성립하고 k는 4~33의 30개이므로 5 × 5 = 25, 답은 (E)다.

5 개의 유효한 k × 5 개의 a 값 = 25
정답
25
25개의 해는 연속한 정수 다섯 개짜리 다섯 블록으로 깔끔하게 나뉜다: 360-364, 390-394, 720-724, 900-904, 930-934. 각 블록은 30의 배수에서 시작하고(k = 12, 13, 24, 30, 31) 일의 자리 a = 0..4를 훑으며, 이는 5 곱하기 5 구조와 맞는다. N = 360을 확인하면 5진법 2420의 마지막 두 자리는 20, 6진법 1400은 00, 합은 20으로 끝난다. 2N = 720도 20으로 끝나므로 일치한다. 개수 25는 가장 큰 선택지이며, 모든 유효한 블록이 세 자리 범위 안에 온전히 들어가도록 설계된 문제와 잘 맞는다.
💡핵심 정리

'마지막 두 자리'는 mod 100으로 다루라는 뜻이다. 일의 자리를 먼저 맞추고 그다음 십의 자리를 맞추면, 무서운 진법 변환 문제가 간단한 나머지 세기로 바뀐다.

  • '마지막 두 자리'를 mod 100으로 바꾸기
  • 각 진법의 마지막 두 자리에 이름 붙이기
  • 일의 자리가 두 진법 일의 자리를 같게 만든다
  • 십의 자리가 k에 대한 조건이 된다
  • 좋은 k를 세고 곱하기

비슷한 유형 더 풀어보기

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