https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Maxninga938&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T11:28:27ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_II_Problems/Problem_13&diff=1120742013 AIME II Problems/Problem 132019-11-23T04:01:48Z<p>Maxninga938: /* Solution 1 */</p>
<hr />
<div>==Problem 13==<br />
In <math>\triangle ABC</math>, <math>AC = BC</math>, and point <math>D</math> is on <math>\overline{BC}</math> so that <math>CD = 3\cdot BD</math>. Let <math>E</math> be the midpoint of <math>\overline{AD}</math>. Given that <math>CE = \sqrt{7}</math> and <math>BE = 3</math>, the area of <math>\triangle ABC</math> can be expressed in the form <math>m\sqrt{n}</math>, where <math>m</math> and <math>n</math> are positive integers and <math>n</math> is not divisible by the square of any prime. Find <math>m+n</math>.<br />
==Solutions==<br />
<br />
===Stewart's Solid Start===<br />
Draw a good diagram. This involves paper and ruler. We can set <math>AE=ED=m</math>. Set <math>BD=k</math>, therefore <math>CD=3k, AC=4k</math>. Thereafter, by Stewart's Theorem on <math>\triangle ACD</math> and cevian <math>CE</math>, we get <math>2m^2+14=25k^2</math>. Also apply Stewart's Theorem on <math>\triangle CEB</math> with cevian <math>DE</math>. After simplification, <math>2m^2=17-6k^2</math>. Therefore, <math>k=1, m=\frac{\sqrt{22}}{2}</math>. Finally, note that (using [] for area) <math>[CED]=[CAE]=3[EDB]=3[AEB]=\frac{3}{8}[ABC]</math>, because of base-ratios. Using Heron's Formula on <math>\triangle EDB</math>, as it is simplest, we see that <math>[ABC]=3\sqrt{7}</math>, so your answer is <math>10</math>. Every step was straightforward and by adopting the simplest steps, we solved the problem quickly.<br />
<br />
=== Solution 1 ===<br />
After drawing the figure, we suppose <math>BD=a</math>, so that <math>CD=3a</math>, <math>AC=4a</math>, and <math>AE=ED=b</math>.<br />
<br />
Using Law of Cosines for <math>\triangle AEC</math> and <math>\triangle CED</math>,we get<br />
<br />
<cmath>b^2+7-2\sqrt{7}\cdot \cos(\angle CED)=9a^2\qquad (1)</cmath><br />
<cmath>b^2+7+2\sqrt{7}\cdot \cos(\angle CED)=16a^2\qquad (2)</cmath><br />
So, <math>(1)+(2)</math>, we get<cmath>2b^2+14=25a^2. \qquad (3)</cmath><br />
<br />
Using Law of Cosines in <math>\triangle ACD</math>, we get<br />
<br />
<cmath>b^2+9a^2-2\cdot 2b\cdot 3a\cdot \cos(\angle ADC)=16a^2</cmath><br />
<br />
So, <cmath>\cos(\angle ADC)=\frac{7a^2-4b^2}{12ab}.\qquad (4)</cmath><br />
<br />
Using Law of Cosines in <math>\triangle EDC</math> and <math>\triangle EDB</math>, we get<br />
<br />
<cmath>b^2+9a^2-2\cdot 3a\cdot b\cdot \cos(\angle ADC)=7\qquad (5)</cmath><br />
<br />
<cmath>b^2+a^2+2\cdot a\cdot b\cdot \cos(\angle ADC)=9.\qquad (6)</cmath><br />
<br />
<math>(5)+(6)</math>, and according to <math>(4)</math>, we can get <br />
<cmath>37a^2+2b^2=48. \qquad (7)</cmath><br />
<br />
Using <math>(3)</math> and <math>(7)</math>, we can solve <math>a=1</math> and <math>b=\frac{\sqrt{22}}{2}</math>.<br />
<br />
Finally, we use Law of Cosines for <math>\triangle ADB</math>, <br />
<br />
<cmath>4(\frac{\sqrt{22}}{2})^2+1+2\cdot2(\frac{\sqrt{22}}{2})\cdot \cos(ADC)=AB^2</cmath><br />
<br />
then <math>AB=2\sqrt{7}</math>, so the height of this <math>\triangle ABC</math> is <math>\sqrt{4^2-(\sqrt{7})^2}=3</math>.<br />
<br />
Then the area of <math>\triangle ABC</math> is <math>3\sqrt{7}</math>, so the answer is <math>\boxed{010}</math>.<br />
<br />
=== Solution 2 ===<br />
Let <math>X</math> be the foot of the altitude from <math>C</math> with other points labelled as shown below.<br />
<asy><br />
size(200);<br />
pair A=(0,0),B=(2*sqrt(7),0),C=(sqrt(7),3),D=(3*B+C)/4,L=C/5,M=3*B/7;<br />
draw(A--B--C--cycle);draw(A--D^^B--L^^C--M);<br />
label("$A$",A,SW);label("$B$",B,SE);label("$C$",C,N);label("$D$",D,NE);label("$L$",L,NW);label("$M$",M,S);<br />
pair X=foot(C,A,B), Y=foot(L,A,B);<br />
pair EE=D/2;<br />
label("$X$",X,S);label("$E$",EE,NW);label("$Y$",Y,S);<br />
draw(C--X^^L--Y,dotted);<br />
draw(rightanglemark(B,X,C)^^rightanglemark(B,Y,L));<br />
</asy><br />
Now we proceed using [[mass points]]. To balance along the segment <math>BC</math>, we assign <math>B</math> a mass of <math>3</math> and <math>C</math> a mass of <math>1</math>. Therefore, <math>D</math> has a mass of <math>4</math>. As <math>E</math> is the midpoint of <math>AD</math>, we must assign <math>A</math> a mass of <math>4</math> as well. This gives <math>L</math> a mass of <math>5</math> and <math>M</math> a mass of <math>7</math>.<br />
<br />
Now let <math>AB=b</math> be the base of the triangle, and let <math>CX=h</math> be the height. Then as <math>AM:MB=3:4</math>, and as <math>AX=\frac{b}{2}</math>, we know that <cmath>MX=\frac{b}{2}-\frac{3b}{7}=\frac{b}{14}.</cmath> Also, as <math>CE:EM=7:1</math>, we know that <math>EM=\frac{1}{\sqrt{7}}</math>. Therefore, by the Pythagorean Theorem on <math>\triangle {XCM}</math>, we know that <cmath>\frac{b^2}{196}+h^2=\left(\sqrt{7}+\frac{1}{\sqrt{7}}\right)^2=\frac{64}{7}.</cmath><br />
<br />
Also, as <math>LE:BE=5:3</math>, we know that <math>BL=\frac{8}{5}\cdot 3=\frac{24}{5}</math>. Furthermore, as <math>\triangle YLA\sim \triangle XCA</math>, and as <math>AL:LC=1:4</math>, we know that <math>LY=\frac{h}{5}</math> and <math>AY=\frac{b}{10}</math>, so <math>YB=\frac{9b}{10}</math>. Therefore, by the Pythagorean Theorem on <math>\triangle BLY</math>, we get <cmath>\frac{81b^2}{100}+\frac{h^2}{25}=\frac{576}{25}.</cmath><br />
Solving this system of equations yields <math>b=2\sqrt{7}</math> and <math>h=3</math>. Therefore, the area of the triangle is <math>3\sqrt{7}</math>, giving us an answer of <math>\boxed{010}</math>.<br />
<br />
=== Solution 3 ===<br />
Let the coordinates of A, B and C be (-a, 0), (a, 0) and (0, h) respectively.<br />
Then <math>D = (\frac{3a}{4}, \frac{h}{4})</math> and <math>E = (-\frac{a}{8},\frac{h}{8}).</math> <br />
<math>EC^2 = 7</math> implies <math>a^2 + 49h^2 = 448</math>; <math>EB^2 = 9</math> implies <math>81a^2 + h^2 = 576.</math><br />
Solve this system of equations simultaneously, <math>a=\sqrt{7}</math> and <math>h=3</math>. <br />
Area of the triangle is ah = <math>3\sqrt{7}</math>, giving us an answer of <math>\boxed{010}</math>.<br />
<br />
===Solution 4===<br />
<asy><br />
size(200);<br />
pair A=(0,0),B=(2*sqrt(7),0),C=(sqrt(7),3),D=(3*B+C)/4,L=C/5,M=3*B/7;<br />
draw(A--B--C--cycle);draw(A--D^^B--L^^C--M);<br />
label("$A$",A,SW);label("$B$",B,SE);label("$C$",C,N);label("$D$",D,NE);label("$L$",L,NW);label("$M$",M,S);<br />
pair EE=D/2;<br />
label("$\sqrt{7}$", C--EE, W); label("$x$", D--B, E); label("$3x$", C--D, E); label("$l$", EE--D, N); label("$3$", EE--B, N);<br />
label("$E$",EE,NW);<br />
</asy><br />
(Thanks to writer of Solution 2)<br />
<br />
Let <math>BD = x</math>. Then <math>CD = 3x</math> and <math>AC = 4x</math>. Also, let <math>AE = ED = l</math>. Using Stewart's Theorem on <math>\bigtriangleup CEB</math> gives us the equation <math>(x)(3x)(4x) + (4x)(l^2) = 27x + 7x</math> or, after simplifying, <math>4l^2 = 34 - 12x^2</math>. We use Stewart's again on <math>\bigtriangleup CAD</math>: <math>(l)(l)(2l) + 7(2l) = (16x^2)(l) + (9x^2)(l)</math>, which becomes <math>2l^2 = 25x^2 - 14</math>. Substituting <math>2l^2 = 17 - 6x^2</math>, we see that <math>31x^2 = 31</math>, or <math>x = 1</math>. Then <math>l^2 = \frac{11}{2}</math>.<br />
<br />
We now use Law of Cosines on <math>\bigtriangleup CAD</math>. <math>(2l)^2 = (4x)^2 + (3x)^2 - 2(4x)(3x)\cos C</math>. Plugging in for <math>x</math> and <math>l</math>, <math>22 = 16 + 9 - 2(4)(3)\cos C</math>, so <math>\cos C = \frac{1}{8}</math>. Using the Pythagorean trig identity <math>\sin^2 + \cos^2 = 1</math>, <math>\sin^2 C = 1 - \frac{1}{64}</math>, so <math>\sin C = \frac{3\sqrt{7}}{8}</math>. <br />
<br />
<math>[ABC] = \frac{1}{2} AC \cdot BC \sin C = (\frac{1}{2})(4)(4)(\frac{3\sqrt{7}}{8}) = 3\sqrt{7}</math>, and our answer is <math>3 + 7 = \boxed{010}</math>.<br />
<br />
===Solution 5 (Barycentric Coordinates)===<br />
Let ABC be the reference triangle, with <math>A=(1,0,0)</math>, <math>B=(0,1,0)</math>, and <math>C=(0,0,1)</math>. We can easily calculate <math>D=(0,\frac{3}{4},\frac{1}{4})</math> and subsequently <math>E=(\frac{1}{2},\frac{3}{8},\frac{1}{8})</math>. Using distance formula on <math>\overline{EC}=(\frac{1}{2},\frac{3}{8},-\frac{7}{8})</math> and <math>\overline{EB}=(\frac{1}{2},-\frac{5}{8},\frac{1}{8})</math> gives <br />
<br />
<cmath><br />
\begin{align*}<br />
\begin{cases}<br />
7&=|EC|^2=-a^2 \cdot \frac{3}{8} \cdot (-\frac{7}{8})-b^2 \cdot \frac{1}{2} \cdot (-\frac{7}{8})-c^2 \cdot \frac{1}{2} \cdot \frac{3}{8} \\<br />
9&=|EB|^2=-a^2 \cdot (-\frac{5}{8}) \cdot \frac{1}{8}-b^2 \cdot \frac{1}{2} \cdot \frac{1}{8}-c^2 \cdot \frac{1}{2} \cdot (-\frac{5}{8}) \\<br />
\end{cases}<br />
\end{align*}<br />
</cmath><br />
<br />
But we know that <math>a=b</math>, so we can substitute and now we have two equations and two variables. So we can clear the denominators and prepare to cancel a variable:<br />
<br />
<cmath><br />
\begin{align*}<br />
\begin{cases}<br />
7\cdot 64&=3\cdot 7\cdot a^2+b^2\cdot 4\cdot 7-c^2\cdot 4\cdot 3\\<br />
9\cdot 64&=5a^2-4b^2+4\cdot 5\cdot c^2 \\<br />
\end{cases}<br />
\end{align*}<br />
</cmath><br />
<br />
<cmath><br />
\begin{align*}<br />
\begin{cases}<br />
7\cdot 64&=49a^2-12c^2 \\<br />
9\cdot 64&=a^2+20c^2 \\<br />
\end{cases}<br />
\end{align*}<br />
</cmath><br />
<br />
<cmath><br />
\begin{align*}<br />
\begin{cases}<br />
5\cdot 7\cdot 64&=245a^2-60c^2 \\<br />
3\cdot 9\cdot 64&=3a^2+60c^2 \\<br />
\end{cases}<br />
\end{align*}<br />
</cmath><br />
<br />
Then we add the equations to get<br />
<br />
<cmath><br />
\begin{align*}<br />
62\cdot 64&=248a^2 \\<br />
a^2 &=16 \\<br />
a &=4 \\<br />
\end{align*}<br />
</cmath><br />
<br />
Then plugging gives <math>b=4</math> and <math>c=2\sqrt{7}</math>. Then the height from <math>C</math> is <math>3</math>, and the area is <math>3\sqrt{7}</math> and our answer is <math>\boxed{010}</math>.<br />
<br />
===Solution 6 (Desperate for points)===<br />
<br />
Note that <math>\triangle BEC</math> uniquely determines <math>\triangle ABC</math>. Assume WTMLOG (without too much loss of generality) that <math>\angle BEC=90^\circ</math>. Then, the answer is <math>2\cdot \frac{1}{2}\cdot 3\cdot \sqrt{7}=3\sqrt{7}\rightarrow\boxed{010}</math>.<br />
<br />
==See Also==<br />
{{AIME box|year=2013|n=II|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Maxninga938https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_14&diff=1102412011 AIME II Problems/Problem 142019-10-12T01:56:08Z<p>Maxninga938: /* Solution 4( Better explanation of Solution 3) */</p>
<hr />
<div>==Problem 14==<br />
There are <math>N</math> [[permutation]]s <math>(a_{1}, a_{2}, ... , a_{30})</math> of <math>1, 2, \ldots, 30</math> such that for <math>m \in \left\{{2, 3, 5}\right\}</math>, <math>m</math> divides <math>a_{n+m} - a_{n}</math> for all integers <math>n</math> with <math>1 \leq n < n+m \leq 30</math>. Find the remainder when <math>N</math> is divided by <math>1000</math>.<br />
<br />
__TOC__<br />
==Solutions==<br />
===Solution 1===<br />
Be wary of "position" versus "number" in the solution!<br />
<br />
Each POSITION in the 30-position permutation is uniquely defined by an ordered triple <math>(i, j, k)</math>. The <math>n</math>th position is defined by this ordered triple where <math>i</math> is <math>n \mod 2</math>, <math>j</math> is <math>n \mod 3</math>, and <math>k</math> is <math>n \mod 5</math>. There are 2 choices for <math>i</math>, 3 for <math>j</math>, and 5 for <math>k</math>, yielding <math>2 \cdot 3 \cdot 5=30</math> possible triples. Because the least common multiple of 2, 3, and 5 is 30, none of these triples are repeated and all are used. By the conditions of the problem, if i is the same in two different triples, then the two numbers in these positions must be equivalent mod 2. If j is the same, then the two numbers must be equivalent <math>\mod 3</math>, and if <math>k</math> is the same, the two numbers must be equivalent mod 5. Take care to note that that doesn't mean that the number 1 has to have <math>1 \mod 2</math>! It's that the POSITION which NUMBER 1 occupies has <math>1 \mod 2</math>!<br />
<br />
The ordered triple (or position) in which 1 can be placed has 2 options for i, 3 for j, and 5 for k, resulting in 30 different positions of placement.<br />
<br />
The ordered triple where 2 can be placed in is somewhat constrained by the placement of 1. Because 1 is not equivalent to 2 in terms of mod 2, 3, or 5, the i, j, and k in their ordered triples must be different. Thus, for the number 2, there are (2-1) choices for i, (3-1) choices for j, and (5-1) choices for k. Thus, there are 1*2*4=8 possible placements for the number two once the number one is placed.<br />
<br />
Because 3 is equivalent to 1 mod 2, it must have the same i as the ordered triple of 1. Because 3 is not equivalent to 1 or 2 in terms of mod 3 or 5, it must have different j and k values. Thus, there is 1 choice for i, (2-1) choices for j, and (4-1) choices for k, for a total of <math>1\cdot 1 \cdot 3=3</math> choices for the placement of 3.<br />
<br />
As above, 4 is even, so it must have the same value of i as 2. It is also 1 mod 3, so it must have the same j value of 1. 4 is not equivalent to 1, 2, or 3 mod 5, so it must have a different k value than that of 1, 2, and 3. Thus, there is 1 choice for i, 1 choice for j, and (3-1) choices for k, yielding a total of <math>1 \cdot 1 \cdot 2=2</math> possible placements for 4.<br />
<br />
5 is odd and is equivalent to 2 mod 3, so it must have the same i value as 1 and the same j value of 2. 5 is not equivalent to 1, 2, 3, or 4 mod 5, so it must have a different k value from 1, 2, 3, and 4. However, 4 different values of k are held by these four numbers, so 5 must hold the one remaining value. Thus, only one possible triple is found for the placement of 5.<br />
<br />
All numbers from 6 to 30 are also fixed in this manner. All values of i, j, and k have been used, so every one of these numbers will have a unique triple for placement, as above with the number five. Thus, after 1, 2, 3, and 4 have been placed, the rest of the permutation is fixed. <br />
<br />
Thus, <math>N = 30 \cdot 8 \cdot 3 \cdot 2=30 \cdot 48=1440</math>. Thus, the remainder when <math>N</math> is divided by <math>1000</math> is <math>\boxed{440}.</math><br />
<br />
===Solution 2===<br />
We observe that the condition on the permutations means that two numbers with indices congruent <math>\mod m</math> are themselves congruent <math>\mod m</math> for <math>m \in \{ 2,3,5\}.</math> Furthermore, suppose that <math>a_n \equiv k \mod m.</math> Then, there are <math>30/m</math> indices congruent to <math>n \mod m,</math> and <math>30/m</math> numbers congruent to <math>k \mod m,</math> because 2, 3, and 5 are all factors of 30. Therefore, since every index congruent to <math>n</math> must contain a number congruent to <math>k,</math> and no number can appear twice in the permutation, only the indices congruent to <math>n</math> contain numbers congruent to <math>k.</math> In other words, <math>a_i \equiv a_j \mod m \iff i \equiv j \mod m.</math> But it is not necessary that <math>\textcolor{red}{(a_i\equiv i)\cup (a_j\equiv j)\mod m}</math>. In fact, if that were the case, there would only be one way to assign the indices, since <math>2,3,5</math> are relatively prime to each other and <math>30=\text{lcm}(2,3,5)</math>: <math>\{a_1,a_2,\dots a_{30}\}\in\{1,2,\dots 30\}\text{ }respectively</math>.<br />
<br />
This tells us that in a valid permutation, the congruence classes <math>\mod m</math> are simply swapped around, and if the set <math>S</math> is a congruence class <math>\mod m</math> for <math>m = </math> 2, 3, or 5, the set <math>\{ a_i \vert i \in S \}</math> is still a congruence class <math>\mod m.</math> Clearly, each valid permutation of the numbers 1 through 30 corresponds to exactly one permutation of the congruence classes modulo 2, 3, and 5. Also, if we choose some permutations of the congruence classes modulo 2, 3, and 5, they correspond to exactly one valid permutation of the numbers 1 through 30. This can be shown as follows: First of all, the choice of permutations of the congruence classes gives us every number in the permutation modulo 2, 3, and 5, so by the Chinese Remainder Theorem, it gives us every number <math>\mod 2\cdot 3\cdot 5 = 30.</math> Because the numbers must be between 1 and 30 inclusive, it thus uniquely determines what number goes in each index. Furthermore, two different indices cannot contain the same number. We will prove this by contradiction, calling the indices <math>a_i</math> and <math>a_j</math> for <math>i \neq j.</math> If <math>a_i=a_j,</math> then they must have the same residues modulo 2, 3, and 5, and so <math>i \equiv j</math> modulo 2, 3, and 5. Again using the Chinese Remainder Theorem, we conclude that <math>i \equiv j \mod 30,</math> so because <math>i</math> and <math>j</math> are both between 1 and 30 inclusive, <math>i = j,</math> giving us a contradiction. Therefore, every choice of permutations of the congruence classes modulo 2, 3, and 5 corresponds to exactly one valid permutation of the numbers 1 through 30.<br />
<br />
In other words, each set of assignment from <math>a_j\rightarrow j\mod (2,3,5)</math> determines a unique string of <math>30</math> numbers. For example:<br />
<br />
<math>\left[(0,1)\rightarrow (1,0)\right]\cap\left[(0,1,2)\rightarrow (0,2,1)\right]\cap\left[(0,1,2,3,4)\rightarrow (4,2,3,0,1)\right]</math>:<br />
<cmath>\begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}<br />
\hline<br />
2&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0&1&0\\ \hline<br />
3&0&2&1&0&2&1&0&2&1&0&2&1&0&2&1&0&2&1&0&2&1&0&2&1&0&2&1&0&2&1\\ \hline<br />
5&4&2&3&0&1&4&2&3&0&1&4&2&3&0&1&4&2&3&0&1&4&2&3&0&1&4&2&3&0&1\\ \hline\hline<br />
30&9&2&13&0&11&4&27&8&25&6&29&22&3&20&1&24&17&28&15&26&19&12&23&10&21&14&7&18&5&16\\ \hline<br />
\end{array} </cmath><br />
<br />
We have now established a bijection between valid permutations of the numbers 1 through 30 and permutations of the congruence classes modulo 2, 3, and 5, so <math>N</math> is equal to the number of permutations of congruence classes. There are always <math>m</math> congruence classes <math>\mod m,</math> so <math>N = 2! \cdot 3! \cdot 5! = 2 \cdot 6 \cdot 120 = 1440 \equiv \framebox[1.3\width]{440} \mod 1000.</math><br />
<br />
===Solution 3 (2-sec solve)===<br />
Note that <math>30=2\cdot 3\cdot 5</math>. Since <math>\gcd(2, 3, 5)=1</math>, by CRT, for each value <math>k=0\ldots 29</math> modulo <math>30</math> there exists a unique ordered triple of values <math>(a, b, c)</math> such that <math>k\equiv a\pmod{2}</math>, <math>k\equiv b\pmod{3}</math>, and <math>k\equiv c\pmod{5}</math>. Therefore, we can independently assign the residues modulo <math>2, 3, 5</math>, so <math>N=2!\cdot 3!\cdot 5!=1440</math>, and the answer is <math>\boxed{440}</math>.<br />
<br />
-TheUltimate123<br />
<br />
===Solution 4( Better explanation of Solution 3) ===<br />
First let's look at the situation when <math>m</math> is equal to 2. It isn't too difficult to see the given conditions are satisfied iff the sequences <math>S_1 = a_1,a_3,a_5,a_7...</math> and <math>S_2 =a_2,a_4,a_6...</math> each are assigned either <math>\equiv 0 \pmod 2</math> or <math>\equiv 1 \pmod 2</math>. Another way to say this is each element in the sequence <math>a_1,a_3,a_5,a_7...</math> would be the same mod 2, and similarly for the other sequence. There are 2! = 2 ways to assign the mods to the sequences.<br />
<br />
Now when <math>m</math> is equal to 3, the sequences are <math>T_1 = a_1, a_4,a_7..</math>, <math>T_2 = a_2,a_5,a_8,a_11...</math>, and <math>T_3 = a_3,a_6,a_9...</math>. Again, for each sequence, all of its elements are congruent either 0,1, or 2 mod 3. There are 3! = 6 ways to assign the mods to the sequences.<br />
<br />
Finally do the same thing for m = 5. There are 5! ways. In total there are 2 * 6*120 = 1440 and the answer is <math>\boxed{440}</math>.<br />
<br />
Why does this method work? Its due to CRT.<br />
<br />
-MathLegend27<br />
<br />
Note: the explanation is not complete without mentioning that 2*3*5 = 30, therefore CRT guarantees there is only 1 permutation for every combination of mod selections. If the problem asked for permutations of <math>{1,2,...,60}</math>, the answer would have been <math>2!3!5!2!2!2!</math>. <br />
<br />
-Mathdummy<br />
<br />
==See also==<br />
{{AIME box | year = 2011 | n = II | num-b=13 | num-a=15}}<br />
<br />
[[Category:Intermediate Combinatorics Problems]]<br />
{{MAA Notice}}</div>Maxninga938https://artofproblemsolving.com/wiki/index.php?title=1996_AHSME_Problems/Problem_25&diff=1073301996 AHSME Problems/Problem 252019-07-04T04:04:56Z<p>Maxninga938: /* Solution 2B (Slightly less computation) */</p>
<hr />
<div>==Problem==<br />
<br />
Given that <math>x^2 + y^2 = 14x + 6y + 6</math>, what is the largest possible value that <math>3x + 4y</math> can have? <br />
<br />
<math> \text{(A)}\ 72\qquad\text{(B)}\ 73\qquad\text{(C)}\ 74\qquad\text{(D)}\ 75\qquad\text{(E)}\ 76 </math><br />
<br />
==Solution 1==<br />
Complete the square to get <br />
<cmath>(x-7)^2 + (y-3)^2 = 64.</cmath><br />
Applying Cauchy-Schwarz directly,<br />
<cmath>64*25=(3^2+4^2)((x-7)^2 + (y-3)^2) \ge (3(x-7)+4(y-3))^2.</cmath><br />
<cmath> 40 \ge 3x+4y-33 </cmath><br />
<cmath>3x+4y \le 73.</cmath><br />
Thus our answer is <math>\boxed{(B)}</math>.<br />
<br />
==Solution 2 (Geometric)==<br />
<br />
The first equation is a [[circle]], so we find its center and [[radius]] by [[completing the square]]: <br />
<math>x^2 - 14x + y^2 - 6y = 6</math>, so <cmath>(x-7)^2 + (y-3)^2 = (x^2- 14x + 49) + (y^2 - 6y + 9) = 6 + 49 + 9 = 64.</cmath><br />
<br />
So we have a circle centered at <math>(7,3)</math> with radius <math>8</math>, and we want to find the max of <math>3x + 4y</math>.<br />
<br />
The set of lines <math>3x + 4y = A</math> are all [[parallel]], with slope <math>-\frac{3}{4}</math>. Increasing <math>A</math> shifts the lines up and/or to the right.<br />
<br />
We want to shift this line up high enough that it's [[tangent (geometry)|tangent]] to the circle, but not so high that it misses the circle altogether. This means <math>3x + 4y = A</math> will be tangent to the circle.<br />
<br />
Imagine that this line hits the circle at point <math>(a,b)</math>. The [[slope]] of the radius connecting the center of the circle, <math>(7,3)</math>, to tangent point <math>(a,b)</math> will be <math>\frac{4}{3}</math>, since the radius is perpendicular to the tangent line.<br />
<br />
So we have a point, <math>(7,3)</math>, and a slope of <math>\frac{4}{3}</math> that represents the slope of the radius to the tangent point. Let's start at the point <math>(7,3)</math>. If we go <math>4k</math> units up and <math>3k</math> units right from <math>(7,3)</math>, we would arrive at a point that's <math>5k</math> units away. But in reality we want <math>5k = 8</math> to reach the tangent point, since the radius of the circle is <math>8</math>.<br />
<br />
Thus, <math>k = \frac{8}{5}</math>, and we want to travel <math>4\cdot \frac{8}{5}</math> up and <math>3\cdot \frac{8}{5}</math> over from the point <math>(7,3)</math> to reach our maximum. This means the maximum value of <math>3x + 4y</math> occurs at <math>\left(7 +3\cdot \frac{8}{5}, 3 + 4\cdot \frac{8}{5}\right)</math>, which is <math>\left(\frac{59}{5}, \frac{47}{5}\right).</math><br />
<br />
Plug in those values for <math>x</math> and <math>y</math>, and you get the maximum value of <math>3x + 4y = 3\cdot\frac{59}{5} + 4\cdot\frac{47}{5} = \boxed{73}</math>, which is option <math>\boxed{(B)}</math>.<br />
==Solution 2B==<br />
Let the tangent point be <math>P</math>, and the tangent line's x-intercept be <math>Q</math>. Consider the horizontal line starting from center of circle (O) meeting the tangent line at K. Now triangle <math>OPK</math> is 3-4-5, <math>OP=8</math>, so <math>OK = \frac{5}{3}*8 = \frac{40}{3}</math>. Note that the horizontal distance from <math>O</math> to the origin is <math>7</math>, and the horizontal distance from K to Q is 4, (<math>\frac{4}{3}</math> of its y coordinate), so the x-intercept is <math>7+4+OK = 73/3</math>. The value of <math>3x+4y</math> is 73 at point <math>Q</math>. Note that this value is constant on the tangent line, so there is no need to calculate the coordinate of <math>P</math>. <math>\boxed{(B)}</math>.<br />
<br />
==Solution 3==<br />
<br />
Let <math>z = 3x + 4y</math>. Solving for <math>y</math>, we get <math>y = (z - 3x)/4</math>. Substituting into the given equation, we get<br />
<cmath>x^2 + \left( \frac{z - 3x}{4} \right)^2 = 14x + 6 \cdot \frac{z - 3x}{4} + 6,</cmath><br />
which simplifies to<br />
<cmath>25x^2 - (6z + 152)x + (z^2 - 24z - 96) = 0.</cmath><br />
<br />
This quadratic equation has real roots in <math>x</math> if and only if its discriminant is nonnegative, so<br />
<cmath>(6z + 152)^2 - 4 \cdot 25 \cdot (z^2 - 24z - 96) \ge 0,</cmath><br />
which simplifies to<br />
<cmath>-64z^2 + 4224z + 32704 \ge 0,</cmath><br />
which can be factored as<br />
<cmath>-64(z + 7)(z - 73) \ge 0.</cmath><br />
The largest value of <math>z</math> that satisfies this inequality is <math>\boxed{73}</math>, which is <math>\boxed{(B)}</math>.<br />
<br />
<br />
==Solution 4 (Using Answer Choice + Calculus)==<br />
Implicitly differentiating the given equation with respect to <math>x</math> yields:<br />
<br />
<math>2x + 2y\frac{dy}{dx} = 14 + 6\frac{dy}{dx}</math><br />
<br />
Now solve for <math>\frac{dy}{dx}</math> to obtain:<br />
<br />
<math>\frac{dy}{dx} = -\frac{x - 7}{y - 3}</math><br />
<br />
Set the equation equal to zero to find the maximum occurs at <math>x = 7</math><br />
<br />
Plug this back into the equation that we are trying to maximize and see that we are left with: <br />
<math>21 + 4y</math>.<br />
<br />
The only answer choice that can be obtained from this equation is <math>\bf{73}</math><br />
<br />
==See also==<br />
{{AHSME box|year=1996|num-b=24|num-a=26}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
[[Category:Introductory Algebra Problems]]<br />
<br />
[[Category:Circle Problems]]<br />
{{MAA Notice}}<br />
<math>aopsswag</math></div>Maxninga938https://artofproblemsolving.com/wiki/index.php?title=2000_AIME_I_Problems/Problem_14&diff=1068372000 AIME I Problems/Problem 142019-06-22T21:35:00Z<p>Maxninga938: /* Solution 3 */</p>
<hr />
<div>== Problem ==<br />
In triangle <math>ABC,</math> it is given that angles <math>B</math> and <math>C</math> are [[congruent (geometry)|congruent]]. Points <math>P</math> and <math>Q</math> lie on <math>\overline{AC}</math> and <math>\overline{AB},</math> respectively, so that <math>AP = PQ = QB = BC.</math> Angle <math>ACB</math> is <math>r</math> times as large as angle <math>APQ,</math> where <math>r</math> is a positive real number. Find the greatest integer that does not exceed <math>1000r</math>.<br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
<center><asy>defaultpen(fontsize(8)); size(200); pair A=20*dir(80)+20*dir(60)+20*dir(100), B=(0,0), C=20*dir(0), P=20*dir(80)+20*dir(60), Q=20*dir(80), R=20*dir(60); draw(A--B--C--A);draw(P--Q);draw(A--R--B);draw(P--R);D(R--C,dashed); label("\(A\)",A,(0,1));label("\(B\)",B,(-1,-1));label("\(C\)",C,(1,-1));label("\(P\)",P,(1,1)); label("\(Q\)",Q,(-1,1));label("\(R\)",R,(1,0));<br />
</asy></center> <br />
Let point <math>R</math> be in <math>\triangle ABC</math> such that <math>QB = BR = RP</math>. Then <math>PQBR</math> is a [[rhombus]], so <math>AB \parallel PR</math> and <math>APRB</math> is an [[isosceles trapezoid]]. Since <math>\overline{PB}</math> bisects <math>\angle QBR</math>, it follows by symmetry in trapezoid <math>APRB</math> that <math>\overline{RA}</math> bisects <math>\angle BAC</math>. Thus <math>R</math> lies on the perpendicular bisector of <math>\overline{BC}</math>, and <math>BC = BR = RC</math>. Hence <math>\triangle BCR</math> is an [[equilateral triangle]].<br />
<br />
Now <math>\angle ABR = \angle BAC = \angle ACR</math>, and the sum of the angles in <math>\triangle ABC</math> is <math>\angle ABR + 60^{\circ} + \angle BAC + \angle ACR + 60^{\circ} = 3\angle BAC + 120^{\circ} = 180^{\circ} \Longrightarrow \angle BAC = 20^{\circ}</math>. Then <math>\angle APQ = 140^{\circ}</math> and <math>\angle ACB = 80^{\circ}</math>, so the answer is <math>\left\lfloor 1000 \cdot \frac{80}{140} \right\rfloor = \left\lfloor \frac{4000}{7} \right\rfloor = \boxed{571}</math>.<br />
<br />
=== Solution 2 ===<br />
<center><asy>defaultpen(fontsize(8)); size(200); pair A=20*dir(80)+20*dir(60)+20*dir(100), B=(0,0), C=20*dir(0), P=20*dir(80)+20*dir(60), Q=20*dir(80), R=20*dir(60), S; S=intersectionpoint(Q--C,P--B); draw(A--B--C--A);draw(B--P--Q--C--R--Q);draw(A--R--B);draw(P--R--S); label("\(A\)",A,(0,1));label("\(B\)",B,(-1,-1));label("\(C\)",C,(1,-1));label("\(P\)",P,(1,1)); label("\(Q\)",Q,(-1,1));label("\(R\)",R,(1,0));label("\(S\)",S,(-1,0));<br />
</asy></center><br />
Again, construct <math>R</math> as above.<br />
<br />
Let <math>\angle BAC = \angle QBR = \angle QPR = 2x</math> and <math>\angle ABC = \angle ACB = y</math>, which means <math>x + y = 90</math>. <br />
<math>\triangle QBC</math> is isosceles with <math>QB = BC</math>, so <math>\angle BCQ = 90 - \frac {y}{2}</math>.<br />
Let <math>S</math> be the intersection of <math>QC</math> and <math>BP</math>. Since <math>\angle BCQ = \angle BQC = \angle BRS</math>, <math>BCRS</math> is [[cyclic quadrilateral|cyclic]], which means <math>\angle RBS = \angle RCS = x</math>.<br />
Since <math>APRB</math> is an isosceles trapezoid, <math>BP = AR</math>, but since <math>AR</math> bisects <math>\angle BAC</math>, <math>\angle ABR = \angle ACR = 2x</math>. <br />
<br />
Therefore we have that <math>\angle ACB = \angle ACR + \angle RCS + \angle QCB = 2x + x + 90 - \frac {y}{2} = y</math>.<br />
We solve the simultaneous equations <math>x + y = 90</math> and <math>2x + x + 90 - \frac {y}{2} = y</math> to get <math>x = 10</math> and <math>y = 80</math>.<br />
<math>\angle APQ = 180 - 4x = 140</math>, <math>\angle ACB = 80</math>, so <math>r = \frac {80}{140} = \frac {4}{7}</math>. <br />
<math>\left\lfloor 1000\left(\frac {4}{7}\right)\right\rfloor = \boxed{571}</math>.<br />
<br />
=== Solution 3 ===<br />
<br />
Let the measure of <math>\angle BAC</math> be <math>\alpha</math> and <math>\overline{AP}=\overline{PQ}=\overline{QB}=\overline{BC}=x</math>. Because <math>\triangle APQ</math> is isosceles, <math>AQ=2x\cos(\alpha)</math>. So, <math>\overline{AB}=x\left(2\cos(\alpha)+1\right)</math>. <math>\triangle{ABC}</math> is isosceles too, so <math>x=\overline{BC}=2\overline{AC}\sin\left(\frac{\alpha}{2}\right)=2x\left(2\cos(\alpha)+1\right)\sin\left(\frac{\alpha}{2}\right)</math>.<br />
Simplifying, <math>1=4\cos(\alpha)\sin\left(\frac{\alpha}{2}\right)+2sin\left(\frac{\alpha}{2}\right)</math>. By double angle formula, we know that <math>\cos(\alpha)=1-2\sin^2\left(\frac{\alpha}{2}\right)</math>.<br />
Applying, <math>4\sin\left(\frac{\alpha}{2}\right)-8\sin^3\left(\frac{\alpha}{2}\right)+2\sin\left(\frac{\alpha}{2}\right)=1</math> and <math>2\left(3\sin\left(\frac{\alpha}{2}\right)-4\sin^3\left(\frac{\alpha}{2}\right)\right)=1</math>.<br />
The expression in the parentheses though is triple angle formula! Hence, <math>\sin\left(\frac{3\alpha}{2}\right)=\frac{1}{2}</math>, <math>\alpha=20^o</math>. It follows now that <math>\angle APQ=140^o</math>, <math>\angle ACB=80^o</math>. Giving <math>r=\frac{4}{7}</math>.<br />
<math>\left\lfloor 1000\left(\frac {4}{7}\right)\right\rfloor = \boxed{571}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2000|n=I|num-b=13|num-a=15|t=721509}}<br />
<br />
[[Category:Intermediate Geometry Problems]]<br />
{{MAA Notice}}</div>Maxninga938https://artofproblemsolving.com/wiki/index.php?title=2000_AIME_I_Problems/Problem_14&diff=1068362000 AIME I Problems/Problem 142019-06-22T21:34:40Z<p>Maxninga938: /* Solution 3/Three/Tres */</p>
<hr />
<div>== Problem ==<br />
In triangle <math>ABC,</math> it is given that angles <math>B</math> and <math>C</math> are [[congruent (geometry)|congruent]]. Points <math>P</math> and <math>Q</math> lie on <math>\overline{AC}</math> and <math>\overline{AB},</math> respectively, so that <math>AP = PQ = QB = BC.</math> Angle <math>ACB</math> is <math>r</math> times as large as angle <math>APQ,</math> where <math>r</math> is a positive real number. Find the greatest integer that does not exceed <math>1000r</math>.<br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
<center><asy>defaultpen(fontsize(8)); size(200); pair A=20*dir(80)+20*dir(60)+20*dir(100), B=(0,0), C=20*dir(0), P=20*dir(80)+20*dir(60), Q=20*dir(80), R=20*dir(60); draw(A--B--C--A);draw(P--Q);draw(A--R--B);draw(P--R);D(R--C,dashed); label("\(A\)",A,(0,1));label("\(B\)",B,(-1,-1));label("\(C\)",C,(1,-1));label("\(P\)",P,(1,1)); label("\(Q\)",Q,(-1,1));label("\(R\)",R,(1,0));<br />
</asy></center> <br />
Let point <math>R</math> be in <math>\triangle ABC</math> such that <math>QB = BR = RP</math>. Then <math>PQBR</math> is a [[rhombus]], so <math>AB \parallel PR</math> and <math>APRB</math> is an [[isosceles trapezoid]]. Since <math>\overline{PB}</math> bisects <math>\angle QBR</math>, it follows by symmetry in trapezoid <math>APRB</math> that <math>\overline{RA}</math> bisects <math>\angle BAC</math>. Thus <math>R</math> lies on the perpendicular bisector of <math>\overline{BC}</math>, and <math>BC = BR = RC</math>. Hence <math>\triangle BCR</math> is an [[equilateral triangle]].<br />
<br />
Now <math>\angle ABR = \angle BAC = \angle ACR</math>, and the sum of the angles in <math>\triangle ABC</math> is <math>\angle ABR + 60^{\circ} + \angle BAC + \angle ACR + 60^{\circ} = 3\angle BAC + 120^{\circ} = 180^{\circ} \Longrightarrow \angle BAC = 20^{\circ}</math>. Then <math>\angle APQ = 140^{\circ}</math> and <math>\angle ACB = 80^{\circ}</math>, so the answer is <math>\left\lfloor 1000 \cdot \frac{80}{140} \right\rfloor = \left\lfloor \frac{4000}{7} \right\rfloor = \boxed{571}</math>.<br />
<br />
=== Solution 2 ===<br />
<center><asy>defaultpen(fontsize(8)); size(200); pair A=20*dir(80)+20*dir(60)+20*dir(100), B=(0,0), C=20*dir(0), P=20*dir(80)+20*dir(60), Q=20*dir(80), R=20*dir(60), S; S=intersectionpoint(Q--C,P--B); draw(A--B--C--A);draw(B--P--Q--C--R--Q);draw(A--R--B);draw(P--R--S); label("\(A\)",A,(0,1));label("\(B\)",B,(-1,-1));label("\(C\)",C,(1,-1));label("\(P\)",P,(1,1)); label("\(Q\)",Q,(-1,1));label("\(R\)",R,(1,0));label("\(S\)",S,(-1,0));<br />
</asy></center><br />
Again, construct <math>R</math> as above.<br />
<br />
Let <math>\angle BAC = \angle QBR = \angle QPR = 2x</math> and <math>\angle ABC = \angle ACB = y</math>, which means <math>x + y = 90</math>. <br />
<math>\triangle QBC</math> is isosceles with <math>QB = BC</math>, so <math>\angle BCQ = 90 - \frac {y}{2}</math>.<br />
Let <math>S</math> be the intersection of <math>QC</math> and <math>BP</math>. Since <math>\angle BCQ = \angle BQC = \angle BRS</math>, <math>BCRS</math> is [[cyclic quadrilateral|cyclic]], which means <math>\angle RBS = \angle RCS = x</math>.<br />
Since <math>APRB</math> is an isosceles trapezoid, <math>BP = AR</math>, but since <math>AR</math> bisects <math>\angle BAC</math>, <math>\angle ABR = \angle ACR = 2x</math>. <br />
<br />
Therefore we have that <math>\angle ACB = \angle ACR + \angle RCS + \angle QCB = 2x + x + 90 - \frac {y}{2} = y</math>.<br />
We solve the simultaneous equations <math>x + y = 90</math> and <math>2x + x + 90 - \frac {y}{2} = y</math> to get <math>x = 10</math> and <math>y = 80</math>.<br />
<math>\angle APQ = 180 - 4x = 140</math>, <math>\angle ACB = 80</math>, so <math>r = \frac {80}{140} = \frac {4}{7}</math>. <br />
<math>\left\lfloor 1000\left(\frac {4}{7}\right)\right\rfloor = \boxed{571}</math>.<br />
<br />
=== Solution 3/Three/Tres ===<br />
<br />
Let the measure of <math>\angle BAC</math> be <math>\alpha</math> and <math>\overline{AP}=\overline{PQ}=\overline{QB}=\overline{BC}=x</math>. Because <math>\triangle APQ</math> is isosceles, <math>AQ=2x\cos(\alpha)</math>. So, <math>\overline{AB}=x\left(2\cos(\alpha)+1\right)</math>. <math>\triangle{ABC}</math> is isosceles too, so <math>x=\overline{BC}=2\overline{AC}\sin\left(\frac{\alpha}{2}\right)=2x\left(2\cos(\alpha)+1\right)\sin\left(\frac{\alpha}{2}\right)</math>.<br />
Simplifying, <math>1=4\cos(\alpha)\sin\left(\frac{\alpha}{2}\right)+2sin\left(\frac{\alpha}{2}\right)</math>. By double angle formula, we know that <math>\cos(\alpha)=1-2\sin^2\left(\frac{\alpha}{2}\right)</math>.<br />
Applying, <math>4\sin\left(\frac{\alpha}{2}\right)-8\sin^3\left(\frac{\alpha}{2}\right)+2\sin\left(\frac{\alpha}{2}\right)=1</math> and <math>2\left(3\sin\left(\frac{\alpha}{2}\right)-4\sin^3\left(\frac{\alpha}{2}\right)\right)=1</math>.<br />
The expression in the parentheses though is triple angle formula! Hence, <math>\sin\left(\frac{3\alpha}{2}\right)=\frac{1}{2}</math>, <math>\alpha=20^o</math>. It follows now that <math>\angle APQ=140^o</math>, <math>\angle ACB=80^o</math>. Giving <math>r=\frac{4}{7}</math>.<br />
<math>\left\lfloor 1000\left(\frac {4}{7}\right)\right\rfloor = \boxed{571}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2000|n=I|num-b=13|num-a=15|t=721509}}<br />
<br />
[[Category:Intermediate Geometry Problems]]<br />
{{MAA Notice}}</div>Maxninga938https://artofproblemsolving.com/wiki/index.php?title=2000_AIME_I_Problems/Problem_14&diff=1068352000 AIME I Problems/Problem 142019-06-22T21:33:37Z<p>Maxninga938: /* Solution Three */</p>
<hr />
<div>== Problem ==<br />
In triangle <math>ABC,</math> it is given that angles <math>B</math> and <math>C</math> are [[congruent (geometry)|congruent]]. Points <math>P</math> and <math>Q</math> lie on <math>\overline{AC}</math> and <math>\overline{AB},</math> respectively, so that <math>AP = PQ = QB = BC.</math> Angle <math>ACB</math> is <math>r</math> times as large as angle <math>APQ,</math> where <math>r</math> is a positive real number. Find the greatest integer that does not exceed <math>1000r</math>.<br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
<center><asy>defaultpen(fontsize(8)); size(200); pair A=20*dir(80)+20*dir(60)+20*dir(100), B=(0,0), C=20*dir(0), P=20*dir(80)+20*dir(60), Q=20*dir(80), R=20*dir(60); draw(A--B--C--A);draw(P--Q);draw(A--R--B);draw(P--R);D(R--C,dashed); label("\(A\)",A,(0,1));label("\(B\)",B,(-1,-1));label("\(C\)",C,(1,-1));label("\(P\)",P,(1,1)); label("\(Q\)",Q,(-1,1));label("\(R\)",R,(1,0));<br />
</asy></center> <br />
Let point <math>R</math> be in <math>\triangle ABC</math> such that <math>QB = BR = RP</math>. Then <math>PQBR</math> is a [[rhombus]], so <math>AB \parallel PR</math> and <math>APRB</math> is an [[isosceles trapezoid]]. Since <math>\overline{PB}</math> bisects <math>\angle QBR</math>, it follows by symmetry in trapezoid <math>APRB</math> that <math>\overline{RA}</math> bisects <math>\angle BAC</math>. Thus <math>R</math> lies on the perpendicular bisector of <math>\overline{BC}</math>, and <math>BC = BR = RC</math>. Hence <math>\triangle BCR</math> is an [[equilateral triangle]].<br />
<br />
Now <math>\angle ABR = \angle BAC = \angle ACR</math>, and the sum of the angles in <math>\triangle ABC</math> is <math>\angle ABR + 60^{\circ} + \angle BAC + \angle ACR + 60^{\circ} = 3\angle BAC + 120^{\circ} = 180^{\circ} \Longrightarrow \angle BAC = 20^{\circ}</math>. Then <math>\angle APQ = 140^{\circ}</math> and <math>\angle ACB = 80^{\circ}</math>, so the answer is <math>\left\lfloor 1000 \cdot \frac{80}{140} \right\rfloor = \left\lfloor \frac{4000}{7} \right\rfloor = \boxed{571}</math>.<br />
<br />
=== Solution 2 ===<br />
<center><asy>defaultpen(fontsize(8)); size(200); pair A=20*dir(80)+20*dir(60)+20*dir(100), B=(0,0), C=20*dir(0), P=20*dir(80)+20*dir(60), Q=20*dir(80), R=20*dir(60), S; S=intersectionpoint(Q--C,P--B); draw(A--B--C--A);draw(B--P--Q--C--R--Q);draw(A--R--B);draw(P--R--S); label("\(A\)",A,(0,1));label("\(B\)",B,(-1,-1));label("\(C\)",C,(1,-1));label("\(P\)",P,(1,1)); label("\(Q\)",Q,(-1,1));label("\(R\)",R,(1,0));label("\(S\)",S,(-1,0));<br />
</asy></center><br />
Again, construct <math>R</math> as above.<br />
<br />
Let <math>\angle BAC = \angle QBR = \angle QPR = 2x</math> and <math>\angle ABC = \angle ACB = y</math>, which means <math>x + y = 90</math>. <br />
<math>\triangle QBC</math> is isosceles with <math>QB = BC</math>, so <math>\angle BCQ = 90 - \frac {y}{2}</math>.<br />
Let <math>S</math> be the intersection of <math>QC</math> and <math>BP</math>. Since <math>\angle BCQ = \angle BQC = \angle BRS</math>, <math>BCRS</math> is [[cyclic quadrilateral|cyclic]], which means <math>\angle RBS = \angle RCS = x</math>.<br />
Since <math>APRB</math> is an isosceles trapezoid, <math>BP = AR</math>, but since <math>AR</math> bisects <math>\angle BAC</math>, <math>\angle ABR = \angle ACR = 2x</math>. <br />
<br />
Therefore we have that <math>\angle ACB = \angle ACR + \angle RCS + \angle QCB = 2x + x + 90 - \frac {y}{2} = y</math>.<br />
We solve the simultaneous equations <math>x + y = 90</math> and <math>2x + x + 90 - \frac {y}{2} = y</math> to get <math>x = 10</math> and <math>y = 80</math>.<br />
<math>\angle APQ = 180 - 4x = 140</math>, <math>\angle ACB = 80</math>, so <math>r = \frac {80}{140} = \frac {4}{7}</math>. <br />
<math>\left\lfloor 1000\left(\frac {4}{7}\right)\right\rfloor = \boxed{571}</math>.<br />
<br />
=== Solution Three ===<br />
<br />
Let the measure of <math>\angle BAC</math> be <math>\alpha</math> and <math>\overline{AP}=\overline{PQ}=\overline{QB}=\overline{BC}=x</math>. Because <math>\triangle APQ</math> is isosceles, <math>AQ=2x\cos(\alpha)</math>. So, <math>\overline{AB}=x\left(2\cos(\alpha)+1\right)</math>. <math>\triangle{ABC}</math> is isosceles too, so <math>x=\overline{BC}=2\overline{AC}\sin\left(\frac{\alpha}{2}\right)=2x\left(2\cos(\alpha)+1\right)\sin\left(\frac{\alpha}{2}\right)</math>.<br />
Simplifying, <math>1=4\cos(\alpha)\sin\left(\frac{\alpha}{2}\right)+2sin\left(\frac{\alpha}{2}\right)</math>. By double angle formula, we know that <math>\cos(\alpha)=1-2\sin^2\left(\frac{\alpha}{2}\right)</math>.<br />
Applying, <math>4\sin\left(\frac{\alpha}{2}\right)-8\sin^3\left(\frac{\alpha}{2}\right)+2\sin\left(\frac{\alpha}{2}\right)=1</math> and <math>2\left(3\sin\left(\frac{\alpha}{2}\right)-4\sin^3\left(\frac{\alpha}{2}\right)\right)=1</math>.<br />
The expression in the parentheses though is triple angle formula! Hence, <math>\sin\left(\frac{3\alpha}{2}\right)=\frac{1}{2}</math>, <math>\alpha=20^o</math>. It follows now that <math>\angle APQ=140^o</math>, <math>\angle ACB=80^o</math>. Giving <math>r=\frac{4}{7}</math>.<br />
<math>\left\lfloor 1000\left(\frac {4}{7}\right)\right\rfloor = \boxed{571}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2000|n=I|num-b=13|num-a=15|t=721509}}<br />
<br />
[[Category:Intermediate Geometry Problems]]<br />
{{MAA Notice}}</div>Maxninga938