AMC 10 · 2017 · #14

학년 7 probability
유형 Modular Cycle Frequency Count └ 세부 유형 Power-Cycle Residue
modular-arithmeticunits-digit-trackingprobability-basic pattern-recognitioneulers-theorem ↑ 선수 지식: modular-arithmetic
📏 중간 풀이 💡 2 개 인사이트
문제
정수 N을 1 ≤ N ≤ 2020에서 무작위로 하나 고른다. 모든 값이 똑같이 나올 수 있다. N¹⁶을 5로 나눈 나머지가 1일 확률을 구하라.

답을 골라 클릭하세요.

(A)
$\frac{1}{5}$
(B)
$\frac{2}{5}$
(C)
$\frac{3}{5}$
(D)
$\frac{4}{5}$
(E)
1

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

풀이 과정
전략 패턴 찾기

N이 2020까지 갈 때 N¹⁶은 엄청나게 큰 수이므로, 도구 #9(더 쉬운 문제로 줄이기)로 줄인다. 곱을 5로 나눈 나머지는 각 인수의 나머지로만 정해지므로, 답은 오직 N을 5로 나눈 나머지에만 달려 있어 0,1,2,3,4의 다섯 가지 경우뿐이다. 도구 #5(패턴 찾기): 각 경우에서 거듭제곱의 나머지는 짧게 반복되는 주기를 이루므로, 큰 거듭제곱을 직접 계산하지 않고 16번째 단계가 어디에 떨어지는지만 본다. 도구 #2(빠짐없이 나열하기)로 다섯 경우를 나란히 정리하고, 도구 #7(작은 문제로 쪼개기)로 "1부터 2020까지 성공하는 수 세기"를 "5의 배수 세기"라는 쉬운 작은 문제로 바꾼다.

1STEP 1

N의 나머지만 중요하다

N¹⁶을 5로 나눈 나머지는 N의 나머지에만 달려 있으니, 2020개 전부 대신 다섯 경우 N ≡ 0, 1, 2, 3, 4만 확인한다.

N¹⁶ mod 5 는 N mod 5∈{0,1,2,3,4} 에만 달림
2STEP 2

각 경우의 주기 추적하기

거듭제곱 나머지는 짧은 주기로 돌고 16은 주기를 끝내므로, 2¹⁶, 3¹⁶, 4¹⁶은 모두 나머지 1이고 1은 1, 0은 0에 머문다.

2¹⁶,3¹⁶,4¹⁶≡ 1, 1¹⁶≡ 1, 0¹⁶≡ 0 (mod 5)
3STEP 3

어떤 N이 성공하나

0이 아닌 네 경우는 모두 나머지 1이고 N ≡ 0만 실패하니, N¹⁶의 나머지가 1인 것은 정확히 N이 5의 배수가 아닐 때이다.

N¹⁶≡ 1 (mod 5) ⇔ 5 ∤ N
4STEP 4

세고 나누기

1부터 2020까지 5의 배수는 404개, 나머지 1616개가 성공하므로 확률은 1616/2020 = 4/5 → (D)이다.

(2020-404)/2020=1616/2020=4/5 → (D)
정답
4/5
똑같이 나올 수 있는 다섯 나머지 묶음 0,1,2,3,4 중 정확히 넷이 성공하고 하나(5의 배수)만 실패하므로 곧장 4/5를 가리킨다. 2020=5× 404이므로 다섯 묶음이 범위를 똑같이 나누어, 개수 1616/2020이 남는 부분 없이 깔끔하게 4/5로 약분된다. 4/5=0.8은 0과 1 사이의 큰 값으로, 5의 배수만 빠진다는 사실과 잘 맞는다.
💡핵심 정리

N을 5로 나눈 나머지만 중요한데, 5의 배수를 뺀 모든 N에서 N¹⁶의 나머지가 1이다 — 전체의 4/5, 즉 선택지 (D)이다.

  • N의 나머지만 중요하다
  • 각 경우의 주기 추적하기
  • 어떤 N이 성공하나
  • 세고 나누기

비슷한 유형 더 풀어보기

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