AMC 10 · 2016 · #25

Grade 11 algebra

Archetype Modular Cycle Frequency Count └ Sub-archetype Power-Cycle Residue

recursive-sequencemodular-arithmeticexponentseulers-theorem convert-to-algebrapattern-recognition ↑ Prerequisites: recursive-sequencemodular-arithmetic

📏 Long solution 💡 4 insights

Problem

Each term multiplies the previous by the square of the one before, and running products are taken. Find the first whole-number length.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Introduce a Variable

Multiplying a_n values directly is hopeless — they are nineteenth roots of 2 and grow like a tower. Tool #4 (Introduce a Variable) is the whole solution: name the exponent, a_n=2^e_n, and then name the scaled exponent b_n=19e_n. Under that renaming the multiplicative rule a_n=a_n-1a_n-2² turns into the additive rule b_n=b_n-1+2b_n-2, and a product turns into a sum — Tool #13 (Convert to Algebra) in its purest form. Tool #7 (Identify Subproblems) separates two questions that are easy to blur: first, why is an integer product the same as an integer exponent (this needs unique factorization, not hand-waving); second, when is the exponent sum divisible by 19. Tool #5 (Look for a Pattern) supplies the closed form for b_n and the powers of 2 modulo 19. Finally the question asks for a smallest k, so Tool #14 (Extreme Principle) and Tool #3 (Eliminate Possibilities) compare the odd-k and even-k candidates and rule out everything before the winner.

1STEP 1

Every term is a power of two

Every term is a power of one number.

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

Integer forces a whole exponent

Being whole forces a whole exponent.

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

3STEP 3

Scale the exponents by nineteen

Scaling clears the fraction entirely.

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

Closed form, proved by induction

The exponents have a proved closed form.

b_n=(2ⁿ-(-1)ⁿ)/3 for all n ≥ 0

5STEP 5

Add the terms with geometric sums

Geometric sums add them exactly.

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

6STEP 6

Divide out the harmless factor three

A harmless factor divides out.

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

7STEP 7

Two has order eighteen mod nineteen

The base's order is eighteen.

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

8STEP 8

Take the smaller of two candidates

The smaller candidate is 17, choice (A).

k odd: 18 ∣ k+1→ k_min=17; k even: 18 ∣ k→ k_min=18; min(17,18)=17

Answer

Check the target value concretely: 3S₁₇=2¹⁸-1=262143=19 · 13797, so S₁₇=87381=19 · 4599 and the product is 2⁴⁵⁹⁹ — an integer, as claimed. Check that nothing smaller sneaks through by listing the running sums directly from b₁,b₂,…=1,1,3,5,11,21,43,85,171,…: S_k=1,2,5,10,21,42,85,170,341,682,…, and none of S₁ through S₁₆ is a multiple of 19 (each equals (2^k+1-1)/3 or (2^k+1-2)/3, which would force 18 ∣ k+1 or 18 ∣ k). The answer choices themselves are a useful cross-check: applying the same criterion, k=18 also gives an integer, while k=19,20,21 do not — since 18 divides neither 19,20,21 nor 20,21,22. So exactly the two smallest choices work and the smallest is 17, matching (A). A wrong turn worth naming: forgetting that the product starts at a₁ and including a₀=1 changes nothing (its exponent is 0), but starting the sum at b₂ instead of b₁ would shift everything and give 18 — the trap answer (B).

💡Key takeaway

Stop multiplying and start adding: every term is 2 to some exponent, the product is an integer only when those exponents add to a whole number, and chasing that sum modulo 19 shows k=17 is the first time it happens.

Every term is a power of two
Integer forces a whole exponent
Scale the exponents by nineteen
Closed form, proved by induction
Add the terms with geometric sums
Divide out the harmless factor three
Two has order eighteen mod nineteen
Take the smaller of two candidates