AMC 10 · 2018 · #13

학년 6 number-theory
유형 Modular Cycle Frequency Count └ 세부 유형 Floor Count Across Residue Bins
modular-arithmeticplace-valuepattern-recognition pattern-recognitioneasier-related-problem ↑ 선수 지식: modular-arithmetic
📏 중간 풀이 💡 2 개 인사이트
문제
목록 101, 1001, 10001, 100001, …을 보자. 각 수는 1, 그다음 0들의 묶음, 그다음 다시 1로 이루어진다. 이 목록의 처음 2018개 수 중에서 101의 배수인 것이 몇 개인지 센다.

답을 골라 클릭하세요.

(A)
253
(B)
504
(C)
505
(D)
506
(E)
1009

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

풀이 과정
전략 패턴 찾기

도구 #5 (패턴 찾기): 각 항은 10의 거듭제곱에 1을 더한 꼴이고, 10의 거듭제곱을 101로 나눈 나머지는 짧은 주기로 반복된다. 그 주기를 찾으면 거대한 수에 대한 질문이 길이 4짜리 반복 목록에 대한 질문으로 바뀐다. 도구 #9 (더 쉬운 문제로 줄이기): 거대한 수 하나하나를 검사하는 대신, '항이 101로 나누어떨어지는가'를 훨씬 작은 질문 '10의 거듭제곱을 101로 나눈 나머지는 무엇인가'로 바꾼다. 도구 #2 (빠짐없이 나열하기): 어느 자리가 맞는지 알면, 답은 그저 2018까지 그 규칙에 맞는 자리를 세는 것이다.

1STEP 1

각 항을 10의 거듭제곱으로 쓰기

각 항은 1, 0들, 1 — 즉 10의 거듭제곱에 1을 더한 꼴이고, 지수는 자리보다 1 크다.

a_n = 10^ n+1 + 1
2STEP 2

나누어떨어짐을 나머지로 바꾸기

항이 101의 배수인 것은 +1 앞의 10의 거듭제곱이 101로 나눈 나머지 100을 남길 때뿐이다.

101 ∣ 10^ n+1+1 ⇔ 10^ n+1 의 나머지가 100 (mod 101)
3STEP 3

나머지의 주기 찾기

10의 거듭제곱을 101로 나눈 나머지는 10, 100, 91, 1로 나온 뒤 반복된다 — 길이 4의 주기이다.

10¹,10²,10³,10⁴ → 10, 100, 91, 1, 10, 100, 91, 1,…
4STEP 4

맞는 자리 골라내기

주기에서 나머지 100은 둘째 자리뿐이므로, 맞는 자리는 n = 1, 5, 9, 13, …이다.

10^ n+1≡ 100 ⇔ n+1≡ 2 (mod 4) ⇔ n = 1,5,9,13,…
5STEP 5

2018까지 그 자리 세기

자리 1, 5, 9, …, 2017은 n = 1+4k (k = 0…504)이고, 505개의 항 — 보기 (C)이다.

n = 1+4k ≤ 2018 → k ≤ 504 → 505 개 → (C)
정답
505
대략 네 자리마다 하나가 맞고 2018÷4≈504.5이므로, 답은 504나 505 부근이어야 한다 — 이는 멀리 떨어진 보기 (A) 253과 (E) 1009를 배제한다. 정확한 값은 504가 아니라 505인데, 첫 항(n=1, 즉 수 101 자체)이 이미 세어지므로 개수가 하나 늘기 때문이다. 함정인 (B) 504와 (D) 506은 그 경계를 잘못 센 결과이다. 신중히 보면 n=1부터 n=2017까지 4 간격으로 정확히 505개이다.
💡핵심 정리

10의 거듭제곱을 101로 나눈 나머지는 네 걸음마다 반복되므로, 목록에서 네 번째 수마다 하나만 101로 나누어떨어진다 — 자리 2018까지 그것을 세면 505이다.

  • 각 항을 10의 거듭제곱으로 쓰기
  • 나누어떨어짐을 나머지로 바꾸기
  • 나머지의 주기 찾기
  • 맞는 자리 골라내기
  • 2018까지 그 자리 세기

비슷한 유형 더 풀어보기

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