AMC 10 · 2024 · #11

학년 8 number-theory

유형 Modular Cycle Frequency Count └ 세부 유형 Floor Count Across Residue Bins

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

📏 긴 풀이 💡 4 개 인사이트

문제

5 이상 2024 이하의 정수 밑 b 중에서, b진법 네 자리 수 2024가 16으로 나누어떨어지는 b가 몇 개인지 세어 그 개수를 K라 합시다. K의 각 자리 숫자의 합을 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 작은 문제로 쪼개기

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

1STEP 1

자릿수를 다항식으로

2024는 2b³ 더하기 2b 더하기 4입니다.

2024_b = 2b³ + 2b + 4, 2b³ + 2b + 4 ≡ 0 (mod 16)

2STEP 2

공통인수 2 빼내기

조건이 법 8짜리로 가벼워집니다.

2(b³ + b + 2) ≡ 0 (mod 16) ⟺ b³ + b + 2 ≡ 0 (mod 8)

3STEP 3

홀수 밑 다루기

홀수는 세제곱해도 b와 같은 나머지를 남깁니다.

b + b + 2 ≡ 0 (mod 8) → 2(b+1) ≡ 0 (mod 8) → b ≡ 3 (mod 4)

4STEP 4

살아남는 홀수 나머지

홀수 쪽에서는 3과 7이 통과합니다.

{b 홀수: b ≡ 3 (mod 4)} = {b ≡ 3 (mod 8)} ∪ {b ≡ 7 (mod 8)}

5STEP 5

짝수 밑 다루기

짝수 쪽에서는 6 하나만 통과합니다.

(2k)³ + 2k + 2 ≡ 2k + 2 ≡ 0 (mod 8) → k ≡ 3 (mod 4) → b ≡ 6 (mod 8)

6STEP 6

밀도 읽기

여덟 개 중 세 개가 살아남습니다.

유효한 b (mod 8) ∈ {3, 6, 7}, 밀도 = 3/8

7STEP 7

범위 안에서 세기

경계를 조정하면 K는 758입니다.

K = 253 · 3 - 1 = 759 - 1 = 758

8STEP 8

자릿수 더하기

7 더하기 5 더하기 8은 20입니다.

7 + 5 + 8 = 20 → (D)

정답

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

💡핵심 정리

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