AMC 10 · 2002 · #21

학년 6 pattern
recursive-sequenceunits-digit-trackingpattern-recognition systematic-enumeration ↑ 선수 지식: recursive-sequenceunits-digit-tracking
📏 긴 풀이 💡 3 개 인사이트
문제
수열은 4,7로 시작하고, 세 번째 항부터는 각 항이 바로 앞 두 항의 합의 일의 자리 숫자이다. S_n을 첫 n개 항의 합이라 하자. S_n이 10,000을 넘는 가장 작은 n을 구하여라.

답을 골라 클릭하세요.

(A)
1992
(B)
1999
(C)
2001
(D)
2002
(E)
2004
풀이 과정
전략 패턴 찾기

이천 개의 항을 손으로 더하는 것은 말이 되지 않고, 보기들은 서로 너무 가까워서 어림만으로는 가려낼 수 없다. 도구 #2(빠짐없이 나열하기)로 무언가 되풀이될 때까지 항을 적는다. 도구 #5(패턴 찾기)는 그 되풀이를 희망이 아니라 증명으로 바꾼다. 각 항이 앞 두 항으로 결정되므로, 연속한 두 항의 쌍이 다시 나타나는 순간 수열 전체가 영원히 되풀이된다. 그러면 도구 #9(더 쉬운 문제로 줄이기)가 수천 개 항의 합을 짧은 한 덩어리의 합과 곱셈으로 바꿔 준다. 남는 것은 누적합이 한 덩어리 도중에 10,000을 넘는 마지막 구간뿐이고, 그 정도는 도구 #6(추측하고 확인하기)으로 한 항씩 밟아 가면 충분하다.

1STEP 1

쌍이 되풀이될 때까지 항 적기

규칙대로 적으면 처음 쌍 4,7이 13, 14번째에 되돌아오므로 덩어리 길이는 12이다.

4,7,1,8,9,7,6,3,9,2,1,3 | 4,7,…
2STEP 2

덩어리가 영원히 반복됨을 증명하기

같은 쌍은 같은 미래를 강제하므로 수열은 첫 항부터 주기적이다.

(a₁₃,a₁₄)=(a₁,a₂) → a_n+12=a_n (모든 n ≥ 1)
3STEP 3

한 덩어리를 더하고 여러 덩어리로 늘리기

한 덩어리의 합은 60이므로 k개 덩어리는 12k항에서 60k를 준다.

4+7+1+8+9+7+6+3+9+2+1+3=60, S₁₂k=60k
4STEP 4

목표 아래 마지막 온전한 덩어리 찾기

10,000 = 60 · 166 + 40이므로 마지막 온전한 덩어리는 S₁₉₉₂ = 9960에서 끝나 아직 모자란다.

10,000=60 · 166+40, S₁₉₉₂=9960, S₂₀₀₄=10,020
5STEP 5

다음 덩어리를 한 항씩 밟기

다음 덩어리를 밟으면 S₁₉₉₈ = 9996, S₁₉₉₉ = 10,002이므로 답은 1999, 보기 (B).

S₁₉₉₈=9996 ≤ 10,000 < 10,002=S₁₉₉₉ → (B)
정답
1999
어림 계산도 같은 동네에 떨어진다. 덩어리의 평균은 항당 60/12=5이므로 10,000에 이르려면 대략 10,000/5=2000개 항이 필요하고, 1999는 바로 그 자리에 있다. 보기들은 진짜 넘어섬 지점 주변에 늘어놓은 아슬아슬한 오답 모음이다. (A) 1992는 마지막 온전한 덩어리 지점으로, 그때 합은 9960이라 목표에 아예 닿지 못한다. (E) 2004는 다음 온전한 덩어리 지점으로 합이 10,020이니 목표를 넘기기는 하지만, 넘어섬은 이미 다섯 항 전에 일어났으므로 늦다. (C) 2001과 (D) 2002도 넘어섬 지점 뒤에 있어 10,000을 넘기지만 가장 작은 n은 아니다. 두 끝점의 정확한 값이 결론을 확정한다. S₁₉₉₈=9996은 부등식을 만족하지 못하고 S₁₉₉₉=10,002는 만족한다.
💡핵심 정리

규칙이 마지막 두 항만 본다면, 쌍이 되풀이되는 순간 수열 전체가 영원히 돈다. 그러니 한 바퀴를 더해서 곱하고, 남은 항만 손으로 밟아 가면 된다.

  • 쌍이 되풀이될 때까지 항 적기
  • 덩어리가 영원히 반복됨을 증명하기
  • 한 덩어리를 더하고 여러 덩어리로 늘리기
  • 목표 아래 마지막 온전한 덩어리 찾기
  • 다음 덩어리를 한 항씩 밟기