During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

Difference between revisions of "2017 AIME I Problems/Problem 9"

Problem 9

Let $a_{10} = 10$, and for each integer $n >10$ let $a_n = 100a_{n - 1} + n$. Find the least $n > 10$ such that $a_n$ is a multiple of $99$.

Solution 1

Writing out the recursive statement for $a_n, a_{n-1}, \dots, a_{10}$ and summing them gives $$a_n+\dots+a_{10}=100(a_{n-1}+\dots+a_{10})+n+\dots+10$$ Which simplifies to $$a_n=99(a_{n-1}+\dots+a_{10})+\frac{1}{2}(n+10)(n-9)$$ Therefore, $a_n$ is divisible by 99 if and only if $\frac{1}{2}(n+10)(n-9)$ is divisible by 99, so $(n+10)(n-9)$ needs to be divisible by 9 and 11. Assume that $n+10$ is a multiple of 11. Writing out a few terms, $n=12, 23, 34, 45$, we see that $n=45$ is the smallest $n$ that works in this case. Next, assume that $n-9$ is a multiple of 11. Writing out a few terms, $n=20, 31, 42, 53$, we see that $n=53$ is the smallest $n$ that works in this case. The smallest $n$ is $\boxed{045}$.

Note that we can also construct the solution using CRT by assuming either $11$ divides $n+10$ and $9$ divides $n-9$, or $9$ divides $n+10$ and $11$ divides $n-9$, and taking the smaller solution.

Solution 2 $$a_n \equiv a_{n-1} + n \pmod {99}$$ By looking at the first few terms, we can see that $$a_n \equiv 10+11+12+ \dots + n \pmod {99}$$ This implies $$a_n \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99}$$ Since $a_n \equiv 0 \pmod {99}$, we can rewrite the equivalence, and simplify $$0 \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99}$$ $$0 \equiv n(n+1) - 90 \pmod {99}$$ $$0 \equiv 4n^2+4n+36 \pmod {99}$$ $$0 \equiv (2n+1)^2+35 \pmod {99}$$ $$64 \equiv (2n+1)^2 \pmod {99}$$ The only squares that are congruent to $64 \pmod {99}$ are $(\pm 8)^2$ and $(\pm 19)^2$, so $$2n+1 \equiv -8, 8, 19, \text{or } {-19} \pmod {99}$$ $2n+1 \equiv -8 \pmod {99}$ yields $n=45$ as the smallest integer solution. $2n+1 \equiv 8 \pmod {99}$ yields $n=53$ as the smallest integer solution. $2n+1 \equiv -19 \pmod {99}$ yields $n=89$ as the smallest integer solution. $2n+1 \equiv 19 \pmod {99}$ yields $n=9$ as the smallest integer solution. However, $n$ must be greater than $10$.

The smallest positive integer solution greater than $10$ is $n=\boxed{045}$.

Solution 3 $a_n=a_{n-1} + n \pmod{99}$. Using the steps of the previous solution we get up to $n^2+n \equiv 90 \pmod{99}$. This gives away the fact that $(n)(n+1) \equiv 0 \pmod{9} \implies n \equiv \{0, 8\} \pmod{9}$ so either $n$ or $n+1$ must be a multiple of 9.

Case 1 ( $n|9$): Say $n=9x$ and after simplification $x(9x+1) = 10 \pmod{90} \forall x \in \mathbb{Z}$.

Case 2: ( $n+1|9$): Say $n=9a-1$ and after simplification $(9a-1)(a) = 10 \pmod{90} \forall a \in \mathbb{Z}$.

As a result $a$ must be a divisor of $10$ and after doing some testing in both cases the smallest value that works is $x=5 \implies \boxed{045}$.

~First

Solution 4 (not good, risky)

We just notice that $100 \equiv 1 \pmod{99}$, so we are just trying to find $10 + 11 + 12 + \cdots + n$ modulo $99$, or $\dfrac{n(n+1)}{2} - 45$ modulo $99$. Also, the sum to $44$ is divisible by $99$, and is the first one that is. Thus, if we sum to $45$ the $45$ is cut off and thus is just a sum to $44$.

Without checking whether there are other sums congruent to $45 \pmod{99}$, we can just write the answer to be $\boxed{045}$.

Solution 5

Let $b_n = 2a_{n+10}$. We can find a formula for $b_n$: $b_n = (20+n)(n+1)$.

Notice that both can't have a factor of 3. Thus we can limit our search range of n to $n \equiv 7,8 \pmod{9}$. Testing values for n in our search range (like 7,8,16,17,25,26...), we get that 35 is the least n. But, don't write that down! Remember, $b_n = 2a_{n+10}$, so, the 35th term in b corresponds to the 45th term in a. Thus our answer is $\boxed{045}$

-AlexLikeMath

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 