AMC 10 · 2016 · #25

학년 11 algebra

유형 Modular Cycle Frequency Count └ 세부 유형 Power-Cycle Residue

recursive-sequencemodular-arithmeticexponentseulers-theorem convert-to-algebrapattern-recognition ↑ 선수 지식: recursive-sequencemodular-arithmetic

📏 긴 풀이 💡 4 개 인사이트

문제

각 항이 앞 항에 그 앞 항의 제곱을 곱한 것이고, 누적 곱을 만든다. 처음으로 정수가 되는 길이를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 변수 도입하기

a_n 값을 직접 곱하는 것은 가망이 없다. 이들은 2의 19제곱근이고 탑처럼 커진다. 도구 #4(변수 도입하기)가 풀이의 전부다: 지수에 이름을 붙여 a_n=2^e_n이라 하고, 다시 배율을 맞춘 지수 b_n=19e_n 에 이름을 붙인다. 이 이름 바꾸기 아래에서 곱셈 규칙 a_n=a_n-1a_n-2²은 덧셈 규칙 b_n=b_n-1+2b_n-2가 되고, 곱은 합이 된다. 이것이 도구 #13(대수로 바꾸기)의 가장 순수한 형태다. 도구 #7(작은 문제로 쪼개기)은 헷갈리기 쉬운 두 질문을 분리한다. 첫째, 곱이 정수인 것과 지수가 정수인 것이 왜 같은가(이건 얼버무릴 게 아니라 소인수분해의 유일성이 필요하다). 둘째, 지수의 합이 언제 19로 나누어떨어지는가. 도구 #5(패턴 찾기)는 b_n 의 닫힌 꼴과 19를 법으로 한 2의 거듭제곱을 제공한다. 마지막으로 문제가 가장 작은 k 를 묻고 있으므로, 도구 #14(극단의 원리)와 도구 #3(가능성 지우기)이 홀수 k 후보와 짝수 k 후보를 비교하고 승자 이전의 모든 값을 지운다.

1STEP 1

모든 항은 2의 거듭제곱

모든 항이 한 수의 거듭제곱이다.

a_n=2^e_n, e₀=0, e₁=1/19, e_n=e_n-1+2e_n-2; a₁a₂… a_k=2^E_k, E_k=Σ_i=1^ke_i

2STEP 2

정수이면 지수는 정수

정수가 되려면 지수가 정수여야 한다.

2^p/q=NinZ_ ＞ 0 → N^q=2^p → N=2^t → tq=p → p/qinZ

3STEP 3

지수에 19를 곱해 정수로

배로 늘리면 분수가 완전히 사라진다.

b_n=19e_n: b₀=0, b₁=1, b_n=b_n-1+2b_n-2; E_k=S_k/19, S_k=Σ_i=1^kb_i

4STEP 4

닫힌 꼴을 귀납법으로 증명

지수에 증명된 닫힌 식이 있다.

b_n=(2ⁿ-(-1)ⁿ)/3 (모든 n ≥ 0)

5STEP 5

등비수열 합으로 더하기

등비수열 합이 그것을 정확히 더한다.

3S_k=(2^k+1-2)-Σ_i=1^k(-1)^i= 2^k+1-2,& k 짝수 ; [2pt] 2^k+1-1,& k 홀수

6STEP 6

무해한 인수 3을 걷어내기

무해한 인수가 지워진다.

gcd(3,19)=1 → (19 ∣ S_k ⇔ 19 ∣ 3S_k); k 짝수: 2^k≡ 1, k 홀수: 2^k+1≡ 1 (mod 19)

7STEP 7

19를 법으로 2의 위수는 18

그 밑의 위수는 18이다.

2⁶≡ 7, 2⁹≡ -1, 2¹⁸≡ 1 (mod 19) → ord₁₉(2)=18; 2^m≡ 1 ⇔ 18 ∣ m

8STEP 8

두 후보 중 작은 쪽 고르기

더 작은 후보는 17, 보기 (A).

k 홀수: 18 ∣ k+1→ k_min=17; k 짝수: 18 ∣ k→ k_min=18; min(17,18)=17

정답

목표 값을 직접 확인하자. 3S₁₇=2¹⁸-1=262143=19 · 13797 이므로 S₁₇=87381=19 · 4599이고 곱은 2⁴⁵⁹⁹, 즉 주장대로 정수다. 더 작은 값이 몰래 통과하지 않는지도 확인한다. b₁,b₂,…=1,1,3,5,11,21,43,85,171,… 에서 누적합은 S_k=1,2,5,10,21,42,85,170,341,682,… 이고 S₁부터 S₁₆까지 19의 배수는 하나도 없다(각각 (2^k+1-1)/3 또는 (2^k+1-2)/3 이며, 그러려면 18 ∣ k+1 또는 18 ∣ k 가 필요하다). 선택지 자체도 좋은 교차 검증이 된다. 같은 기준을 적용하면 k=18도 정수를 주지만 k=19,20,21은 아니다. 18은 19,20,21도 20,21,22도 나누지 못하기 때문이다. 즉 가장 작은 두 선택지만 조건을 만족하고 그중 작은 쪽이 17 이므로 (A)와 일치한다. 짚어둘 만한 함정: 곱이 a₁부터 시작한다는 점을 잊고 a₀=1을 포함해도 지수가 0이라 아무것도 바뀌지 않지만, 합을 b₁이 아니라 b₂부터 시작하면 전체가 한 칸 밀려 18이 나온다. 그것이 함정 선택지 (B) 다.

💡핵심 정리

곱하기를 멈추고 더하기로 바꾸면 된다. 모든 항은 2의 어떤 지수이고, 곱이 정수가 되는 것은 그 지수들의 합이 정수일 때뿐이며, 그 합을 19로 나눈 나머지를 쫓아가면 처음 그렇게 되는 순간이 k=17이다.

모든 항은 2의 거듭제곱
정수이면 지수는 정수
지수에 19를 곱해 정수로
닫힌 꼴을 귀납법으로 증명
등비수열 합으로 더하기
무해한 인수 3을 걷어내기
19를 법으로 2의 위수는 18
두 후보 중 작은 쪽 고르기