Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 7 (Bash Bash Bash))
m (→‎Solution 7 (Bash Bash Bash))
Line 90: Line 90:
 
We will work<math>\mod 99</math>. The recursive formula now becomes <math>a_n=a_{n-1}+n</math>. Now, we will bash. For convenience, everything is taken <math>\mod 99</math>. The sequence is
 
We will work<math>\mod 99</math>. The recursive formula now becomes <math>a_n=a_{n-1}+n</math>. Now, we will bash. For convenience, everything is taken <math>\mod 99</math>. The sequence is
 
<cmath>\begin{align*}a_{10}&=10 \\ a_{11}&=10+11=21 \\ a_{12}&=12+21=33 \\ a_{13}&=13+33=46 \\ a_{14}&=46+14=60 \\ a_{15}&=60+15=75 \\ a_{16}&=75+16=91 \\ a_{17}&=91+17=9 \\ a_{18}&=9+18=27 \\ a_{19}&=27+19=46 \\ a_{20}&=46+20=66 \\ a_{21}&=66+21=87 \\ a_{22}&=87+22=10 \\ a_{23}&=10+23=33 \\ a_{24}&=33+24=57 \\ a_{25}&=57+25=82 \\ a_{26}&=82+26=9 \\ a_{27}&=9+27=36 \\ a_{28}&=36+28=54 \\ a_{29}&=54+29=83 \\ a_{30}&=83+30=14 \\ a_{31}&=14+31=45 \\ a_{32}&=45+32=77 \\ a_{33}&=77+33=1 \\ a_{34}&=11+34=45 \\ a_{35}&=45+35=80 \\ a_{36}&=80+36=17 \\ a_{37}&=17+37=54 \\ a_{38}&=54+38=92 \\ a_{39}&=92+39=32 \\ a_{40}&=32+40=72 \\ a_{41}&=72+41=24 \\ a_{42}&=24+42=66 \\ a_{43}&=66+43=10 \\ a_{44}&=10+44=54 \\ a_{45}&=54+45=0.\end{align*}</cmath> Hence the least number <math>n</math> is <math>n=45</math>.
 
<cmath>\begin{align*}a_{10}&=10 \\ a_{11}&=10+11=21 \\ a_{12}&=12+21=33 \\ a_{13}&=13+33=46 \\ a_{14}&=46+14=60 \\ a_{15}&=60+15=75 \\ a_{16}&=75+16=91 \\ a_{17}&=91+17=9 \\ a_{18}&=9+18=27 \\ a_{19}&=27+19=46 \\ a_{20}&=46+20=66 \\ a_{21}&=66+21=87 \\ a_{22}&=87+22=10 \\ a_{23}&=10+23=33 \\ a_{24}&=33+24=57 \\ a_{25}&=57+25=82 \\ a_{26}&=82+26=9 \\ a_{27}&=9+27=36 \\ a_{28}&=36+28=54 \\ a_{29}&=54+29=83 \\ a_{30}&=83+30=14 \\ a_{31}&=14+31=45 \\ a_{32}&=45+32=77 \\ a_{33}&=77+33=1 \\ a_{34}&=11+34=45 \\ a_{35}&=45+35=80 \\ a_{36}&=80+36=17 \\ a_{37}&=17+37=54 \\ a_{38}&=54+38=92 \\ a_{39}&=92+39=32 \\ a_{40}&=32+40=72 \\ a_{41}&=72+41=24 \\ a_{42}&=24+42=66 \\ a_{43}&=66+43=10 \\ a_{44}&=10+44=54 \\ a_{45}&=54+45=0.\end{align*}</cmath> Hence the least number <math>n</math> is <math>n=45</math>.
−
 
−
Solution by pleaseletmetwin, but not added to the Wiki by pleaseletmetwin
 
−
 
−
-jackshi2006
 
−
(LaTeX by PureSwag and phoenixfire)
 
  
 
==See also==
 
==See also==

Revision as of 19:35, 16 March 2021

Problem 9

Let $a_{10} = 10$, and for each positive integer $n >10$ let $a_n = 100a_{n - 1} + n$. Find the least positive $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 ($9 \mid n$): Say $n=9x$ and after simplification $x(9x+1) = 10 \pmod{90} \forall x \in \mathbb{Z}$.

Case 2: ($9 \mid n+1$): 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

Solution 6 (bash, slower, but safer)

The first thing you should realize is that each term after the tenth is another two-digit number chained to the last number. $10, 1011, 101112, \dots$. Now the fact that the sequence starts at $10$ can be completely discarded for this solution. Just consider $a(10)$ then same as $a(1)$, and we can add nine to the answer at the end.


The second step is to split $99$ as $9$ and $11$ and solve for divisibility rules individually. Let's start with $11$ because it gives us the most information to continue.


In any number generated, if the numbers don't go beyond $20$, then the highest number we can get is $10111213141516171819$, with every odd digit being $1$. This is a little risky because we are assuming that it doesn't exceed $20$. If someone wanted to be absolutely sure they could continue, but this is unnecessary later and a big hassle. Anyways, now we write an equation to check for divisibility by $11$. The expression being $\frac{((n-1) + 0)\cdot n)}{2}-n$.

The concept here is to add $0$ to the $n-1^{th}$ term altogether, then subtract the number of ones in it, which is $n$. Simplify to $\frac{n(n-3)}{2}$ congruent to $0 \pmod{11}$. Now notice the divide by two can be discarded because one of $n$ or $(n-3)$ will be even. So if $n$ or $n-3$ is to be divisible by $11$, we can make a simple list.

\[n = 0, 3, 11, 14, 22, 25, 33, 36, 44, 47, \dots\]

Now we test each $n$ for divisibility by $9$. This is done by making a list that ultimately calculates the sum of every digit in the large number. $n(1)$ to $n(10)$ has the first digit $1$. $n(11)$ to $n(20)$ has the first digit $2$, and so on. The necessary thing to realize is that the sum of all digits $0-9$ is divisible by $9$, so we only have to solve for the sum of the first digits, and then the short list of second digits.

For example, let's test $n=25$.

So we know that $25$ include both $1-10$ and $11-20$, so that's $10 + 20$ right away. $21-25$ contains $5$ numbers that have the first digit $3$, so $+15$. Then we add $0-4$ together, which is $10$. $10+20+15+10=55$, which is not divisible by $9$, so it is not the answer.

Do this for just a minute you get that $36$ sums to $99$, a multiple of nine! So $n(36)$ is the answer, right? Don't forget we have to add $9$ because we translated $n(10)$ to $n(1)$ at the very beginning! Finally, after a short bash, we get $\boxed{045}$.

-jackshi2006 ($LaTeX$ by PureSwag)

Solution 7 (Bash Bash Bash)

We will work$\mod 99$. The recursive formula now becomes $a_n=a_{n-1}+n$. Now, we will bash. For convenience, everything is taken $\mod 99$. The sequence is \begin{align*}a_{10}&=10 \\ a_{11}&=10+11=21 \\ a_{12}&=12+21=33 \\ a_{13}&=13+33=46 \\ a_{14}&=46+14=60 \\ a_{15}&=60+15=75 \\ a_{16}&=75+16=91 \\ a_{17}&=91+17=9 \\ a_{18}&=9+18=27 \\ a_{19}&=27+19=46 \\ a_{20}&=46+20=66 \\ a_{21}&=66+21=87 \\ a_{22}&=87+22=10 \\ a_{23}&=10+23=33 \\ a_{24}&=33+24=57 \\ a_{25}&=57+25=82 \\ a_{26}&=82+26=9 \\ a_{27}&=9+27=36 \\ a_{28}&=36+28=54 \\ a_{29}&=54+29=83 \\ a_{30}&=83+30=14 \\ a_{31}&=14+31=45 \\ a_{32}&=45+32=77 \\ a_{33}&=77+33=1 \\ a_{34}&=11+34=45 \\ a_{35}&=45+35=80 \\ a_{36}&=80+36=17 \\ a_{37}&=17+37=54 \\ a_{38}&=54+38=92 \\ a_{39}&=92+39=32 \\ a_{40}&=32+40=72 \\ a_{41}&=72+41=24 \\ a_{42}&=24+42=66 \\ a_{43}&=66+43=10 \\ a_{44}&=10+44=54 \\ a_{45}&=54+45=0.\end{align*} Hence the least number $n$ is $n=45$.

See also

2017 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_I_Problems/Problem_9&oldid=149637"