https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=D1shs0ap&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T20:28:29ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_I_Problems/Problem_9&diff=888632017 AIME I Problems/Problem 92017-12-11T04:57:06Z<p>D1shs0ap: /* Solution 1 */</p>
<hr />
<div>==Problem 9==<br />
Let <math>a_{10} = 10</math>, and for each integer <math>n >10</math> let <math>a_n = 100a_{n - 1} + n</math>. Find the least <math>n > 10</math> such that <math>a_n</math> is a multiple of <math>99</math>.<br />
<br />
==Solution 1==<br />
Writing out the recursive statement for <math>a_n, a_{n-1}, \dots, a_{10}</math> and summing them gives <cmath>a_n+\dots+a_{10}=100(a_{n-1}+\dots+a_{10})+n+\dots+10</cmath><br />
Which simplifies to <cmath>a_n=99(a_{n-1}+\dots+a_{10})+\frac{1}{2}(n+10)(n-9)</cmath><br />
Therefore, <math>a_n</math> is divisible by 99 if and only if <math>\frac{1}{2}(n+10)(n-9)</math> is divisible by 99, so <math>(n+10)(n-9)</math> needs to be divisible by 9 and 11. Assume that <math>n+10</math> is a multiple of 11. Writing out a few terms, <math>n=12, 23, 34, 45</math>, we see that <math>n=45</math> is the smallest <math>n</math> that works in this case. Next, assume that <math>n-9</math> is a multiple of 11. Writing out a few terms, <math>n=20, 31, 42, 53</math>, we see that <math>n=53</math> is the smallest <math>n</math> that works in this case. The smallest <math>n</math> is <math>\boxed{045}</math>.<br />
<br />
Note that we can also construct the solution using CRT by assuming either <math>11</math> divides <math>n+10</math> and <math>9</math> divides <math>n-9</math>, or <math>9</math> divides <math>n+10</math> and <math>11</math> divides <math>n-9</math>, and taking the smaller solution.<br />
<br />
==Solution 2==<br />
<cmath>a_n \equiv a_{n-1} + n \pmod {99} </cmath><br />
By looking at the first few terms, we can see that <br />
<cmath>a_n \equiv 10+11+12+ \dots + n \pmod {99} </cmath><br />
This implies<br />
<cmath>a_n \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99} </cmath><br />
Since <math>a_n \equiv 0 \pmod {99}</math>, we can rewrite the equivalence, and simplify <br />
<cmath>0 \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99} </cmath><br />
<cmath>0 \equiv n(n+1) - 90 \pmod {99} </cmath><br />
<cmath>0 \equiv 4n^2+4n+36 \pmod {99} </cmath><br />
<cmath>0 \equiv (2n+1)^2+35 \pmod {99} </cmath><br />
<cmath>64 \equiv (2n+1)^2 \pmod {99} </cmath><br />
The only squares that are congruent to <math>64 \pmod {99}</math> are <math>(\pm 8)^2</math> and <math>(\pm 19)^2</math>, so <br />
<cmath>2n+1 \equiv -8, 8, 19, \text{or } {-19} \pmod {99}</cmath><br />
<math>2n+1 \equiv -8 \pmod {99}</math> yields <math>n=45</math> as the smallest integer solution.<br />
<br />
<math>2n+1 \equiv 8 \pmod {99}</math> yields <math>n=53</math> as the smallest integer solution.<br />
<br />
<math>2n+1 \equiv -19 \pmod {99}</math> yields <math>n=89</math> as the smallest integer solution.<br />
<br />
<math>2n+1 \equiv 19 \pmod {99}</math> yields <math>n=9</math> as the smallest integer solution. However, <math>n</math> must be greater than <math>10</math>.<br />
<br />
The smallest positive integer solution greater than <math>10</math> is <math>n=\boxed{045}</math>.<br />
<br />
==Solution 3==<br />
<math>a_n=a_{n-1} + n \pmod{99}</math>. Using the steps of the previous solution we get up to <math>n^2+n \equiv 90 \pmod{99}</math>. This gives away the fact that <math>(n)(n+1) \equiv 0 \pmod{9} \implies n \equiv \{0, 8\} \pmod{9}</math> so either <math>n</math> or <math>n+1</math> must be a multiple of 9. <br />
<br />
Case 1 (<math>n|9</math>): Say <math>n=9x</math> and after simplification <math>x(9x+1) = 10 \pmod{90} \forall x \in \mathbb{Z}</math>. <br />
<br />
Case 2: (<math>n+1|9</math>): Say <math>n=9a-1</math> and after simplification <math>(9a-1)(a) = 10 \pmod{90} \forall a \in \mathbb{Z}</math>.<br />
<br />
As a result <math>a</math> must be a divisor of <math>10</math> and after doing some testing in both cases the smallest value that works is <math>x=5 \implies \boxed{045}</math>.<br />
<br />
~First<br />
<br />
==See also==<br />
{{AIME box|year=2017|n=I|num-b=8|num-a=10}}<br />
{{MAA Notice}}</div>D1shs0aphttps://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_10&diff=846912016 AIME II Problems/Problem 102017-03-13T23:28:06Z<p>D1shs0ap: /* Solution 3 */</p>
<hr />
<div>Triangle <math>ABC</math> is inscribed in circle <math>\omega</math>. Points <math>P</math> and <math>Q</math> are on side <math>\overline{AB}</math> with <math>AP<AQ</math>. Rays <math>CP</math> and <math>CQ</math> meet <math>\omega</math> again at <math>S</math> and <math>T</math> (other than <math>C</math>), respectively. If <math>AP=4,PQ=3,QB=6,BT=5,</math> and <math>AS=7</math>, then <math>ST=\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
==Solution 1==<br />
<asy><br />
import cse5;<br />
pathpen = black; pointpen = black;<br />
pointfontsize = 9;<br />
size(8cm);<br />
<br />
pair A = origin, B = (13,0), P = (4,0), Q = (7,0),<br />
T = B + 5 dir(220), C = IP(circumcircle(A,B,T),Line(T,Q,-0.1,10)),<br />
S = IP(circumcircle(A,B,C),Line(C,P,-0.1,10));<br />
<br />
Drawing(A--B--C--cycle);<br />
D(circumcircle(A,B,C),rgb(0,0.6,1));<br />
DrawPathArray(C--S^^C--T,rgb(1,0.4,0.1));<br />
DrawPathArray(A--S^^B--T,rgb(0,0.4,0));<br />
D(S--T,rgb(1,0.2,0.4));<br />
<br />
D("A",A,dir(215));<br />
D("B",B,dir(330));<br />
D("P",P,dir(240));<br />
D("Q",Q,dir(240));<br />
D("T",T,dir(290));<br />
D("C",C,dir(120));<br />
D("S",S,dir(250));<br />
<br />
MP("4",(A+P)/2,dir(90));<br />
MP("3",(P+Q)/2,dir(90));<br />
MP("6",(Q+B)/2,dir(90));<br />
MP("5",(B+T)/2,dir(140));<br />
MP("7",(A+S)/2,dir(40));<br />
</asy><br />
Let <math>\angle ACP=\alpha</math>, <math>\angle PCQ=\beta</math>, and <math>\angle QCB=\gamma</math>. Note that since <math>\triangle ACQ\sim\triangle TBQ</math> we have <math>\tfrac{AC}{CQ}=\tfrac56</math>, so by the Ratio Lemma <cmath>\dfrac{AP}{PQ}=\dfrac{AC}{CQ}\cdot\dfrac{\sin\alpha}{\sin\beta}\quad\implies\quad \dfrac{\sin\alpha}{\sin\beta}=\dfrac{24}{15}.</cmath>Similarly, we can deduce <math>\tfrac{PC}{CB}=\tfrac47</math> and hence <math>\tfrac{\sin\beta}{\sin\gamma}=\tfrac{21}{24}</math>.<br />
<br />
Now Law of Sines on <math>\triangle ACS</math>, <math>\triangle SCT</math>, and <math>\triangle TCB</math> yields <cmath>\dfrac{AS}{\sin\alpha}=\dfrac{ST}{\sin\beta}=\dfrac{TB}{\sin\gamma}.</cmath>Hence <cmath>\dfrac{ST^2}{\sin^2\beta}=\dfrac{TB\cdot AS}{\sin\alpha\sin\gamma},</cmath>so <cmath>TS^2=TB\cdot AS\left(\dfrac{\sin\beta}{\sin\alpha}\dfrac{\sin\beta}{\sin\gamma}\right)=\dfrac{15\cdot 21}{24^2}\cdot 5\cdot 7=\dfrac{35^2}{8^2}.</cmath>Hence <math>ST=\tfrac{35}8</math> and the requested answer is <math>35+8=\boxed{43}</math>.<br />
<br />
Edit: Note that the finish is much simpler. Once you get, <math>\dfrac{AS}{\sin\alpha}=\dfrac{ST}{\sin\beta}</math>, so <math>ST=\dfrac{AS*\sin(\beta)}{\sin(\alpha)}=7*(15/24)=35/8</math>.<br />
<br />
==Solution 2==<br />
Projecting through <math>C</math> we have <cmath>\frac{3}{4}\times \frac{13}{6}=(A,Q;P,B)\stackrel{C}{=}(A,T;S,B)=\frac{ST}{7}\times \frac{13}{5}</cmath> which easily gives <math>ST=\frac{35}{8}\Longrightarrow 35+8=\boxed{43.}</math><br />
<br />
==Solution 3==<br />
By Ptolemy's Theorem applied to quadrilateral <math>ASTB</math>, we find<br />
<cmath>5\cdot 7+13\cdot ST=AT\cdot BS.</cmath><br />
Therefore, in order to find <math>ST</math>, it suffices to find <math>AT\cdot BS</math>. We do this using similar triangles, which can be found by using Power of a Point theorem.<br />
<br />
As <math>\triangle APS\sim \triangle CPB</math>, we find<br />
<cmath>\frac{4}{PC}=\frac{7}{BC}.</cmath><br />
Therefore, <math>\frac{BC}{PC}=\frac{7}{4}</math>.<br />
<br />
As <math>\triangle BQT\sim\triangle CQA</math>, we find<br />
<cmath>\frac{6}{CQ}=\frac{5}{AC}.</cmath><br />
Therefore, <math>\frac{AC}{CQ}=\frac{5}{6}</math>.<br />
<br />
As <math>\triangle ATQ\sim\triangle CBQ</math>, we find<br />
<cmath>\frac{AT}{BC}=\frac{7}{CQ}.</cmath><br />
Therefore, <math>AT=\frac{7\cdot BC}{CQ}</math>.<br />
<br />
As <math>\triangle BPS\sim \triangle CPA</math>, we find<br />
<cmath>\frac{9}{PC}=\frac{BS}{AC}.</cmath><br />
Therefore, <math>BS=\frac{9\cdot AC}{PC}</math>. Thus we find<br />
<cmath>AT\cdot BS=\left(\frac{7\cdot BC}{CQ}\right)\left(\frac{9\cdot AC}{PC}\right).</cmath><br />
But now we can substitute in our previously found values for <math>\frac{BC}{PC}</math> and <math>\frac{AC}{CQ}</math>, finding<br />
<cmath>AT\cdot BS=63\cdot \frac{7}{4}\cdot \frac{5}{6}=\frac{21\cdot 35}{8}.</cmath><br />
Substituting this into our original expression from Ptolemy's Theorem, we find<br />
<cmath>\begin{align*}35+13ST&=\frac{21\cdot 35}{8}\\13ST&=\frac{13\cdot 35}{8}\\ST&=\frac{35}{8}.\end{align*}</cmath><br />
Thus the answer is <math>\boxed{43}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2016|n=II|num-b=9|num-a=11}}<br />
{{MAA Notice}}</div>D1shs0ap