AMC 10 · 2024 · #18

학년 8 number-theory

modular-arithmeticdigit-decompositiondivisibility-rulesparity identify-subproblemscaseworkpattern-recognition ↑ 선수 지식: modular-arithmeticplace-valuedivisibility-rules

📏 긴 풀이 💡 4 개 인사이트

문제

There are exactly $K$ positive integers $b$ with $5 \leq b \leq 2024$ such that the base- $b$ integer $2024_b$ is divisible by $16$ (where $16$ is in base ten). What is the sum of the digits of $K$ ?

$\textbf{(A) }16\qquad\textbf{(B) }17\qquad\textbf{(C) }18\qquad\textbf{(D) }20\qquad\textbf{(E) }21$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $5 \le b \le 2024$ 인 정수 $b$ 중에서, $b$진법 네 자리 수 $2024_b$ 가 $16$ 으로 나누어떨어지는 경우는 몇 개인지 그 개수를 $K$ 라 하고, $K$ 의 각 자릿수의 합을 구하세요.

주어진 것: $2024_b$ 는 자릿수 $2, 0, 2, 4$ 를 갖는 $b$진법 수; $b$ 의 범위: $5 \le b \le 2024$ ($4$ 가 자릿수이므로 $b > 4$ 필요); 나눗셈 기준: $16$ (십진수); $K$ 는 조건을 만족하는 $b$ 의 개수이고, 최종 답은 $K$ 의 자릿수의 합; 선택지: (A) $16$, (B) $17$, (C) $18$, (D) $20$, (E) $21$

구하는 것: $K$ = 조건을 만족하는 $b$ 의 개수; $K$ 의 자릿수의 합

이해

계획

주요 도구: #7 작은 문제로 쪼개기

보조 도구: #9 더 쉬운 문제로 줄이기

이 문제는 네 가지 작업이 한 줄로 이어져 있습니다 — (i) $2024_b$ 를 10진법으로 옮기기, (ii) "$16$ 으로 나누어떨어진다"를 $b$ 에 대한 깔끔한 합동식으로 바꾸기, (iii) $[5, 2024]$ 안에서 그 합동식을 통과하는 $b$ 의 개수 세기, (iv) 자릿수의 합 계산. 작업들이 차곡차곡 쌓여 있다는 점이 도구 #7(작은 문제로 쪼개기)을 부르는 신호 — 각 조각을 따로 해결한 뒤 이어 붙이면 됩니다. 단계 (ii) 안에서 도구 #9(더 쉬운 문제로 줄이기)도 함께 씁니다 — $2b^3 + 2b + 4$ 의 모든 항이 짝수이므로 합동식 전체를 $2$ 로 나누면 법(modulus)이 $16$ 에서 $8$ 로 작아집니다. 법 $8$ 에서는 "홀수 $b$ 의 경우 $b^2 \equiv 1 \pmod 8$" 이라는 한 가지 사실이 3차 합동식을 1차로 줄여 줍니다.

실행 — 정답: D

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

쪼개기 1: $2024_b$ 를 10진법으로 바꾸기.
자릿수 $2, 0, 2, 4$ 가 $b$진법에서 의미하는 값은 $2 \cdot b^3 + 0 \cdot b^2 + 2 \cdot b + 4$ 입니다.
나눗셈 조건은 법 $16$ 의 합동식이 됩니다.

$$2024_b = 2b^3 + 2b + 4, \quad 2b^3 + 2b + 4 \equiv 0 \pmod{16}$$

💡 $b$진법의 자릿값은 5학년의 "한 자리가 오른쪽 자리의 $b$ 배" 규칙을 문자 $b$ 로 확장한 것뿐입니다.

#9 더 쉬운 문제로 줄이기 6.NS.B.4 단계 2

쪼개기 2: 법을 작게 만들기.
좌변의 모든 항이 짝수이므로 $2$ 를 묶어낼 수 있습니다.
$2x \equiv 0 \pmod{16}$ 은 $x \equiv 0 \pmod 8$ 과 같은 뜻입니다.
이것이 도구 #9 의 동작 — 같은 문제를 더 작은 법으로 바꾸기.

$$2(b^3 + b + 2) \equiv 0 \pmod{16} \;\Longleftrightarrow\; b^3 + b + 2 \equiv 0 \pmod 8$$

💡 모든 항에서 공통인수를 빼내는 6학년 분배법칙 동작을, 합이 아니라 합동식에 적용한 것.

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

쪼개기 3a: $b$ 가 홀수일 때 법 $8$ 합동식 풀기.
핵심 사실: 임의의 홀수 $b$ 에 대해 $b^2 \equiv 1 \pmod 8$ ($1^2, 3^2, 5^2, 7^2 \equiv 1, 1, 1, 1 \pmod 8$ 확인).
따라서 $b^3 = b \cdot b^2 \equiv b \pmod 8$ 이 되고, 합동식은 $b$ 에 관한 1차식으로 줄어듭니다.

$$b + b + 2 \equiv 0 \pmod 8 \;\Rightarrow\; 2(b+1) \equiv 0 \pmod 8 \;\Rightarrow\; b \equiv 3 \pmod 4$$

💡 "홀수의 제곱은 법 $8$ 에서 항상 $1$" 은 정수론에서 가장 유용한 지수 사실 중 하나로, 3차 합동식을 1차 합동식으로 바꿔 줍니다.

#7 작은 문제로 쪼개기 4.OA.C.5 단계 4

쪼개기 3b: 홀수 $b$ 중 $b \equiv 3 \pmod 4$ 인 것을 나열.
그런 $b$ 는 $3, 7, 11, 15, 19, 23, \dots$ — 법 $8$ 에서 $\equiv 3$ 과 $\equiv 7$ 을 번갈아 갖습니다.
따라서 홀수 해는 정확히 $b \equiv 3 \pmod 8$ 과 $b \equiv 7 \pmod 8$.

$$\{b \;\text{홀수}: b \equiv 3 \pmod 4\} = \{b \equiv 3 \pmod 8\} \cup \{b \equiv 7 \pmod 8\}$$

💡 "$4$ 씩 건너뛰기" 에서 "$8$ 씩 건너뛰기" 로 가면 각 잔여류가 둘로 갈라집니다 — 4학년 "패턴 잇기" 규칙을 잔여류에 적용한 모습.

#7 작은 문제로 쪼개기 8.EE.A.1 단계 5

쪼개기 3c: $b$ 가 짝수일 때 합동식 풀기.
$b = 2k$ 로 두면 $b^3 = 8k^3$ 은 법 $8$ 에서 사라지고, 합동식은 $2k + 2 \equiv 0 \pmod 8$, 즉 $k \equiv 3 \pmod 4$ 로 줄어듭니다.
되돌리면 $b = 2k = 8m + 6$.
따라서 짝수 해는 정확히 $b \equiv 6 \pmod 8$.

$$(2k)^3 + 2k + 2 \equiv 2k + 2 \equiv 0 \pmod 8 \;\Rightarrow\; k \equiv 3 \pmod 4 \;\Rightarrow\; b \equiv 6 \pmod 8$$

💡 $b = 2k$ 로 치환하면 $(2k)^3$ 이 이미 $8$ 의 배수라서 3차항이 통째로 사라집니다 — 깔끔한 세제곱 성질.

#7 작은 문제로 쪼개기 4.OA.C.5 단계 6

세 잔여류 조합: $b$ 가 조건을 만족할 필요충분조건은 $b \equiv 3, 6, \text{또는 } 7 \pmod 8$.
연속한 $8$ 개의 정수 중에서는 정확히 $3$ 개의 잔여류가 통과합니다.

$$\text{유효한 } b \pmod 8 \;\in\; \{3, 6, 7\}, \quad \text{밀도 } = \dfrac{3}{8}$$

💡 잔여류는 $8$ 걸음마다 반복 — 어떤 잔여류가 통과하는지만 알면, 세는 일은 "완전한 블록이 몇 개 들어가고 자투리가 얼마인가" 가 전부.

#7 작은 문제로 쪼개기 4.OA.C.5 단계 7

쪼개기 4: $[5, 2024]$ 안의 유효한 $b$ 개수 세기.
창 $[1, 2024]$ 에는 정확히 $2024 / 8 = 253$ 개의 완전한 블록이 들어가므로 해의 수는 $253 \times 3 = 759$.
이제 $b < 5$ 인 해를 빼야 합니다.
$b = 1, 2, 3, 4$ 를 잔여류 집합 $\{3, 6, 7\}$ 과 비교하면 $b = 3$ 만 조건 통과.
따라서 $K = 759 - 1 = 758$.

$$K = 253 \cdot 3 - 1 = 759 - 1 = 758$$

💡 "창 안에서 세기" 의 정석은 더 큰 창에서 쉽게 세고, 원치 않는 부분만 빼는 것.

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

마지막 조각: $K = 758$ 의 자릿수의 합.

$$7 + 5 + 8 = 20 \;\Rightarrow\; \textbf{(D)}$$

💡 자릿수의 합은 10진법 자릿값을 그대로 쓰는 가장 직접적인 동작 — 그냥 자릿수를 더하고 멈추면 끝.

[1] #7 5.NBT.A.1 쪼개기 1: $2024_b$ 를 10진법으로 바꾸기. 자릿수 $2, 0, 2, 4$ 가 $b$진법에서 의미하는 값은 $2 \cdot b^3 +

[2] #9 6.NS.B.4 쪼개기 2: 법을 작게 만들기. 좌변의 모든 항이 짝수이므로 $2$ 를 묶어낼 수 있습니다. $2x \equiv 0 \pmod{16}$ 은 $x

[3] #7 8.EE.A.1 쪼개기 3a: $b$ 가 홀수일 때 법 $8$ 합동식 풀기. 핵심 사실: 임의의 홀수 $b$ 에 대해 $b^2 \equiv 1 \pmod 8$

[4] #7 4.OA.C.5 쪼개기 3b: 홀수 $b$ 중 $b \equiv 3 \pmod 4$ 인 것을 나열. 그런 $b$ 는 $3, 7, 11, 15, 19, 23, \

[5] #7 8.EE.A.1 쪼개기 3c: $b$ 가 짝수일 때 합동식 풀기. $b = 2k$ 로 두면 $b^3 = 8k^3$ 은 법 $8$ 에서 사라지고, 합동식은 $2k

[6] #7 4.OA.C.5 세 잔여류 조합: $b$ 가 조건을 만족할 필요충분조건은 $b \equiv 3, 6, \text{또는 } 7 \pmod 8$. 연속한 $8$ 개

[7] #7 4.OA.C.5 쪼개기 4: $[5, 2024]$ 안의 유효한 $b$ 개수 세기. 창 $[1, 2024]$ 에는 정확히 $2024 / 8 = 253$ 개의 완전

[8] #7 5.NBT.A.1 마지막 조각: $K = 758$ 의 자릿수의 합.

검토

합리성 확인: 잔여류 목록을 작은 $b$ 로 점검. $b = 3$ (주장된 해): $2b^3 + 2b + 4 = 2(27) + 6 + 4 = 64 = 4 \cdot 16$, $16$ 의 배수. $b = 6$: $2(216) + 12 + 4 = 432 + 16 = 448 = 28 \cdot 16$, 배수. $b = 7$: $2(343) + 14 + 4 = 686 + 18 = 704 = 44 \cdot 16$, 배수. 비해 점검: $b = 5$ 는 $2(125) + 10 + 4 = 264 = 16 \cdot 16 + 8$, 배수 아님 — $5 \not\equiv 3, 6, 7 \pmod 8$ 이므로 맞음. 밀도 $\tfrac{3}{8}$ 로 $[5, 2024]$ 안의 해는 대략 $\tfrac{3}{8}(2020) \approx 758$ 개로 예측되며 $K = 758$ 과 정확히 일치. 자릿수의 합 $20$ 은 (D).

대안 접근: 도구 #5(패턴 찾기): 대수적 경우 분석 대신, $b = 1, 2, \dots, 16$ 에 대해 $2b^3 + 2b + 4 \pmod {16}$ 을 계산해 어느 $b$ 가 $0$ 을 주는지 표로 만듭니다. 통과하는 잔여류가 정확히 $b \equiv 3, 6, 7 \pmod 8$ 임을 표에서 곧장 읽을 수 있어 "홀수 제곱은 법 $8$ 에서 $1$" 사실을 부르지 않아도 됩니다. 그 뒤 $[1, 2024]$ 의 $\tfrac{3}{8}$ 에서 $b = 3$ 하나만 빼면 같은 결과.

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

5.NBT.A.1 여러 자리 수에서 한 자리의 값이 오른쪽 자리값의 10배임을 인식하기 (10진법의 자릿값 규칙을 $b$진법으로 일반화해 $2024_b = 2b^3 + 0 \cdot b^2 + 2b + 4$ 로 옮기고, 마지막에 $K = 758$ 의 자릿수의 합을 읽어내는 데 사용.)
6.NS.B.4 두 수의 최대공약수와 최소공배수 구하기 ($2b^3 + 2b + 4$ 에서 공통인수 $2$ 를 빼내, $\equiv 0 \pmod{16}$ 을 더 쉬운 $b^3 + b + 2 \equiv 0 \pmod 8$ 으로 줄이는 데 사용.)
4.OA.C.5 주어진 규칙을 따라 수 패턴을 만들고 그 특징을 파악 (법 $8$ 에 대한 잔여류를 주기 $8$ 의 반복 패턴으로 보고, 연속한 $8$ 정수마다 $3$ 개가 통과한다는 사실로부터 $[1, 2024]$ 의 해의 수를 $253 \times 3 = 759$ 로 세는 데 사용.)
8.EE.A.1 정수 지수의 성질을 알고 적용하기 (홀수 $b$ 에 대해 $b^2 \equiv 1 \pmod 8$ (따라서 $b^3 \equiv b \pmod 8$) 과 짝수 $b = 2k$ 에 대해 $(2k)^3 = 8k^3 \equiv 0 \pmod 8$ 이라는 두 사실을 써서 3차 합동식을 깨는 데 사용.)

⭐ $b$ 에 대한 다항식 안에 나눗셈 조건이 숨어 있을 때는 일을 쪼개세요 — $b$진법 수를 옮기고, 공통인수로 법을 줄이고, 홀수 $b$ 와 짝수 $b$ 를 따로 다루면 끝. 어떤 잔여류가 법 $8$ 에서 통과하는지 알아내면, 긴 범위에서 세는 일은 창의 $\tfrac{3}{8}$ 에 가장자리만 보정하면 됩니다.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: D

검토

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

비슷한 유형 더 풀어보기