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$ 을 고르고, 그 수의 $5$ 진법 표현과 $6$ 진법 표현을 모두 칠판에 적는다. 나중에 르로이가 베르나르도가 적은 두 수를 본다. 르로이는 이 두 수를 $10$ 진법 정수로 여기고 더해서 정수 $S$ 를 얻는다. 예를 들어 $N = 749$ 이면, 베르나르도는 $10,\!444$ 와 $3,\!245$ 를 적고, 르로이는 합 $S = 13,\!689$ 를 얻는다. $S$ 의 오른쪽 끝 두 자리가 순서대로 $2N$ 의 오른쪽 끝 두 자리와 같은 $N$ 은 몇 가지인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 세 자리 수 N(100부터 999까지)을 5진법과 6진법으로 각각 나타낸다. 이 두 숫자를 보통의 10진수처럼 읽어서 더하면 S가 된다. S의 마지막 두 자리가 2N의 마지막 두 자리와 같아지는 N이 몇 개인지 세어라.

주어진 것: N은 세 자리 정수이므로 100 <= N <= 999이다.; N5는 N의 5진법 표기를 10진수로 읽은 값이고, N6은 6진법 표기를 10진수로 읽은 값이다.; S = N5 + N6이다.; S의 마지막 두 자리와 2N의 마지막 두 자리를 비교한다.

구하는 것: 가능한 900개의 N 중에서 S의 마지막 두 자리가 2N의 마지막 두 자리와 일치하는 것이 몇 개인가.

이해

계획

주요 도구: #4 변수 도입하기

보조 도구: #8 단위 살펴보기, #7 작은 문제로 쪼개기, #3 가능성 지우기

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

실행 — 정답: E

#8 단위 살펴보기 5.NBT.A.1 단계 1

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

두 수가 마지막 두 자리를 공유하는 것은 정확히 두 수가 mod 100으로 같을 때이므로, 목표는 S가 2N과 modulo 100으로 합동이 되는 것이다.
5진법 숫자를 10진수로 읽는 것은 자릿수 간격만 바꿀 뿐이고, 그 결과에 mod 100을 취하면 마지막 두 자리만 남는다.
따라서 N의 마지막 두 5진 자리와 마지막 두 6진 자리만이 문제가 된다.

$$S \equiv 2N \pmod{100}$$

💡 mod 100은 십의 자리와 일의 자리를 뺀 모든 자리를 지우므로, 각 숫자의 마지막 두 자리만 살아남는다.

#4 변수 도입하기 4.NBT.B.6 단계 2

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

N을 나눗셈으로 쪼갠다.
5진법에서 일의 자리는 a = N mod 5, 5의 자리는 b = floor(N/5) mod 5이므로 N5는 'b a' 블록으로 끝나고 그 값은 mod 100으로 10b + a다.
6진법에서 일의 자리는 c = N mod 6, 6의 자리는 d = floor(N/6) mod 6이므로 값은 10d + c다.
조건은 (10b + a) + (10d + c)가 2N과 modulo 100으로 합동이 된다.

$$(10b+a)+(10d+c)\equiv 2N \pmod{100}$$

💡 5로, 6으로 나누면 일의 자리와 십의 자리에 놓일 정확한 숫자가 그대로 나온다.

#7 작은 문제로 쪼개기 6.EE.A.2 단계 3

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

먼저 mod 10을 본다.
a는 최대 4, c는 최대 5이므로 합 a + c는 최대 9여서 S의 일의 자리는 그냥 a + c다.
또 2N mod 10은 2 곱하기 (N mod 5) = 2a와 같다.
일의 자리를 맞추면 a + c가 2a와 modulo 10으로 합동이므로 c가 a와 modulo 10으로 합동이다.
a와 c가 모두 0과 5 사이이므로 이는 c = a를 강제한다.
그러면 N은 mod 5와 mod 6에서 같은 나머지 a(a는 최대 4)를 가지므로 N은 a와 modulo 30으로 합동이다.
따라서 일의 자리 나머지는 a = 0, 1, 2, 3, 4의 5가지가 가능하다.

$$a+c\equiv 2a \pmod{10} \;\Rightarrow\; c=a,\quad N\equiv a \pmod{30}$$

💡 일의 자리는 두 진법 나머지가 말 그대로 같은 수일 때만 균형이 맞는다.

#4 변수 도입하기 5.NBT.A.2 단계 4

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

N = 30k + a로 쓰고 a는 {0, 1, 2, 3, 4}에 있다.
그러면 2N = 60k + 2a이고, c = a이므로 조건 (10b + a) + (10d + a)가 60k + 2a와 합동인 것은 10(b + d)가 60k와 modulo 100으로 합동, 즉 b + d가 6k와 modulo 10으로 합동으로 줄어든다.
N을 나누면 b = floor(N/5) mod 5 = 6k mod 5 = k mod 5, d = floor(N/6) mod 6 = 5k mod 6이다.
따라서 문제는 이제 '어떤 k에서 (k mod 5) + (5k mod 6)이 6k와 modulo 10으로 합동인가?'가 된다.

$$10(b+d)\equiv 60k \pmod{100} \;\Rightarrow\; b+d\equiv 6k \pmod{10},\quad b=k\bmod 5,\; d=5k\bmod 6$$

💡 이미 맞아떨어진 일의 자리를 걷어내면 오직 k에 대한 깔끔한 합동식 하나만 남는다.

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

좋은 k를 세고 곱하기

(k mod 5) + (5k mod 6)이 6k와 modulo 10으로 합동인지의 조건은 k mod 30에만 의존한다.
한 주기를 전부 확인하면 이는 k가 0, 1, 12, 13, 24와 modulo 30으로 합동일 때, 즉 다섯 개의 나머지에서만 성립한다.
N = 30k + a가 a가 최대 4일 때 세 자리가 되려면 k는 4부터 33까지 움직이며, 이는 연속한 30개의 값이므로 각 나머지 mod 30이 정확히 한 번씩 나타난다.
그래서 유효한 k가 5개(즉 12, 13, 24, 30, 31) 나오고, 각각은 a의 5가지 선택과 짝을 이룬다.
따라서 개수는 5 곱하기 5 = 25이고, 이는 (E)다.

5 \text{ 개의 유효한 } k \times 5 \text{ 개의 } a \text{ 값} = 25

💡 깔끔한 합동식 하나가 다섯 개의 k 블록을 주고, 각 블록이 다섯 개의 일의 자리를 담으니, 전체는 5 곱하기 5의 격자가 된다.

[1] #8 5.NBT.A.1 두 수가 마지막 두 자리를 공유하는 것은 정확히 두 수가 mod 100으로 같을 때이므로, 목표는 S가 2N과 modulo 100으로 합동이 되

[2] #4 4.NBT.B.6 N을 나눗셈으로 쪼갠다. 5진법에서 일의 자리는 a = N mod 5, 5의 자리는 b = floor(N/5) mod 5이므로 N5는 'b a'

[3] #7 6.EE.A.2 먼저 mod 10을 본다. a는 최대 4, c는 최대 5이므로 합 a + c는 최대 9여서 S의 일의 자리는 그냥 a + c다. 또 2N mod

[4] #4 5.NBT.A.2 N = 30k + a로 쓰고 a는 {0, 1, 2, 3, 4}에 있다. 그러면 2N = 60k + 2a이고, c = a이므로 조건 (10b +

[5] #3 4.NBT.B.5 (k mod 5) + (5k mod 6)이 6k와 modulo 10으로 합동인지의 조건은 k mod 30에만 의존한다. 한 주기를 전부 확인하면

검토

합리성 확인: 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는 가장 큰 선택지이며, 모든 유효한 블록이 세 자리 범위 안에 온전히 들어가도록 설계된 문제와 잘 맞는다.

대안 접근: 대수를 건너뛰고 무차별 대입으로 풀 수도 있다. N을 100부터 999까지 하나씩 돌며 5진법과 6진법 표기를 만들고, 10진수로 읽어 더한 뒤, 마지막 두 자리를 2N의 마지막 두 자리와 비교한다. 맞는 것을 세면 곧바로 25가 나온다. 대수는 왜 승자들이 다섯 개짜리 다섯 블록으로 뭉치는지를 설명해 줄 뿐이다.

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

5.NBT.A.1 Recognize that a digit in one place represents ten times as much as to its right (5진법 또는 6진법 숫자의 마지막 두 자리를 10 곱하기 십의 자리 더하기 일의 자리로 읽고, mod 100이 그 두 자리만 남긴다는 것을 파악하기.)
4.NBT.B.6 Find whole-number quotients and remainders with up to four-digit dividends (나눗셈의 나머지로 진법 자리 a = N mod 5, b = floor(N/5) mod 5, c = N mod 6, d = floor(N/6) mod 6을 뽑아내기.)
6.EE.A.2 Write, read, and evaluate expressions in which letters stand for numbers (a, b, c, d, k에 대한 합동식을 세우고 줄여서 c = a와 k에 대한 조건을 이끌어내기.)
5.NBT.A.2 Explain patterns in the number of zeros and placement of the decimal point (10배의 자릿값 이동을 이용해 10(b + d)가 60k와 합동인 것을 b + d가 6k와 modulo 10으로 합동으로 바꾸기.)
4.NBT.B.5 Multiply a whole number of up to four digits by a one-digit whole number (유효한 k 5개와 a 값 5개를 결합해 최종 개수 5 곱하기 5 = 25를 얻기.)

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