AMC 10 · 2009 · #25

Grade 8 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

prime-factorizationexponentsoptimization caseworkbound-inequality-then-enumerate ↑ Prerequisites: prime-factorization

📏 Long solution 💡 3 insights

Problem

For each positive integer k, the number I_k is written as a 1, then exactly k zeros, then the two digits 6 and 4; for example, I_1 = 1064. Let N(k) be the number of times 2 divides I_k, that is, the exponent of 2 in its prime factorization. Find the largest value N(k) can ever reach as k ranges over the positive integers.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Extreme Principle

The question asks for a maximum, so Tool #14 (Extreme Principle) sets the target: find where the count of 2s is pushed as high as possible, which turns out to be a single boundary case. To get there, Tool #4 (Introduce a Variable) rewrites the digit-picture I_k as the clean formula 10^k+2+64 and then as 2^k+25^k+2+2⁶, exposing the two separate sources of 2s. Tool #7 (Identify Subproblems) splits the work by comparing the two powers k+2 and 6: when they differ, the smaller one wins and no extra 2s appear; only when they are equal can the two pieces combine to release more 2s. Tool #6 (Guess and Check) then tests that balance point directly (k=4) to read off the exact count.

1STEP 1

Write the number as a formula

The last two digits are the fixed 64, and the leading 1 sits $k+2$ places up, so $I_k=10^{k+2}+64$ ; check $I_1=1064$ .

I_k = 10^k+2 + 64

2STEP 2

Split each piece into 2s and 5s

Since $10=2\cdot5$ , the number splits as $I_k=2^{k+2}5^{k+2}+2^6$ — two separate stacks of 2s.

I_k = 2^k+25^k+2 + 2⁶

3STEP 3

Factor out the smaller power of 2

Only the 2s both terms share come out — 2 raised to the smaller of $k+2$ and 6 — so three cases follow.

min(k+2, 6) factors of 2 come out first

4STEP 4

Case k ＜ 4: the smaller side wins

For $k=1,2,3$ the bracket $5^{k+2}+2^{4-k}$ is odd plus even, hence odd, so $N(k)=k+2$ , at most 5.

I_k=2^k+2(5^k+2+2⁴-k), N(k)=k+2 ≤ 5

5STEP 5

Case k ＞ 4: capped at 64's six 2s

For $k \ge 5$ the tail is weaker: $I_k=2^6(2^{k-4}5^{k+2}+1)$ is even plus 1, so $N(k)$ sticks at 6.

I_k=2⁶(2^k-45^k+2+1), N(k)=6

6STEP 6

Boundary case k = 4: the two sides balance

At $k=4$ both stacks are $2^6$ : $I_4=2^6(5^6+1)=2^<span class="hl-ask">7</span>\cdot7813$ with 7813 odd, so $N(4)$ hits 7.

I₄=2⁶(5⁶+1)=2⁶·15626=2⁷·7813, N(4)=7

7STEP 7

Take the maximum

The three cases give at most 5, exactly 6, and 7, so the maximum is 7, reached only at k=4 — choice (B).

max N(k)=max{5,6,7}=7=(B)

Answer

The answer must be at least 6, since 64=2⁶ guarantees six factors of 2 before anything cancels, and choices start at 6. The extra factor at k=4 is real: 1000064=2⁷·7813 with 7813 odd, so exactly seven 2s and no more. For every other k the parentheses came out odd, capping the count at 6 or below, so 7 genuinely cannot be beaten. This matches choice (B) and rules out 8,9,10, which would need the parentheses to hold two or more extra 2s — impossible here since 5⁶+1 has only one.

💡Key takeaway

Split the number into its 2s from 10^k+2 and its 2s from 64; you gain an extra factor of 2 only when those two stacks are exactly equal, which happens at k=4 and gives the maximum N=7, choice (B).

Write the number as a formula
Split each piece into 2s and 5s
Factor out the smaller power of 2
Case k ＜ 4: the smaller side wins
Case k ＞ 4: capped at 64's six 2s
Boundary case k = 4: the two sides balance
Take the maximum