AMC 10 · 2006 · #25

학년 8 number-theorypattern

유형 Branching State Enumeration └ 세부 유형 Rule-Governed Process Simulation

recursive-sequencegcdparitymodular-arithmetic invariant-monovariantpattern-recognition ↑ 선수 지식: gcdrecursive-sequence

📏 긴 풀이 💡 4 개 인사이트

문제

어떤 수열이 999와 또 하나의 값으로 시작하고, 이후 각 항은 앞 두 항의 차의 절댓값이다. 2006번째 항이 1이 되게 하는 시작값의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

165

(B)

324

(C)

495

(D)

499

(E)

660

풀이 과정

전략 패턴 찾기

2006 번째 항은 직접 계산해서 도달할 수 없으므로, 수열이 진행해도 변하지 않는 양이나 한 방향으로만 변하는 양을 찾는 것이 계획이다. Tool #15 (다르게 정리하기)는 같은 수열을 두 가지 방식으로 보라고 말한다. 이웃한 두 항의 최대공약수로 보는 방식과, 2로 나눈 나머지로 보는 방식이다. 앞의 것은 아예 변하지 않고, 뒤의 것은 주기 3으로 반복되는데 2006을 3으로 나눈 나머지가 문제 전체를 좌우한다. 이 두 관점이 함께 대부분의 시작값을 배제한다. 그러나 배제는 절반의 작업일 뿐이다. 두 검사를 통과한 시작값도 실제로 2006 번째 항 전에 1에 도달해야 하는데, 여기까지의 논증은 그것을 전혀 말해 주지 않는다. 그 빈틈을 Tool #14 (극단의 원리)가 메운다. 이웃한 두 항 중 큰 쪽을 지켜보면 두 걸음마다 반드시 줄어들 수밖에 없으므로 999 번 넘게 줄어들 수는 없다. Tool #16 (관점 바꾸기)은 마지막 세기를 999와 공약수가 없는 수를 세는 문제로 바꾸고, Tool #9 (더 쉬운 문제로 줄이기)는 999를 9로 바꾼 축소판에서 이 판정 기준을 검증한다.

1STEP 1

수열이 깎여 내려가는 모습 보기

예 하나가 수열이 반복되는 덩어리로 깎여 내려감을 보여 준다.

a₂=4: 999, 4, 995, 991, 4, 987, 983, 4, … ; c, c → c, c, 0, c, c, 0, … (영원히)

2STEP 2

공통 약수는 변하지 않는다

규칙이 공약수를 영원히 그대로 둔다.

gcd(a_n+1,|a_n+1-a_n|)=gcd(a_n+1,a_n) → 모든 n 에 대해 g=gcd(999,a₂) ; g ∣ a₂₀₀₆=1 → gcd(999,a₂)=1, 999=3³ · 37

3STEP 3

홀짝은 셋마다 반복된다

홀짝이 세 항마다 반복되어 목표 항을 정한다.

a₂ 홀수: 1,1,0,1,1,0,… (mod 2) → a₂₀₀₆ 홀수 ; a₂ 짝수: 1,0,1,1,0,1,… (mod 2) → a₂₀₀₆ 짝수 ; 2006=3 · 668+2

4STEP 4

남은 빈틈에 이름 붙이기

지금까지는 한 방향만 증명되어 빈틈이 남는다.

증명된 것: a₂₀₀₆=1 → (gcd(999,a₂)=1이고 a₂ 홀수) ; 아직 필요한 것: (gcd(999,a₂)=1이고 a₂ 홀수) → a₂₀₀₆=1

5STEP 5

이웃한 두 항 중 큰 쪽은 반드시 줄어든다

이웃한 둘 중 큰 쪽이 반드시 줄어 수열이 영원히 멈출 수 없다.

a_j ＞ a_j+1 ＞ 0: a_j+2=a_j-a_j+1, a_j+3=|a_j-2a_j+1| → max(a_j+2,a_j+3) ＜ a_j ; a_j+1 ＞ a_j ＞ 0: a_j+2=a_j+1-a_j, a_j+3=a_j → max(a_j+2,a_j+3) ＜ a_j+1 ; 999=M₁ ＞ M₂ ＞ … ＞ M₁₀₀₀ → M₁₀₀₀ ≤ 0, 불가능

6STEP 6

빈틈을 메우고 1에 도달하기

그것이 빈틈을 메우고 수열이 실제로 1에 도달한다.

a_i=a_i+1=c → c=gcd(a_i,a_i+1)=g=1 ; a_j=0, j ≥ 3 → a_j-2=a_j-1=1 ; ∃ i ≤ 1997: a_i=a_i+1=1 → a₂₀₀₆∈{0,1}, 그리고 홀수 → a₂₀₀₆=1

7STEP 7

999와 서로소인 홀수 세기

서로소인 홀수를 세면 648개다.

a₂ 홀수이고 gcd(a₂,999)=1⇔ gcd(a₂,1998)=1, 1998=2 · 3³ · 37 ; φ(1998)=φ(2) φ(27) φ(37)=1 · 18 · 36=648

8STEP 8

범위를 반으로 접기

범위를 반으로 접으면 324, 보기 (B).

x⟼ 1998-x 는 648 개 위의 고정점 없는 대합이며 [1,998]과 [1000,1997]을 맞바꾼다 ; 648/2=324 → (B)

정답

324

여기서 센 것은 "a₂₀₀₆=1 일 필요충분조건은 a₂가 홀수이고 gcd(a₂,999)=1 인 것"이라는 정확한 판정 기준이므로, 양쪽 방향 모두 검증할 가치가 있다. 문제를 축소해 보자 (Tool #9). 999를 9로 바꾸고 첨자는 3으로 나눈 나머지가 2 인 것을 유지한다. 판정 기준은 작동하는 시작값이 9 미만의 홀수 중 9와 서로소인 1,5,7, 즉 φ(9)/2=3 개라고 예측하는데, 실제로 수열을 돌려 보면 정확히 {1,5,7}이 작동한다. 999를 27로 바꾼 경우도 {1,5,7,11,13,17,19,23,25}를 예측하고 실제로 그렇게 나오며, 15로 바꾸면 {1,7,11,13}이 나온다. 둘째, 세기 자체를 파이 함수 없이 다시 할 수 있다. {1,…,998} 안의 홀수는 499 개이고, 그중 3의 배수는 166 개 (3,9,…,993), 37의 배수는 13 개 (37,111,…,925), 둘 다의 배수 즉 111의 홀수 배수는 4 개 (111,333,555,777)이다. 포함배제로 499-166-13+4=324가 되어 일치한다. 셋째, 가장 중요하게, 단계 5의 첨자 상한은 형식적인 절차가 아니라 실제로 결정적이다. 가장 느린 생존자는 a₂=1이고 그 수열은 999,1,998,997,1,996,995,1,… 로 첨자 1498이 되어서야 1,1에 도달한다. 그러니 2006은 여유 있게 충분하지만 여유가 아주 큰 것은 아니다. 만약 문제가 a₁₀₁=1을 물었다면 (101도 3으로 나눈 나머지가 2이다) 324 개 중 301 개만 조건을 만족해서, 홀짝과 최대공약수만 쓰는 논증은 틀린 개수를 준다. 끝으로 오답 선택지는 정확히 지름길들이다. 499는 최대공약수 조건을 잊었을 때의 홀수 a₂의 개수이고, φ(999)=648은 홀짝 조건을 잊었을 때의 서로소인 a₂의 개수이다. 324는 그것의 절반으로, a₂ 세 개 중 대략 하나를 남기는 조건에 맞는 크기이다.

💡핵심 정리

규칙으로 정의된 수열을 끝까지 따라갈 수 없을 때는, 절대 변하지 않는 것 (여기서는 이웃한 두 항의 공통 약수)과 줄어들기만 하는 것 (여기서는 이웃한 두 항 중 큰 쪽)을 찾아라. 그 둘이 함께 2006 번째 항이 어디에 있어야 하는지 알려 준다.

수열이 깎여 내려가는 모습 보기
공통 약수는 변하지 않는다
홀짝은 셋마다 반복된다
남은 빈틈에 이름 붙이기
이웃한 두 항 중 큰 쪽은 반드시 줄어든다
빈틈을 메우고 1에 도달하기
999와 서로소인 홀수 세기
범위를 반으로 접기