AMC 10 · 2009 · #25
Grade 8 number-theoryFor k>0, let Ik=10…064, where there are k zeros between the 1 and the 6. Let N(k) be the number of factors of 2 in the prime factorization of Ik. What is the maximum value of N(k)?
Pick an answer.
AMC 10 2009 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: For each $k>0$, the number $I_k$ is a $1$, then $k$ zeros, then the digits $6$ and $4$ (so $I_k=1\underbrace{0\cdots0}_{k}64$). Let $N(k)$ count how many times $2$ divides $I_k$ (the exponent of $2$ in its prime factorization). Find the largest value $N(k)$ can ever reach as $k$ ranges over the positive integers.
Givens: $I_k$ has a leading $1$, then exactly $k$ zeros, then $64$; $N(k)$ is the number of factors of $2$ in $I_k$ (its $2$-adic valuation); $k$ is a positive integer; Answer choices: $6,\ 7,\ 8,\ 9,\ 10$
Unknowns: The maximum of $N(k)$ over all positive integers $k$
Understand
Restated: For each $k>0$, the number $I_k$ is a $1$, then $k$ zeros, then the digits $6$ and $4$ (so $I_k=1\underbrace{0\cdots0}_{k}64$). Let $N(k)$ count how many times $2$ divides $I_k$ (the exponent of $2$ in its prime factorization). Find the largest value $N(k)$ can ever reach as $k$ ranges over the positive integers.
Givens: $I_k$ has a leading $1$, then exactly $k$ zeros, then $64$; $N(k)$ is the number of factors of $2$ in $I_k$ (its $2$-adic valuation); $k$ is a positive integer; Answer choices: $6,\ 7,\ 8,\ 9,\ 10$
Plan
Primary tool: #14 Extreme Principle
Secondary: #4 Introduce a Variable, #7 Identify Subproblems, #6 Guess and Check
The question asks for a maximum, so Tool #14 (Extreme Principle) sets the target: find where the count of $2$s 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+2}5^{k+2}+2^6$, exposing the two separate sources of $2$s. 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 $2$s appear; only when they are equal can the two pieces combine to release more $2$s. Tool #6 (Guess and Check) then tests that balance point directly ($k=4$) to read off the exact count.
Execute — Answer: B
5.NBT.A.2 Step 1 Write the number as a formula
- Read the place values.
- The final digits are $6$ (tens) and $4$ (units), so the last two digits form the fixed number $64$.
- Above them sit $k$ zeros, and above those the leading $1$.
- Counting places, the $1$ is $k+2$ steps to the left of the units digit, so it stands for $10^{k+2}$.
- Therefore $I_k=10^{k+2}+64$.
- As a check, $k=1$ gives $10^3+64=1064$, which is $1$, one zero, then $64$.
💡 Each zero you add just shifts the leading $1$ one more place, which multiplies its place value by another $10$.
8.EE.A.1 Step 2 Split each piece into 2s and 5s
- Every factor of $2$ has to come from one of the two terms, so prime-factor each.
- Since $10=2\cdot5$, the power of ten is $10^{k+2}=2^{k+2}\,5^{k+2}$.
- The tail is $64=2^6$.
- So $I_k=2^{k+2}5^{k+2}+2^6$.
- Now the whole problem is about the two exponents $k+2$ and $6$ on the two chunks of $2$.
💡 Powers of $10$ are just paired-up $2$s and $5$s, so pulling them apart shows exactly where the $2$s live.
6.NS.B.4 Step 3 Factor out the smaller power of 2
- When you add $2^{k+2}5^{k+2}$ and $2^6$, you can only pull out $2$s that both terms share, which is $2$ to the smaller of the two exponents $k+2$ and $6$.
- After factoring that out, whatever is left in the parentheses decides if any more $2$s survive.
- This naturally breaks into three subproblems: $k+2$ smaller than $6$, larger than $6$, or exactly equal to $6$.
💡 A sum is divisible by $2^m$ only as far as both parts are, so the weaker term caps the shared $2$s.
4.OA.B.4 Step 4 Case k < 4: the smaller side wins
- If $k+2<6$ (that is $k=1,2,3$), factor out $2^{k+2}$: $I_k=2^{k+2}\big(5^{k+2}+2^{\,4-k}\big)$.
- Inside, $5^{k+2}$ is odd, and since $4-k\ge1$ the term $2^{\,4-k}$ is even, so odd $+$ even $=$ odd.
- The parentheses hold no more $2$s, so $N(k)=k+2$.
- The best this case can do is $k=3$, giving $N(3)=5$.
💡 One odd plus one even is always odd, so the leftover part contributes zero extra $2$s.
4.OA.B.4 Step 5 Case k > 4: capped at 64's six 2s
- If $k+2>6$ (that is $k\ge5$), the tail $2^6$ is the weaker term, so factor out $2^6$: $I_k=2^6\big(2^{\,k-4}5^{k+2}+1\big)$.
- Since $k-4\ge1$, the term $2^{\,k-4}5^{k+2}$ is even, and even $+1$ is odd.
- So the parentheses are odd and $N(k)=6$ exactly, no matter how large $k$ grows.
- Piling on more zeros never helps.
💡 Once $64$ is the smaller stack of $2$s, adding an even number to it leaves an odd remainder, so it caps the count at $6$.
6.NS.B.3 Step 6 Boundary case k = 4: the two sides balance
- The only case left is $k+2=6$, i.e.
- $k=4$, where both terms carry exactly $2^6$: $I_4=2^6\,5^6+2^6=2^6\big(5^6+1\big)$.
- Now the parentheses can be even.
- Compute $5^6=15625$, so $5^6+1=15626=2\cdot 7813$, and $7813$ is odd.
- That gives one extra factor of $2$: $I_4=2^6\cdot2\cdot7813=2^7\cdot7813$.
- So $N(4)=7$.
- (Check: $I_4=1000064$ and $1000064\div128=7813$.)
💡 Only when the two equal stacks of $2$s meet does adding them release a fresh $2$.
6.EE.A.2 Step 7 Take the maximum
- Compare the three cases: $k<4$ gives at most $N=5$, $k>4$ gives $N=6$, and the balance point $k=4$ gives $N=7$.
- The largest is $7$, reached only at $k=4$.
- So the maximum value of $N(k)$ is $\boxed{7}$, which is choice $\textbf{(B)}$.
💡 The peak sits exactly at the boundary where the two powers of two match, not at the extremes of $k$.
5.NBT.A.2 Read the place values. The final digits are $6$ (tens) and $4$ (units), so the l 8.EE.A.1 Every factor of $2$ has to come from one of the two terms, so prime-factor each. 6.NS.B.4 When you add $2^{k+2}5^{k+2}$ and $2^6$, you can only pull out $2$s that both te 4.OA.B.4 If $k+2<6$ (that is $k=1,2,3$), factor out $2^{k+2}$: $I_k=2^{k+2}\big(5^{k+2}+2 4.OA.B.4 If $k+2>6$ (that is $k\ge5$), the tail $2^6$ is the weaker term, so factor out $ 6.NS.B.3 The only case left is $k+2=6$, i.e. $k=4$, where both terms carry exactly $2^6$: 6.EE.A.2 Compare the three cases: $k<4$ gives at most $N=5$, $k>4$ gives $N=6$, and the b Review
Reasonableness: The answer must be at least $6$, since $64=2^6$ guarantees six factors of $2$ before anything cancels, and choices start at $6$. The extra factor at $k=4$ is real: $1000064=2^7\cdot7813$ with $7813$ odd, so exactly seven $2$s 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 $\textbf{(B)}$ and rules out $8,9,10$, which would need the parentheses to hold two or more extra $2$s — impossible here since $5^6+1$ has only one.
Alternative: Use the Lifting-the-Exponent viewpoint. Factor $I_k=2^6\big(2^{\,k-4}5^{k+2}+1\big)$ once $2^6$ is pulled out (valid for $k\ge4$; smaller $k$ clearly gives $N=k+2\le5$). The bracket is odd unless $k-4=0$, i.e. $k=4$, where it becomes $5^6+1$; by the sum-of-like-powers rule $5^6+1$ is divisible by $5+1=6$ but only a single factor of $2$, so $N$ climbs to $7$ exactly once. Same conclusion, $\textbf{(B)}$.
CCSS standards used (min grade 8)
5.NBT.A.2Explain patterns in number of zeros and placement of decimal point (Reading the digit picture $1\,0\cdots0\,64$ as the formula $10^{k+2}+64$ by tracking place value.)8.EE.A.1Know and apply the properties of integer exponents (Rewriting $10^{k+2}=2^{k+2}5^{k+2}$ and $64=2^6$ and manipulating the exponents when factoring.)6.NS.B.4Find greatest common factor and least common multiple of two numbers (Pulling out the common power of $2$ — the smaller of $2^{k+2}$ and $2^6$ — from the sum of the two terms.)4.OA.B.4Find all factor pairs and recognize multiples; determine prime or composite (Judging the parity (odd vs. even) of the leftover parentheses in the $k<4$ and $k>4$ cases.)6.NS.B.3Fluently add, subtract, multiply, and divide multi-digit decimals (Computing $5^6=15625$, then $15626=2\cdot7813$, to extract the extra factor of $2$ at $k=4$.)6.EE.A.2Write, read, and evaluate expressions in which letters stand for numbers (Evaluating $N(k)$ across the three cases and selecting the maximum.)
⭐ Split the number into its $2$s from $10^{k+2}$ and its $2$s 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 $\textbf{(B)}$.
⭐ Split the number into its $2$s from $10^{k+2}$ and its $2$s 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 $\textbf{(B)}$.
More like this
Same archetype — closest grade level first.