https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Drbao&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T18:58:50ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=1990_IMO_Problems/Problem_3&diff=1563631990 IMO Problems/Problem 32021-06-19T14:26:08Z<p>Drbao: /* Solution 3 */</p>
<hr />
<div>==Problem==<br />
Determine all integers <math>n > 1</math> such that <math>\frac{2^n+1}{n^2}</math> is an integer.<br />
<br />
==Solution 1==<br />
Let <math> N = \{ n\in\mathbb{N} : 2^n\equiv - 1\pmod{n^2} \}</math> be the set of all solutions and <math> P = \{ p\text{ is prime} : \exists n\in N, p|n \}</math> be the set of all prime factors of the solutions.<br />
<br />
It is clear that the smallest element of <math> P</math> is 3.<br />
Assume that <math> P\ne\{3\}</math> and let's try to determine the second smallest element <math> q = \min (P\setminus\{3\})</math>.<br />
<br />
Let <math> n\in N</math> be a multiple of <math> q</math>. It is important to notice that <math> 9\not|n</math> (otherwise it is easy to get that any power of <math> 3</math> divides <math> n</math>, a non-sense). Therefore, <math> n = 3^t n'</math> where <math> t = 0</math> or <math> 1</math> and <math> n'</math> does not have prime divisors smaller than <math> q</math>.<br />
Since <math> 2^{2n}\equiv 1\pmod{q}</math>, the multiplicative order <math> r = ord_q(2)</math> of 2 modulo <math> q</math> divides <math> 2n</math>. Moreover, <math> r</math> must be even, since otherwise we would have <math> 2^n \equiv 1\pmod{q}</math>, a contradiction to the required <math> 2^n \equiv - 1\pmod{q}</math>.<br />
Since <math> r < q</math> we must have <math> r = 2</math> or <math> 2\cdot 3 = 6</math>. But the numbers <math> 2^2 - 1 = 3</math> and <math> 2^6 - 1 = 63</math> deliver only one new prime factor <math> 7</math>, implying that <math> q = 7</math>. However, in this case <math> r = ord_7(2) = 3</math>, a contradiction. This contradiction proves that <math> P = \{3\}</math> and thus <math> N = \{1,3\}</math>.<br />
<br />
This solution was posted and copyrighted by maxal/orl. The original thread for this problem can be found here: [https://aops.com/community/p1225144]<br />
<br />
==Solution 2==<br />
Let <math> p</math> be the smallest prime divisor of <math> n</math>. It is easy to check that, <math> n=3</math> is obviously solution. Let <math> p^{a} || n</math> . <math> p | 2^{2n}-1</math> and <math> p | 2^{p-1} - 1</math> (By the fermat's theorem), we obtain that <math> p=3</math>. It is also obvious that n is an odd number.<br />
Lemma: For all <math> n</math> positive integers, <math> 2</math> is a primitive root modulo <math> 3^{n}</math>.<br />
<math> 3^{2a} | 2^{2n} - 1</math>. Using the lemma, we get that <math> \phi(3^{2a}) | 2n</math>. Using the power of three, we obtain that <math> 3^{2a-1} | 3^{a}</math>. This is only possible when <math> a \geq 2a-1</math>. So <math> a=1</math>. Now <math> q</math> be the second smallest prime divisor of <math> n</math>. <math> (2n,q-1) = 2 , 6</math>. If this equals to 2, we get <math> q=3</math> which is a contradiction.If <math> (2n,q-1) = 6</math> then <math> q|63</math>. We know that <math> q</math> is different from <math> 3</math>. Hence <math> q</math> must be <math> 7</math>. But this is impossible since<br />
<math> 2^{n} +1\equiv 2\mod 7</math> when <math> n</math> is divisible by <math> 3</math>. Hence the answer is <math> n = 3</math>.<br />
<br />
This solution was posted and copyrighted by grumpyorum. The original thread for this problem can be found here: [https://aops.com/community/p1707739]<br />
<br />
==Solution 3==<br />
Trivially <math>n=1</math> is a solution. Now assume <math>n\neq 1</math> and define <math>\pi(n)</math> to be the smallest prime divisor of <math>n</math>. Let <math>\pi(n)=p\neq 2</math>. Then we have:<br />
<cmath>\begin{eqnarray*} p\mid 2^n+1\mid 2^{2n}-1 \text{ and } p\mid 2^{p-1}-1 \\ \implies p\mid 2^{\gcd(2n, p-1)}-1 \end{eqnarray*}</cmath><br />
<br />
Now if <math>r\neq 2\mid n</math> then we can't have <math>r\mid p-1</math> because then <math>r\le p-1</math> contradiction. Therefore <math>r=2</math> and since <math>n</math> is odd <math>\gcd(2n, p-1)=2</math>. Hence<cmath>p\mid 2^2-1 \implies p=3</cmath>Let <math>v_3(n)=k</math>. By lifting the exponent we must have<cmath>v_3(2^n+1)=1+k\ge v_3(n^2)=2k \implies k=1</cmath>Let <math>n=3n_1</math>. <math>n_1=1</math> is a solution (<math>2^3+1=3^2=9</math>). Assume <math>n_1\neq 1</math> and let <math>\pi(n_1)=q\neq 3</math>. By Chinese Remainder Theorem since <math>q\neq 3</math> we have:<br />
\begin{eqnarray*} q\mid 8^{n_1}+1\mid 8^{2n_1}-1 \text{ and } q\mid 8^{q-1}-1 \\ \implies q\mid 8^{\gcd(2n_1, q-1)}-1=63 \text{ so } q=7 \end{eqnarray*}<br />
<br />
However <math>2^n+1\equiv 8^{n_1}+1\equiv 2\pmod{7}</math> contradiction.<br />
<br />
The solutions are henceforth <math>n=1, 3</math>.<br />
This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [https://aops.com/community/p3217312]<br />
<br />
==Solution 4==<br />
et <math>n>1</math> and <math>p</math> be the smallest prime factor of <math>n</math>.Then <math>p|2^{2n}-1,p|2^{p-1}-1 \Rightarrow p|2^{\text{gcd}(2n,p-1)}=2^2-1=3\Rightarrow \boxed{p=3}</math>.<br />
Thus <math>n=3^x*y</math> for some positive <math>x</math> and <math>y</math>.<br />
Also <math>n^2|2^n+1 \Rightarrow 2x=v_3(n^2) \le v_3(2^n+1)=v_3(3)+v_3(n)=x+1 \Rightarrow \boxed{x=1}</math>.<br />
<br />
Thus <math>n=3y</math> for some positive integer <math>y</math>.<br />
Now let <math>y>1</math> and <math>q</math> be the smallest prime divisor of <math>y</math>.Then we can deduce that <math>q|2^{\text{gcd}(2n,q-1)}-1=2^{2\text{gcd}(n,q-1)}-1=2^6-1=63=7*3^2 \Rightarrow \boxed{q=7}</math>(Note that <math>\text{gcd}(n,q-1)</math> is <math>1</math> or <math>3</math>).<br />
<br />
But this gives <math>7|2^n+1</math> which is false as <math>2^n+1</math> leaves remainders <math>1,2,4</math> modulo <math>7</math>.<br />
<br />
Thus <math>y=1</math> and <math>\boxed{n=3}</math> if <math>n>1</math>.<br />
<br />
Thus the solutions are <math>\boxed{n=1}</math> and <math>\boxed{n=3}</math><br />
<br />
This solution was posted and copyrighted by sayantanchakraborty. The original thread for this problem can be found here: [https://aops.com/community/p3494946]<br />
<br />
Many more solutions can be found in the thread in Contest Collections.<br />
<br />
== See Also == {{IMO box|year=1990|num-b=2|num-a=4}}</div>Drbaohttps://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_15&diff=1232462020 AIME I Problems/Problem 152020-05-29T15:00:05Z<p>Drbao: /* Solution 2 */</p>
<hr />
<div><br />
== Problem ==<br />
Let <math>\triangle ABC</math> be an acute triangle with circumcircle <math>\omega,</math> and let <math>H</math> be the intersection of the altitudes of <math>\triangle ABC.</math> Suppose the tangent to the circumcircle of <math>\triangle HBC</math> at <math>H</math> intersects <math>\omega</math> at points <math>X</math> and <math>Y</math> with <math>HA=3,HX=2,</math> and <math>HY=6.</math> The area of <math>\triangle ABC</math> can be written as <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 />
<br />
== Solution 1==<br />
The following is a power of a point solution to this menace of a problem:<br />
<asy><br />
/* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */<br />
import graph; size(18cm); <br />
real labelscalefactor = 0.5; /* changes label-to-point distance */<br />
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ <br />
pen dotstyle = black; /* point style */ <br />
real xmin = -12.821705655137235, xmax = 10.870448356581754, ymin = -3.0673360097491003, ymax = 10.363346102088961; /* image dimensions */<br />
pen wrwrwr = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); <br />
/* draw figures */<br />
draw((xmin, 0.0052470390246834855*xmin + 3.437118410441658)--(xmax, 0.0052470390246834855*xmax + 3.437118410441658), linewidth(2) + wrwrwr); /* line */<br />
draw(circle((-4.538171990791266,4.905585481447388), 4.693275552848494), linewidth(2) + wrwrwr); <br />
draw(circle((-4.522512329243054,1.9211095752183682), 4.693275552848494), linewidth(2) + wrwrwr); <br />
draw((xmin, -190.58367877496823*xmin-1479.5139994609244)--(xmax, -190.58367877496823*xmax-1479.5139994609244), linewidth(2) + wrwrwr); /* line */<br />
draw((xmin, 0.9703333412757664*xmin + 12.849035992754926)--(xmax, 0.9703333412757664*xmax + 12.849035992754926), linewidth(2) + wrwrwr); /* line */<br />
draw(circle((-7.790821079477277,5.289342543424063), 1.8930768158550504), linewidth(2) + wrwrwr); <br />
draw((xmin, -1.0305736775830343*xmin-5.438100054565965)--(xmax, -1.0305736775830343*xmax-5.438100054565965), linewidth(2) + wrwrwr); /* line */<br />
draw((xmin, -1.0305736775830343*xmin + 0.22866488339331612)--(xmax, -1.0305736775830343*xmax + 0.22866488339331612), linewidth(2) + wrwrwr); /* line */<br />
/* dots and labels */<br />
dot((-8.98,3.39),dotstyle); <br />
label("$B$", (-8.914038694762803,3.548005694821766), NE * labelscalefactor); <br />
dot((-0.08068432003432058,3.4366950566657577),dotstyle); <br />
label("$C$", (-0.021788682572170717,3.594159241597842), NE * labelscalefactor); <br />
dot((-4.538171990791266,4.905585481447388),dotstyle); <br />
label("$O$", (-4.483298204259513,5.055688222840243), NE * labelscalefactor); <br />
dot((-4.522512329243054,1.9211095752183682),linewidth(4pt) + dotstyle); <br />
label("$O'$", (-4.467913688667488,2.0403231668032897), NE * labelscalefactor); <br />
dot((-7.790821079477277,5.289342543424063),dotstyle); <br />
label("$H$", (-7.729430994176854,5.440301112640874), NE * labelscalefactor); <br />
dot((-7.806480741025488,8.273818449653083),linewidth(4pt) + dotstyle); <br />
label("$A$", (-7.7448155097688804,8.394128106309726), NE * labelscalefactor); <br />
dot((-9.139423209055858,3.980748932978468),linewidth(4pt) + dotstyle); <br />
label("$X$", (-9.083268366275083,4.101848256134676), NE * labelscalefactor); <br />
dot((-9.752410287411378,3.3859471330788855),linewidth(4pt) + dotstyle); <br />
label("$K$", (-9.68326447436407,3.5018521480456903), NE * labelscalefactor); <br />
dot((-3.475227037470366,9.476907329794422),linewidth(4pt) + dotstyle); <br />
label("$Y$", (-3.4063821128177407,9.594120322487697), NE * labelscalefactor); <br />
dot((-7.780888168280388,3.3962917865759925),linewidth(4pt) + dotstyle); <br />
label("$L$", (-7.714046478584829,3.5172366636377155), NE * labelscalefactor); <br />
dot((-7.776585346090923,2.5762441045932913),linewidth(4pt) + dotstyle); <br />
label("$D$", (-7.714046478584829,2.7018573372603765), NE * labelscalefactor); <br />
dot((-6.307325123263112,6.728828131386446),linewidth(4pt) + dotstyle); <br />
label("$E$", (-6.252517497342424,6.855676547107199), NE * labelscalefactor); <br />
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); <br />
/* end of picture */<br />
</asy><br />
<br />
Let points be what they appear as in the diagram below. Note that <math>3HX = HY</math> is not insignificant; from here, we set <math>XH = HE = \frac{1}{2} EY = HL = 2</math> by PoP and trivial construction. Now, <math>D</math> is the reflection of <math>A</math> over <math>H</math>. Note <math>AO \perp XY</math>, and therefore by Pythagorean theorem we have <math>AE = XD = \sqrt{5}</math>. Consider <math>HD = 3</math>. We have that <math>\triangle HXD \cong HLK</math>, and therefore we are ready to PoP with respect to <math>(BHC)</math>. Setting <math>BL = x, LC = y</math>, we obtain <math>xy = 10</math> by PoP on <math>(ABC)</math>, and furthermore, we have <math>KH^2 = 9 = (KL - x)(KL + y) = (\sqrt{5} - x)(\sqrt{5} + y)</math>. Now, we get <math>4 = \sqrt{5}(y - x) - xy</math>, and from <math>xy = 10</math> we take <cmath>\frac{14}{\sqrt{5}} = y - x.</cmath> However, squaring and manipulating with <math>xy = 10</math> yields that <math>(x + y)^2 = \frac{396}{5}</math> and from here, since <math>AL = 5</math> we get the area to be <math>3\sqrt{55} \implies \boxed{058}</math>. ~awang11's sol<br />
<br />
==Solution 1a==<br />
As in the diagram, let ray <math>AH</math> extended hits BC at L and the circumcircle at say <math>P</math>. By power of the point at H, we have <math>HX \cdot HY = AH \cdot HP</math>. The three values we are given tells us that <math>HP=\frac{2\cdot 6}{3}=4</math>. L is the midpoint of <math>HP</math>(see here: https://www.cut-the-knot.org/Curriculum/Geometry/AltitudeAndCircumcircle.shtml ), so <math>HL=LP=2</math>.<br />
<br />
As in the diagram provided, let K be the intersection of <math>BC</math> and <math>XY</math>. By power of a point on the circumcircle of triangle <math>HBC</math>, <math>KH^{2}=KB \cdot KC</math>. By power of a point on the circumcircle of triangle <math>ABC</math>, <math>KB \cdot KC=KX \cdot KY</math>, thus <math>KH^{2}=(KH-2)(KH+6)</math>. Solving gives <math>4KH=12</math> or <math>KH=3</math>.<br />
<br />
By the Pythagorean Theorem on triangle <math>HKL</math>, <math>KL=\sqrt{5}</math>. Now continue with solution 1.<br />
<br />
== Solution 2 ==<br />
<asy><br />
size(10cm);<br />
pair A, B, C, D, H, K, O, P, L, M, X, Y;<br />
A = (-15, 27);<br />
B = (-24, 0);<br />
C = (24, 0);<br />
D = (-8.28, 18.04);<br />
O = (0, 7);<br />
P = (0, -7);<br />
H = (-15, 13);<br />
K = (-15, -13);<br />
M = (0, 0);<br />
L = (-15, 0);<br />
X = (-24.9569, 5.53234);<br />
Y = (8.39688, 30.5477);<br />
draw(circle(O, 25));<br />
draw(circle(P, 25));<br />
draw(A--B--C--cycle);<br />
draw(H -- K);<br />
draw(A -- O -- P -- H -- cycle);<br />
draw(X -- Y);<br />
draw(O -- X, dashed);<br />
draw(O -- Y, dashed);<br />
draw(O -- B, dashed);<br />
draw(O -- C, dashed);<br />
<br />
label("$O$", O, ENE);<br />
label("$A$", A, NW);<br />
label("$B$", B, W);<br />
label("$C$", C, E);<br />
label("$H$", H, E);<br />
label("$H'$", K, NE);<br />
label("$X$", X, W);<br />
label("$Y$", Y, NE);<br />
label("$O'$", P, E);<br />
label("$M$", M, NE);<br />
label("$L$", L, NE);<br />
label("$D$", D, NNE);<br />
<br />
label("$2$", X -- H, NW);<br />
label("$3$", H -- A, SW);<br />
label("$6$", H -- Y, NW);<br />
label("$R$", O -- Y, E);<br />
<br />
dot(O);<br />
dot(P);<br />
dot(D);<br />
dot(H);<br />
<br />
</asy><br />
Diagram not to scale.<br />
<br />
<br />
We first observe that <math>H'</math>, the image of the reflection of <math>H</math> over line <math>BC</math>, lies on circle <math>O</math>. This is because <math>\angle HBC = 90 - \angle C = \angle H'AC = \angle H'BC</math>. This is a well known lemma. The result of this observation is that circle <math>O'</math>, the circumcircle of <math>\triangle BHC</math> is the image of circle <math>O</math> over line <math>BC</math>, which in turn implies that <math>\overline{AH} = \overline{OO'}</math> and thus <math>AHO'O</math> is a parallelogram. That <math>AHO'O</math> is a parallelogram implies that <math>AO</math> is perpendicular to <math>\overline{XY}</math>, and thus divides segment <math>\overline{XY}</math> in two equal pieces, <math>\overline{XD}</math> and <math>\overline{DY}</math>, of length <math>4</math>.<br />
<br />
<br />
Using Power of a Point,<br />
<cmath>\overline{AH} \cdot \overline{HH'} = \overline{XH} \cdot \overline{HY} \Longrightarrow 3 \cdot \overline{HH'} = 2 \cdot 6 \Longrightarrow \overline{HH'} = 4</cmath><br />
This means that <math>\overline{HL} = \frac12 \cdot 4 = 2</math> and <math>\overline{AL} = 2 + 3 = 5</math>, where <math>L</math> is the foot of the altitude from <math>A</math> onto <math>BC</math>. All that remains to be found is the length of segment <math>\overline{BC}</math>.<br />
<br />
Looking at right triangle <math>\triangle AHD</math>, we find that<br />
<cmath>\overline{AD} = \sqrt{\overline{AH}^2 - \overline{HD}^2} = \sqrt{3^2 - 2^2} = \sqrt{5}</cmath><br />
Looking at right triangle <math>\triangle ODY</math>, we get the equation<br />
<cmath>\overline{OY}^2 - \overline{DY}^2 = \overline{OD}^2 = \left(\overline{AO} - \overline{AD}\right)^2</cmath><br />
Plugging in known values, and letting <math>R</math> be the radius of the circle, we find that<br />
<cmath>R^2 - 16 = (R - \sqrt{5})^2 = R^2 - 2\sqrt5 R + 5 \Longrightarrow R = \frac{21\sqrt5}{10}</cmath><br />
<br />
Recall that <math>AHO'O</math> is a parallelogram, so <math>\overline{AH} = \overline{OO'} = 3</math>. So, <math>\overline{OM} = \frac32</math>, where <math>M</math> is the midpoint of <math>\overline{BC}</math>. This means that<br />
<cmath>\overline{BC} = 2\overline{BM} = 2\sqrt{R^2 - \left(\frac32\right)^2} = 2\sqrt{\frac{441}{20} - \frac{9}{4}} = \frac{6\sqrt{55}}{5}</cmath><br />
<br />
Thus, the area of triangle <math>\triangle ABC</math> is<br />
<cmath>\frac{\overline{AL} \cdot \overline{BC}}{2} = \frac{5 \cdot \frac{6\sqrt{55}}{5}}{2} = \boxed{3\sqrt{55}}</cmath><br />
The answer is <math>3 + 55 = \boxed{058}</math>.<br />
<br />
== Video Solution ==<br />
https://www.youtube.com/watch?v=L7B20E95s4M<br />
<br />
==See Also==<br />
{{AIME box|year=2020|n=I|num-b=14|after=Last Problem}}<br />
{{MAA Notice}}</div>Drbaohttps://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_9&diff=1231052020 AIME I Problems/Problem 92020-05-28T00:07:24Z<p>Drbao: /* Solution 1 */</p>
<hr />
<div><br />
== Problem ==<br />
Let <math>S</math> be the set of positive integer divisors of <math>20^9.</math> Three numbers are chosen independently and at random with replacement from the set <math>S</math> and labeled <math>a_1,a_2,</math> and <math>a_3</math> in the order they are chosen. The probability that both <math>a_1</math> divides <math>a_2</math> and <math>a_2</math> divides <math>a_3</math> is <math>\tfrac{m}{n},</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m.</math><br />
<br />
== Solution 1 ==<br />
<br />
<asy><br />
size(12cm);<br />
for (int x = 1; x < 18; ++x) {<br />
draw((x, 0) -- (x, 9), dotted);<br />
}<br />
for (int y = 1; y < 9; ++y) {<br />
draw((0, y) -- (18, y), dotted);<br />
}<br />
<br />
draw((0, 0) -- (18, 0) -- (18, 9) -- (0, 9) -- cycle);<br />
<br />
pair b1, b2, b3;<br />
pair c1, c2, c3;<br />
pair a1, a2, a3;<br />
b1 = (3, 0); b2 = (12, 0); b3 = (16, 0);<br />
c1 = (0, 2); c2 = (0, 4); c3 = (0, 8);<br />
a1 = b1 + c1; a2 = b2 + c2; a3 = b3 + c3;<br />
<br />
draw(b1 -- a1 -- c1);<br />
draw(b2 -- a2 -- c2);<br />
draw(b3 -- a3 -- c3);<br />
<br />
dot(a1); dot(a2); dot(a3);<br />
label("$a_1$", a1, NE);<br />
label("$a_2$", a2, NE);<br />
label("$a_3$", a3, NE);<br />
label("$b_1$", b1, S);<br />
label("$b_2$", b2, S);<br />
label("$b_3$", b3, S);<br />
label("$c_1$", c1, W);<br />
label("$c_2$", c2, W);<br />
label("$c_3$", c3, W);<br />
<br />
</asy><br />
<br />
First, prime factorize <math>20^9</math> as <math>2^{18} \cdot 5^9</math>. Denote <math>a_1</math> as <math>2^{b_1} \cdot 5^{c_1}</math>, <math>a_2</math> as <math>2^{b_2} \cdot 5^{c_2}</math>, and <math>a_3</math> as <math>2^{b_3} \cdot 5^{c_3}</math>.<br />
<br />
In order for <math>a_1</math> to divide <math>a_2</math>, and for <math>a_2</math> to divide <math>a_3</math>, <math>b_1\le b_2\le b_3</math>, and <math>c_1\le c_2\le c_3</math>. We will consider each case separately. Note that the total amount of possibilities is <math>190^3</math>, as there are <math>(18+1)(9+1)=190</math> choices for each factor.<br />
<br />
We notice that if we add <math>1</math> to <math>b_2</math> and <math>2</math> to <math>b_3</math>, then we can reach the stronger inequality <math>0\le b_1<b_2+1<b_3+2\le 20</math>. Therefore, if we pick <math>3</math> integers from <math>0</math> to <math>20</math>, they will correspond to a unique solution, forming a 1-1 correspondence between the numbers <math>b_1</math>, <math>b_2+1</math>, and <math>b_3+2</math>. This is also equivalent to applying stars and bars on distributing the powers of 2 and 5 through differences. The amount of solutions to this inequality is <math>\dbinom{21}{3}</math>.<br />
<br />
The case for <math>c_1</math>,<math>c_2</math>, and <math>c_3</math> proceeds similarly for a result of <math>\dbinom{12}{3}</math>. Therefore, the probability of choosing three such factors is <cmath>\frac{\dbinom{21}{3} \cdot \dbinom{12}{3}}{190^3}.</cmath> Simplification gives <math>\frac{77}{1805}</math>, and therefore the answer is <math>\boxed{077}</math>.<br />
<br />
-molocyxu<br />
<br />
== Solution 2==<br />
<br />
Same as before, say the factors have powers of <math>b</math> and <math>c</math>. <math>b_1, b_2, b_3</math> can either be all distinct, all equal, or two of the three are equal. As well, we must have <math>b_1 \leq b_2 \leq b_3</math>. If they are all distinct, the number of cases is simply <math>{19 \choose 3}</math>. If they are all equal, there are only <math>19</math> cases for the general value. If we have a pair equal, then we have <math>2 \cdot {19\choose 2}</math>. We need to multiply by <math>2</math> because if we have two values <math>b_i < b_j</math>, we can have either <math>(b_i, b_i, b_j)</math> or <math>(b_i, b_j, b_j)</math>. <br />
<br />
<cmath>{19 \choose 3} + 2 \cdot {19 \choose 2} + 19 = 1330</cmath><br />
<br />
Likewise for <math>c</math>, we get<br />
<br />
<cmath>{10 \choose 3} + 2 \cdot {10 \choose 2} + 10 = 220</cmath><br />
<br />
The final probability is simply <math>\frac{1330 \cdot 220}{190^3}</math>. Simplification gives <math>\frac{77}{1805}</math>, and therefore the answer is <math>\boxed{077}</math>.<br />
<br />
==Solution 3==<br />
<br />
Similar to before, we calculate that there are <math>190^3</math> ways to choose <math>3</math> factors with replacement. Then, we figure out the number of triplets <math>{a,b,c}</math> and <math>{d,f,g}</math>, where <math>a</math>, <math>b</math>, and <math>c</math> represent powers of <math>2</math> and <math>d</math>, <math>f</math>, and <math>g</math> represent powers of <math>5</math>, such that the triplets are in non-descending order. The maximum power of <math>2</math> is <math>18</math>, and the maximum power of <math>5</math> is <math>9</math>. Using the Hockey Stick identity, we figure out that there are <math>\dbinom{12}{3}</math> ways to choose <math>d</math>, <math>f</math> and <math>g</math>, and <math>\dbinom{21}{3}</math> ways to choose <math>a</math>, <math>b</math>, and <math>c</math>. Therefore, the probability of choosing <math>3</math> factors which satisfy the conditions is <cmath>\frac{\dbinom{21}{3} \cdot \dbinom{12}{3}}{190^3}.</cmath> This simplifies to <math>\frac{77}{1805}</math>, therefore <math>m =</math> <math>\boxed{077}</math>.<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2020|n=I|num-b=8|num-a=10}}<br />
<br />
[[Category: Intermediate Combinatorics Problems]]<br />
{{MAA Notice}}</div>Drbaohttps://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_8&diff=1075302004 AIME II Problems/Problem 82019-07-10T15:19:59Z<p>Drbao: /* Solution */</p>
<hr />
<div>== Problem ==<br />
How many positive integer divisors of <math>2004^{2004}</math> are divisible by exactly 2004 positive integers?<br />
<br />
== Solution ==<br />
The [[prime factorization]] of 2004 is <math>2^2\cdot 3\cdot 167</math>. Thus the prime factorization of <math>2004^{2004}</math> is <math>2^{4008}\cdot 3^{2004}\cdot 167^{2004}</math>.<br />
<br />
We can [[divisor function | count the number of divisors]] of a number by multiplying together one more than each of the [[exponentiation | exponents]] of the prime factors in its prime factorization. For example, the number of divisors of <math>2004=2^2\cdot 3^1\cdot 167^1</math> is <math>(2+1)(1+1)(1+1)=12</math>. <br />
<br />
A positive integer divisor of <math>2004^{2004}</math> will be of the form <math>2^a\cdot 3^b\cdot 167^c</math>. Thus we need to find how many <math>(a,b,c)</math> satisfy <br />
<br />
<center><math>(a+1)(b+1)(c+1)=2^2\cdot 3\cdot 167.</math></center> <br />
<br />
We can think of this as [[partition]]ing the exponents to <math>a+1,</math> <math>b+1,</math> and <math>c+1</math>. So let's partition the 2's first. There are two 2's so this is equivalent to partitioning two items in three containers. We can do this in <math>{4 \choose 2} = 6</math> ways. We can partition the 3 in three ways and likewise we can partition the 167 in three ways. So we have <math>6\cdot 3\cdot 3 = \boxed{54}</math> as our answer.<br />
<br />
== See also ==<br />
{{AIME box|year=2004|n=II|num-b=7|num-a=9}}<br />
<br />
[[Category:Intermediate Number Theory Problems]]<br />
[[Category:Intermediate Combinatorics Problems]]<br />
{{MAA Notice}}</div>Drbaohttps://artofproblemsolving.com/wiki/index.php?title=1993_AIME_Problems/Problem_4&diff=1065641993 AIME Problems/Problem 42019-06-18T14:25:22Z<p>Drbao: /* Solution */</p>
<hr />
<div>== Problem ==<br />
How many ordered four-tuples of integers <math>(a,b,c,d)\,</math> with <math>0 < a < b < c < d < 500\,</math> satisfy <math>a + d = b + c\,</math> and <math>bc - ad = 93\,</math>?<br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
Let <math>k = a + d = b + c</math> so <math>d = k-a, b=k-c</math>. It follows that <math>(k-c)c - a(k-a) = (a-c)(a+c-k) = (c-a)(d-c) = 93</math>. Hence <math>(c - a,d - c) = (1,93),(3,31),(31,3),(93,1)</math>.<br />
<br />
Solve them in tems of <math>c</math> to get <br />
<math>(a,b,c,d) = (c - 93,c - 92,c,c + 1),</math> <math>(c - 31,c - 28,c,c + 3),</math> <math>(c - 1,c + 92,c,c + 93),</math> <math>(c - 3,c + 28,c,c + 31)</math>. The last two solutions don't follow <math>a < b < c < d</math>, so we only need to consider the first two solutions.<br />
<br />
The first solution gives us <math>c - 93\geq 1</math> and <math>c + 1\leq 499</math> <math>\implies 94\leq c\leq 498</math>, and the second one gives us <math>32\leq c\leq 496</math>.<br />
<br />
So the total number of such four-tuples is <math>405 + 465 = \boxed{870}</math>.<br />
<br />
=== Solution 2 ===<br />
Let <math>b = a + m</math> and <math>c = a + m + n</math>. From <math>a + d = b + c</math>, <math>d = b + c - a = a + 2m + n</math>. <br />
<br />
Substituting <math>b = a + m</math>, <math>c = a + m + n</math>, and <math>d = b + c - a = a + 2m + n</math> into <math>bc - ad = 93</math>,<br />
<cmath><br />
bc - ad = (1 + m)(1 + m + n) - a(a + 2m + n) = m(m + n). = 93 = 3(31)<br />
</cmath><br />
Hence, <math>(m,n) = (1,92)</math> or <math>(3,28)</math>. <br />
<br />
For <math>(m,n) = (1,92)</math>, we know that <math>0 < a < a + 1 < a + 93 < a + 94 < 500</math>, so there are <math>405</math> four-tuples. For <math>(m,n) = (3,28)</math>, <math>0 < a < a + 3 < a + 31 < a + 34 < 500</math>, and there are <math>465</math> four-tuples. In total, we have <math>405 + 465 = \boxed{870}</math> four-tuples.<br />
<br />
=== Solution 3 ===<br />
Square both sides of the first equation in order to get <math>bc</math> and <math>ad</math> terms, which we can plug <math>93</math> in for.<br />
<br />
<math>(a+d)^2 = (b+c)^2 \implies a^2 + 2ad + d^2 = b^2 + 2bc + c^2 \implies 2bc-2ad = a^2-b^2 + d^2-c^2 \implies 2(bc-ad) = (a-b)(a+b)<br />
+(d-c)(d+c)</math><br />
<br />
We can plug <math>93</math> in for <math>bc - ad</math> to get <math>186</math> on the left side, and also observe that <math>a-b = c-d</math> after rearranging the first equation. Plug in <math>c-d</math> for <math>a-b</math>.<br />
<br />
<math>186 = (c-d)(a+b) + (d-c)(d+c) \implies 186 = -(d-c)(a+b) + (d-c)(d+c) \implies 186 = (d-c)(d+c-a-b)</math><br />
<br />
Now observe the possible factors of <math>186</math>, which are <math>1 \cdot 186, 2\cdot 93, 3 \cdot 62, 6\cdot 31</math>. <math>(d-c)</math> and <math>(d+c-a-b)</math> must be factors of <math>186</math>, and <math>(d+c-a-b)</math> must be greater than <math>(d-c)</math>.<br />
<br />
<math>1 \cdot 186</math> work, and yields <math>405</math> possible solutions.<br />
<math>2 \cdot 93</math> does not work, because if <math>c-d = 2</math>, then <math>a+b</math> must differ by 2 as well, but an odd number <math>93</math> can only result from two numbers of different parity. <math>c-d</math> will be even, and <math>a+b</math> will be even, so <math>c+d - (a+b)</math> must be even.<br />
<math>3 \cdot 62</math> works, and yields <math>465</math> possible solutions, while <math>6 \cdot 31</math> fails for the same reasoning above.<br />
<br />
Thus, the answer is <math>405 + 465 = \boxed{870}</math><br />
<br />
===Solution 4===<br />
<br />
Add the two conditions together to get <math>a+d+ad+93=b+c+bc</math>. Rearranging and factorising with SFFT, <math>(a+1)(d+1)+93=(b+1)(c+1)</math>. This implies that for every quadruple <math>(a,b,c,d)</math>, we can replace <math>a\longrightarrow a+1</math>, <math>b\longrightarrow b+1</math>, etc. and this will still produce a valid quadruple. This means, that we can fix <math>a=1</math>, and then just repeatedly add <math>1</math> to get the other quadruples. <br />
<br />
Now, our conditions are <math>b+c=d+1</math> and <math>bc=d+93</math>. Replacing <math>d</math> in the first equation, we get <math>bc-b-c=92</math>. Factorising again with SFFT gives <math>(b-1)(c-1)=93</math>. Since <math>b<c</math>, we have two possible cases to consider.<br />
<br />
Case 1: <math>b=2</math>, <math>c=94</math>. This produces the quadruple <math>(1,2,94,95)</math>, which indeed works.<br />
<br />
Case 2: <math>b=4</math>, <math>c=32</math>. This produces the quadruple <math>(1,4,32,35)</math>, which indeed works. <br />
<br />
Now, for case 1, we can add <math>1</math> to each term exactly <math>404</math> times (until we get the quadruple <math>(405,406,498,499)</math>), until we violate <math>d<500</math>. This gives <math>405</math> quadruples for case 1.<br />
<br />
For case 2, we can add <math>1</math> to each term exactly <math>464</math> times (until we get the quadruple <math>(465,468,496,499)</math>). this gives <math>465</math> quadruples for case 2.<br />
<br />
In conclusion, having exhausted all cases, we can finish. There are hence <math>405+465=\boxed{870}</math> possible quadruples.<br />
<br />
===Solution 5===<br />
<br />
Let <math>r = d-c</math>. From the equation <math>a+d = b+c</math>, we have <cmath> r = d-c = b-a , </cmath> so <math>b = a+r</math> and <math>c = d-r</math>. We then have <cmath> 93 = (a+r)(d-r) - ad = rd - ra - r^2 = r(d-a-r) . </cmath> Since <math>c > b</math>, <math>d-r > a+r</math>, or <math>d-a-r > r</math>. Since the prime factorization of 93 is <math>3 \cdot 31</math>, we must either have <math>r=1</math> and <math>d-a-r = 93</math>, or <math>r=3</math> and <math>d-a-r = 31</math>. We consider these cases separately.<br />
<br />
If <math>r=1</math>, then <math>d-a = 94</math>, <math>b= a+1</math>, and <math>c = d-1</math>. Thus <math>d</math> can be any integer between 95 and 499, inclusive, and our choice of <math>d</math> determines the four-tuple <math>(a,b,c,d)</math>. We therefore have <math>499-95+1 = 405</math> possibilities in this case.<br />
<br />
If <math>r=3</math>, then <math>d-a = 34</math>, <math>b = a+3</math>, and <math>c=d-3</math>. Thus <math>d</math> can be any integer between 35 and 499, inclusive, and our choice of <math>d</math> determines the four-tuple <math>(a,b,c,d)</math>, as before. We therefore have <math>499-35+1 = 465</math> possibilities in this case.<br />
<br />
Since there are 405 possibilities in the first case and 465 possibilities in the second case, in total there are <math>405 + 465 = \boxed{870}</math> four-tuples.<br />
<br />
== See also ==<br />
{{AIME box|year=1993|num-b=3|num-a=5}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Drbaohttps://artofproblemsolving.com/wiki/index.php?title=1993_AIME_Problems/Problem_4&diff=1065631993 AIME Problems/Problem 42019-06-18T14:19:59Z<p>Drbao: /* Solution 3 */</p>
<hr />
<div>== Problem ==<br />
How many ordered four-tuples of integers <math>(a,b,c,d)\,</math> with <math>0 < a < b < c < d < 500\,</math> satisfy <math>a + d = b + c\,</math> and <math>bc - ad = 93\,</math>?<br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
Let <math>k = a + d = b + c</math> so <math>d = k-a, b=k-c</math>. It follows that <math>(k-c)c - a(k-a) = (a-c)(a+c-k) = (c-a)(d-c) = 93</math>. Hence <math>(c - a,d - c) = (1,93),(3,31),(31,3),(93,1)</math>.<br />
<br />
Solve them in tems of <math>c</math> to get <br />
<math>(a,b,c,d) = (c - 93,c - 92,c,c + 1),</math> <math>(c - 31,c - 28,c,c + 3),</math> <math>(c - 1,c + 92,c,c + 93),</math> <math>(c - 3,c + 28,c,c + 31)</math>. The last two solutions don't follow <math>a < b < c < d</math>, so we only need to consider the first two solutions.<br />
<br />
The first solution gives us <math>c - 93\geq 1</math> and <math>c + 1\leq 499</math> <math>\implies 94\leq c\leq 498</math>, and the second one gives us <math>32\leq c\leq 496</math>.<br />
<br />
So the total number of such four-tuples is <math>405 + 465 = \boxed{870}</math>.<br />
<br />
=== Solution 2 ===<br />
Let <math>b = a + m</math> and <math>c = a + m + n</math>. From <math>a + d = b + c</math>, <math>d = b + c - a = a + 2m + n</math>. <br />
<br />
Substituting <math>b = a + m</math>, <math>c = a + m + n</math>, and <math>d = b + c - a = a + 2m + n</math> into <math>bc - ad = 93</math>,<br />
<cmath><br />
bc - ad = (1 + m)(1 + m + n) - a(a + 2m + n) = m(m + n). = 93 = 3(31)<br />
</cmath><br />
Hence, <math>(m,n) = (1,92)</math> or <math>(3,28)</math>. <br />
<br />
For <math>(m,n) = (1,92)</math>, we know that <math>0 < a < a + 1 < a + 93 < a + 94 < 500</math>, so there are <math>405</math> four-tuples. For <math>(m,n) = (3,28)</math>, <math>0 < a < a + 3 < a + 31 < a + 34 < 500</math>, and there are <math>465</math> four-tuples. In total, we have <math>405 + 465 = \boxed{870}</math> four-tuples.<br />
<br />
=== Solution 3 ===<br />
Square both sides of the first equation in order to get <math>bc</math> and <math>ad</math> terms, which we can plug <math>93</math> in for.<br />
<br />
<math>(a+d)^2 = (b+c)^2 \implies a^2 + 2ad + d^2 = b^2 + 2bc + c^2 \implies 2bc-2ad = a^2-b^2 + d^2-c^2 \implies 2(bc-ad) = (a-b)(a+b)<br />
+(d-c)(d+c)</math><br />
<br />
We can plug <math>93</math> in for <math>bc - ad</math> to get <math>186</math> on the left side, and also observe that <math>a-b = c-d</math> after rearranging the first equation. Plug in <math>c-d</math> for <math>a-b</math>.<br />
<br />
<math>186 = (c-d)(a+b) + (d-c)(d+c) \implies 186 = -(d-c)(a+b) + (d-c)(d+c) \implies 186 = (d-c)(d+c-a-b)</math><br />
<br />
Now observe the possible factors of <math>186</math>, which are <math>1 \cdot 186, 2\cdot 93, 3 \cdot 62, 6\cdot 31</math>. <math>(d-c)</math> and <math>(d+c-a-b)</math> must be factors of <math>186</math>, and <math>(d+c-a-b)</math> must be greater than <math>(d-c)</math>.<br />
<br />
<math>1 \cdot 186</math> work, and yields <math>405</math> possible solutions.<br />
<math>2 \cdot 93</math> does not work, because if <math>c-d = 2</math>, then <math>a+b</math> must differ by 2 as well, but an odd number <math>93</math> can only result from two numbers of different parity. <math>c-d</math> will be even, and <math>a+b</math> will be even, so <math>c+d - (a+b)</math> must be even.<br />
<math>3 \cdot 62</math> works, and yields <math>465</math> possible solutions, while <math>6 \cdot 31</math> fails for the same reasoning above.<br />
<br />
Thus, the answer is <math>405 + 465 = \boxed{870}</math><br />
<br />
===Solution 4===<br />
<br />
Add the two conditions together to get <math>a+d+ad+93=b+c+bc</math>. Rearranging and factorising with SFFT, <math>(a+1)(d+1)+93=(b+1)(c+1)</math>. This implies that for every quadruple <math>(a,b,c,d)</math>, we can replace <math>a\longrightarrow a+1</math>, <math>b\longrightarrow b+1</math>, etc. and this will still produce a valid quadruple. This means, that we can fix <math>a=1</math>, and then just repeatedly add <math>1</math> to get the other quadruples. <br />
<br />
Now, our conditions are <math>b+c=d+1</math> and <math>bc=d+93</math>. Replacing <math>d</math> in the first equation, we get <math>bc-b-c=92</math>. Factorising again with SFFT gives <math>(b-1)(c-1)=93</math>. Since <math>b<c</math>, we have two possible cases to consider.<br />
<br />
Case 1: <math>b=2</math>, <math>c=94</math>. This produces the quadruple <math>(1,2,94,95)</math>, which indeed works.<br />
<br />
Case 2: <math>b=4</math>, <math>c=32</math>. This produces the quadruple <math>(1,4,32,35)</math>, which indeed works. <br />
<br />
Now, for case 1, we can add <math>1</math> to each term exactly <math>404</math> times (until we get the quadruple <math>(405,406,498,499)</math>), until we violate <math>d<500</math>. This gives <math>405</math> quadruples for case 1.<br />
<br />
For case 2, we can add <math>1</math> to each term exactly <math>464</math> times (until we get the quadruple <math>(465,468,496,499)</math>). this gives <math>465</math> quadruples for case 2.<br />
<br />
In conclusion, having exhausted all cases, we can finish. There are hence <math>405+465=\boxed{870}</math> possible quadruples.<br />
<br />
== See also ==<br />
{{AIME box|year=1993|num-b=3|num-a=5}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Drbaohttps://artofproblemsolving.com/wiki/index.php?title=1999_AIME_Problems/Problem_2&diff=1062711999 AIME Problems/Problem 22019-06-13T19:27:50Z<p>Drbao: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
Consider the [[parallelogram]] with [[vertex|vertices]] <math>(10,45)</math>, <math>(10,114)</math>, <math>(28,153)</math>, and <math>(28,84)</math>. A [[line]] through the [[origin]] cuts this figure into two [[congruent]] [[polygon]]s. The [[slope]] of the line is <math>m/n,</math> where <math>m_{}</math> and <math>n_{}</math> are [[relatively prime]] [[positive]] [[integer]]s. Find <math>m+n</math>.<br />
<br />
== Solution ==<br />
=== Solution 1 ===<br />
Let the first point on the line <math>x=10</math> be <math>(10,45+a)</math> where a is the height above <math>(10,45)</math>. Let the second point on the line <math>x=28</math> be <math>(28, 153-a)</math>. For two given points, the line will pass the origin if the coordinates are [[proportion]]al (such that <math>\frac{y_1}{x_1} = \frac{y_2}{x_2}</math>). Then, we can write that <math>\frac{45 + a}{10} = \frac{153 - a}{28}</math>. Solving for <math>a</math> yields that <math>1530 - 10a = 1260 + 28a</math>, so <math>a=\frac{270}{38}=\frac{135}{19}</math>. The slope of the line (since it passes through the origin) is <math>\frac{45 + \frac{135}{19}}{10} = \frac{99}{19}</math>, and the solution is <math>m + n = \boxed{118}</math>.<br />
<br />
=== Solution 2 ===<br />
You can clearly see that a line that cuts a parallelogram into two congruent pieces must go through the center of the parallelogram. Taking the midpoint of <math>(10,45)</math>, and <math>(28,153)</math> gives <math>(19,99)</math>, which is the center of the parallelogram. Thus the slope of the line must be <math>\frac{99}{19}</math>, and the solution is <math>\boxed{118}</math>.<br />
<br />
=== Solution 3 (Area) === <br />
<br />
Note that the area of the parallelogram is equivalent to <math>69 \cdot 18 = 1242,</math> so the area of each of the two trapezoids with congruent area is <math>621.</math> Therefore, since the height is <math>18,</math> the sum of the bases of each trapezoid must be <math>69.</math> <br />
<br />
The points where the line in question intersects the long side of the parallelogram can be denoted as <math>(10, \frac{10m}{n})</math> and <math>(28, \frac{28m}{n}),</math> respectively. We see that <math>\frac{10m}{n} - 45 + \frac{28m}{n} - 84 = 69,</math> so <math>\frac{38m}{n} = 198 \implies \frac{m}{n} = \frac{99}{19} \implies \boxed{118}.</math><br />
<br />
Solution by Ilikeapos<br />
<br />
== See also ==<br />
{{AIME box|year=1999|num-b=1|num-a=3}}<br />
<br />
[[Category:Intermediate Geometry Problems]]<br />
{{MAA Notice}}</div>Drbao