https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Bjhhar&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T13:10:17ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12A_Problems/Problem_14&diff=1181422020 AMC 12A Problems/Problem 142020-02-20T02:10:24Z<p>Bjhhar: /* Solution 3 (Elementary Geometry) */</p>
<hr />
<div>==Problem 14==<br />
Regular octagon <math>ABCDEFGH</math> has area <math>n</math>. Let <math>m</math> be the area of quadrilateral <math>ACEG</math>. What is <math>\tfrac{m}{n}?</math><br />
<br />
<math>\textbf{(A) } \frac{\sqrt{2}}{4} \qquad \textbf{(B) } \frac{\sqrt{2}}{2} \qquad \textbf{(C) } \frac{3}{4} \qquad \textbf{(D) } \frac{3\sqrt{2}}{5} \qquad \textbf{(E) } \frac{2\sqrt{2}}{3}</math><br />
<br />
==Solution 1==<br />
<math>ACEG</math> is a square. WLOG <math>AB = 1,</math> then using Law of Cosines, <math>AC^2 = [ACEG] = 1^2 + 1^2 - 2 \cos{135} = 2 + \sqrt{2}.</math> The area of the octagon is just <math>[ACEG]</math> plus the area of the four congruent (by symmetry) isosceles triangles, all an angle of <math>135</math> in between two sides of length 1. Now, <cmath>\dfrac{m}{n} = \dfrac{2 + \sqrt{2}}{2 + \sqrt{2} + 4 \cdot \tfrac{1}{2} \sin{135}} = \dfrac{2 + \sqrt{2}}{2 + 2 \sqrt{2}} = \dfrac{\sqrt{2}}{2}.</cmath> The answer is <math>\boxed{\textbf{(B)}}.</math><br />
<br />
==Solution 2==<br />
Refer to the diagram. Call one of the side lengths of the square <math>s</math>. Since quadrilateral ACEG is a square, the area of the square would just be <math>s^2</math>, which we can find by applying Law of Cosines on one of the four triangles. Assume each of the sides of the octagon has length <math>1</math>. Since each angle measures <math>135^{\circ}</math> in an octagon, then <math>s^2 = 1^2+1^2-2*\cos(135^{\circ}) = 2+\sqrt{2}</math> <br />
<br />
There are many ways to find the area of the octagon, but one way is to split the octagon into two trapezoids and one rectangle. We can easily compute AF to be <math>1+\sqrt{2}</math> from splitting one of the sides into two <math>45-45-90</math> triangles. So the area of the octagon is <math>2*\frac{1+\sqrt{2}}{2}+1+\sqrt{2} \Rightarrow 2+2\sqrt{2}</math>. <br />
<br />
Hence, <cmath>\frac{m}{n} = \frac{2+\sqrt{2}}{2+2\sqrt{2}}</cmath> <br />
<cmath>\Rightarrow \frac{2+\sqrt{2}}{2+2\sqrt{2}} \cdot \frac{2-2\sqrt{2}}{2-2\sqrt{2}}</cmath><br />
<cmath>\Rightarrow \frac{-2\sqrt{2}}{-4}</cmath><br />
<cmath>\Rightarrow \boxed{\frac{\sqrt{2}}{2}}</cmath><br />
<br />
~Solution by IronicNinja<br />
<br />
== Solution 3 (Deriving Formulas) ==<br />
<br />
<asy><br />
draw((1, 2.41421356)--(2.41421356, 1)--(2.41421356, -1)--(1, -2.41421356)--(-1, -2.41421356)--(-2.41421356, -1)--(-2.41421356, 1)--(-1, 2.41421356)--cycle);<br />
draw((2.41421356, 1)--(1, -2.41421356)--(-2.41421356, -1)--(-1, 2.41421356)--cycle);<br />
label("A",(-1, 2.41421356),NW);<br />
label("B",(1, 2.41421356),NE);<br />
label("C",(2.41421356, 1),NE);<br />
label("D",(2.41421356, -1),SE);<br />
label("E",(1,-2.41421356),SE);<br />
label("F",(-1,-2.41421356),SW);<br />
label("G",(-2.41421356,-1),SW);<br />
label("H",(-2.41421356,1),NW);<br />
</asy><br />
<br />
The first thing to notice is that <math>ACEG</math> is a square. This is because, as <math>\bigtriangleup ABC \cong \bigtriangleup CDE \cong \bigtriangleup EFG \cong \bigtriangleup GHE</math>, they all have the same base, meaning that <math>AC = DE = EG = GA</math>. Hence, we have that it is a square. To determine the area of this square, we can determine the length of its diagonals.<br />
<br />
In order to do this, we first determine the area of the octagon. Letting the side length be <math>a</math>, we can create a square of length <math>s</math> around it (see figure).<br />
<asy><br />
draw((1, 2.41421356)--(2.41421356, 1)--(2.41421356, -1)--(1, -2.41421356)--(-1, -2.41421356)--(-2.41421356, -1)--(-2.41421356, 1)--(-1, 2.41421356)--cycle);<br />
label("a",(1, 2.41421356)--(2.41421356, 1),S);<br />
draw((-2.41421356, 2.41421356)--(2.41421356, 2.41421356)--(2.41421356, -2.41421356)--(-2.41421356, -2.41421356)--cycle);<br />
label("s",(-2.41421356, 2.41421356)--(2.41421356, 2.41421356),N);<br />
</asy><br />
<br />
Creating a small square of side length <math>a</math> from the corners of this figure gives us an area of <math>a^2</math>. Thus, <math>s^2 - a^2 = n</math> where <math>n</math> is the area of the octagon. We know from the Pythagorean Theorem that <math>s = a + \frac{a}{\sqrt{2}}</math>, meaning that <math>n = (a + \frac{a}{\sqrt{2}})^2 - a^2 = 2a^2(1+\sqrt{2})</math>.<br />
<br />
Dividing this by <math>8</math> gives us the area of each triangular segment which makes up the octagon. Further dividing by <math>2</math> gives us the area of a smaller segment consisting of the right triangle with legs of the apothem and <math>\frac{a}{2}</math>. Using the area of a triangle as <math>\frac{1}{2}bh</math>, we can determine the length of apothem <math>r</math> from<br />
<br />
<cmath>\frac{2a^2(1+\sqrt{2})}{8 \times 2} = \frac{\frac{a}{2}\times r}{2}</cmath><br />
<cmath>\frac{4a^2(1+\sqrt{2})}{8 } = ar</cmath><br />
<cmath>\frac{a(1+\sqrt{2})}{2} = r</cmath>.<br />
<br />
From the apothem, we can once again use the Pythagorean Theorem, giving us the length of the circumradius <math>R</math>.<br />
<br />
<cmath>R^2 = (\frac{a(1+\sqrt{2})}{2})^2 + (\frac{a}{2})^2</cmath><br />
<cmath>R^2 = \frac{a^2(1+\sqrt{2})^2}{4} + \frac{a^2}{4}</cmath><br />
<cmath>R^2 = \frac{a^2(3+2\sqrt{2})}{4} + \frac{a^2}{4}</cmath><br />
<cmath>R^2 = \frac{a^2(4+2\sqrt{2})}{4}</cmath><br />
<cmath>R = \sqrt{\frac{a^2(4+2\sqrt{2})}{4}} = \frac{a\sqrt{4 + 2\sqrt2}}{2}</cmath>.<br />
<br />
Doubling this gives us the diagonal of both the square and the octagon. From here, we can use the formula <math>A = \frac{1}{2}d^2</math> for the area of the square:<br />
<br />
<cmath>A = \frac{(a\sqrt{4 + 2\sqrt2})^2}{2}</cmath><br />
<cmath>A = \frac{a^2(4+2\sqrt{2})}{2} = m</cmath>.<br />
<br />
Thus we now only need to find the ratio <math>\frac{m}{n}</math>. This can be easily done through some algebra:<br />
<br />
<cmath>\frac{m}{n} = \frac{a^2(4+2\sqrt{2})}{2(2a^2(1+\sqrt{2})}</cmath><br />
<cmath>\frac{m}{n} = \frac{4+2\sqrt{2}}{4+4\sqrt{2}}</cmath><br />
<cmath>\frac{m}{n} = \frac{2+\sqrt{2}}{2+2\sqrt{2}}</cmath><br />
<br />
Rationalizing the denominator by multiplying by the conjugate, we get <math>\frac{m}{n} = \boxed{\textbf{(B) } \frac{\sqrt{2}}{2}}</math>. ~ciceronii<br />
<br />
*<math>\textbf{Note:}</math> this can more easily be done if you know any of these formulas. This was an entire derivation of the area of an octagon, it's apothem, and it's circumradius, but it can be much simpler if you have any of these memorized.<br />
<br />
==Solution 3 (Elementary Geometry)==<br />
WLOG, let <math>AE=1</math>. Let the intersection of <math>AF</math> and <math>GD</math> be point <math>I</math>. <math>GIF</math> is an isosceles right triangle (<math>m\angle HGF=135^{\circ}</math>), so <math>IG=IF=\frac{1}{\sqrt{2}}</math>. The distance between each side and the center is then <math>IF+\frac{1}{2}GH=\frac{1}{2}+\frac{1}{\sqrt{2}}</math>. <math>ABCDEFGH</math> is 8 triangles of base 1 and altitude <math>\frac{1}{2}+\frac{1}{\sqrt{2}}</math>, so its area is <math>8(\frac{1}{2})(\frac{1}{2}+\frac{1}{\sqrt{2}})</math> or <br />
<cmath>2+2\sqrt{2}</cmath><br />
Similarly, <math>ACEG</math> is clearly a square of area <math>GA^2</math>. By the Pythagorean Theorem, <math>GA^2=GI^2+IA^2=(\frac{1}{\sqrt{2}})^2+(1+\frac{1}{\sqrt{2}})^2</math> or <br />
<cmath>2+\sqrt{2}</cmath><br />
<cmath>\frac{m}{n} = \frac{2+\sqrt{2}}{2+2\sqrt{2}}</cmath><br />
From some fast manipulations, see that it is <math>\boxed{\textbf{B)}\frac{\sqrt{2}}{{2}}}</math><br />
<br />
~~BJHHar<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2020|ab=A|num-b=13|num-a=15}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12A_Problems/Problem_14&diff=1181412020 AMC 12A Problems/Problem 142020-02-20T02:10:03Z<p>Bjhhar: </p>
<hr />
<div>==Problem 14==<br />
Regular octagon <math>ABCDEFGH</math> has area <math>n</math>. Let <math>m</math> be the area of quadrilateral <math>ACEG</math>. What is <math>\tfrac{m}{n}?</math><br />
<br />
<math>\textbf{(A) } \frac{\sqrt{2}}{4} \qquad \textbf{(B) } \frac{\sqrt{2}}{2} \qquad \textbf{(C) } \frac{3}{4} \qquad \textbf{(D) } \frac{3\sqrt{2}}{5} \qquad \textbf{(E) } \frac{2\sqrt{2}}{3}</math><br />
<br />
==Solution 1==<br />
<math>ACEG</math> is a square. WLOG <math>AB = 1,</math> then using Law of Cosines, <math>AC^2 = [ACEG] = 1^2 + 1^2 - 2 \cos{135} = 2 + \sqrt{2}.</math> The area of the octagon is just <math>[ACEG]</math> plus the area of the four congruent (by symmetry) isosceles triangles, all an angle of <math>135</math> in between two sides of length 1. Now, <cmath>\dfrac{m}{n} = \dfrac{2 + \sqrt{2}}{2 + \sqrt{2} + 4 \cdot \tfrac{1}{2} \sin{135}} = \dfrac{2 + \sqrt{2}}{2 + 2 \sqrt{2}} = \dfrac{\sqrt{2}}{2}.</cmath> The answer is <math>\boxed{\textbf{(B)}}.</math><br />
<br />
==Solution 2==<br />
Refer to the diagram. Call one of the side lengths of the square <math>s</math>. Since quadrilateral ACEG is a square, the area of the square would just be <math>s^2</math>, which we can find by applying Law of Cosines on one of the four triangles. Assume each of the sides of the octagon has length <math>1</math>. Since each angle measures <math>135^{\circ}</math> in an octagon, then <math>s^2 = 1^2+1^2-2*\cos(135^{\circ}) = 2+\sqrt{2}</math> <br />
<br />
There are many ways to find the area of the octagon, but one way is to split the octagon into two trapezoids and one rectangle. We can easily compute AF to be <math>1+\sqrt{2}</math> from splitting one of the sides into two <math>45-45-90</math> triangles. So the area of the octagon is <math>2*\frac{1+\sqrt{2}}{2}+1+\sqrt{2} \Rightarrow 2+2\sqrt{2}</math>. <br />
<br />
Hence, <cmath>\frac{m}{n} = \frac{2+\sqrt{2}}{2+2\sqrt{2}}</cmath> <br />
<cmath>\Rightarrow \frac{2+\sqrt{2}}{2+2\sqrt{2}} \cdot \frac{2-2\sqrt{2}}{2-2\sqrt{2}}</cmath><br />
<cmath>\Rightarrow \frac{-2\sqrt{2}}{-4}</cmath><br />
<cmath>\Rightarrow \boxed{\frac{\sqrt{2}}{2}}</cmath><br />
<br />
~Solution by IronicNinja<br />
<br />
== Solution 3 (Deriving Formulas) ==<br />
<br />
<asy><br />
draw((1, 2.41421356)--(2.41421356, 1)--(2.41421356, -1)--(1, -2.41421356)--(-1, -2.41421356)--(-2.41421356, -1)--(-2.41421356, 1)--(-1, 2.41421356)--cycle);<br />
draw((2.41421356, 1)--(1, -2.41421356)--(-2.41421356, -1)--(-1, 2.41421356)--cycle);<br />
label("A",(-1, 2.41421356),NW);<br />
label("B",(1, 2.41421356),NE);<br />
label("C",(2.41421356, 1),NE);<br />
label("D",(2.41421356, -1),SE);<br />
label("E",(1,-2.41421356),SE);<br />
label("F",(-1,-2.41421356),SW);<br />
label("G",(-2.41421356,-1),SW);<br />
label("H",(-2.41421356,1),NW);<br />
</asy><br />
<br />
The first thing to notice is that <math>ACEG</math> is a square. This is because, as <math>\bigtriangleup ABC \cong \bigtriangleup CDE \cong \bigtriangleup EFG \cong \bigtriangleup GHE</math>, they all have the same base, meaning that <math>AC = DE = EG = GA</math>. Hence, we have that it is a square. To determine the area of this square, we can determine the length of its diagonals.<br />
<br />
In order to do this, we first determine the area of the octagon. Letting the side length be <math>a</math>, we can create a square of length <math>s</math> around it (see figure).<br />
<asy><br />
draw((1, 2.41421356)--(2.41421356, 1)--(2.41421356, -1)--(1, -2.41421356)--(-1, -2.41421356)--(-2.41421356, -1)--(-2.41421356, 1)--(-1, 2.41421356)--cycle);<br />
label("a",(1, 2.41421356)--(2.41421356, 1),S);<br />
draw((-2.41421356, 2.41421356)--(2.41421356, 2.41421356)--(2.41421356, -2.41421356)--(-2.41421356, -2.41421356)--cycle);<br />
label("s",(-2.41421356, 2.41421356)--(2.41421356, 2.41421356),N);<br />
</asy><br />
<br />
Creating a small square of side length <math>a</math> from the corners of this figure gives us an area of <math>a^2</math>. Thus, <math>s^2 - a^2 = n</math> where <math>n</math> is the area of the octagon. We know from the Pythagorean Theorem that <math>s = a + \frac{a}{\sqrt{2}}</math>, meaning that <math>n = (a + \frac{a}{\sqrt{2}})^2 - a^2 = 2a^2(1+\sqrt{2})</math>.<br />
<br />
Dividing this by <math>8</math> gives us the area of each triangular segment which makes up the octagon. Further dividing by <math>2</math> gives us the area of a smaller segment consisting of the right triangle with legs of the apothem and <math>\frac{a}{2}</math>. Using the area of a triangle as <math>\frac{1}{2}bh</math>, we can determine the length of apothem <math>r</math> from<br />
<br />
<cmath>\frac{2a^2(1+\sqrt{2})}{8 \times 2} = \frac{\frac{a}{2}\times r}{2}</cmath><br />
<cmath>\frac{4a^2(1+\sqrt{2})}{8 } = ar</cmath><br />
<cmath>\frac{a(1+\sqrt{2})}{2} = r</cmath>.<br />
<br />
From the apothem, we can once again use the Pythagorean Theorem, giving us the length of the circumradius <math>R</math>.<br />
<br />
<cmath>R^2 = (\frac{a(1+\sqrt{2})}{2})^2 + (\frac{a}{2})^2</cmath><br />
<cmath>R^2 = \frac{a^2(1+\sqrt{2})^2}{4} + \frac{a^2}{4}</cmath><br />
<cmath>R^2 = \frac{a^2(3+2\sqrt{2})}{4} + \frac{a^2}{4}</cmath><br />
<cmath>R^2 = \frac{a^2(4+2\sqrt{2})}{4}</cmath><br />
<cmath>R = \sqrt{\frac{a^2(4+2\sqrt{2})}{4}} = \frac{a\sqrt{4 + 2\sqrt2}}{2}</cmath>.<br />
<br />
Doubling this gives us the diagonal of both the square and the octagon. From here, we can use the formula <math>A = \frac{1}{2}d^2</math> for the area of the square:<br />
<br />
<cmath>A = \frac{(a\sqrt{4 + 2\sqrt2})^2}{2}</cmath><br />
<cmath>A = \frac{a^2(4+2\sqrt{2})}{2} = m</cmath>.<br />
<br />
Thus we now only need to find the ratio <math>\frac{m}{n}</math>. This can be easily done through some algebra:<br />
<br />
<cmath>\frac{m}{n} = \frac{a^2(4+2\sqrt{2})}{2(2a^2(1+\sqrt{2})}</cmath><br />
<cmath>\frac{m}{n} = \frac{4+2\sqrt{2}}{4+4\sqrt{2}}</cmath><br />
<cmath>\frac{m}{n} = \frac{2+\sqrt{2}}{2+2\sqrt{2}}</cmath><br />
<br />
Rationalizing the denominator by multiplying by the conjugate, we get <math>\frac{m}{n} = \boxed{\textbf{(B) } \frac{\sqrt{2}}{2}}</math>. ~ciceronii<br />
<br />
*<math>\textbf{Note:}</math> this can more easily be done if you know any of these formulas. This was an entire derivation of the area of an octagon, it's apothem, and it's circumradius, but it can be much simpler if you have any of these memorized.<br />
<br />
==Solution 3 (Elementary Geometry)==<br />
WLOG, let <math>AE=1</math>. Let the intersection of <math>AF</math> and <math>GD</math> be point <math>I</math>. <math>GIF</math> is an isosceles right triangle (<math>m\angle HGF=135^{\circ}</math>), so <math>IG=IF=\frac{1}{\sqrt{2}}</math>. The distance between each side and the center is then <math>IF+\frac{1}{2}GH=\frac{1}{2}+\frac{1}{\sqrt{2}}</math>. <math>ABCDEFGH</math> is 8 triangles of base 1 and altitude <math>\frac{1}{2}+\frac{1}{\sqrt{2}}</math>, so its area is <math>8(\frac{1}{2})(\frac{1}{2}+\frac{1}{\sqrt{2}})</math> or <br />
<cmath>2+2\sqrt{2}</cmath><br />
Similarly, <math>ACEG</math> is clearly a square of area <math>GA^2</math>. By the Pythagorean Theorem, <math>GA^2=GI^2+IA^2=(\frac{1}{\sqrt{2}})^2+(1+\frac{1}{\sqrt{2}})^2</math> or <br />
<cmath>2+\sqrt{2}</cmath><br />
<cmath>\frac{m}{n} = \frac{2+\sqrt{2}}{2+2\sqrt{2}}</cmath><br />
From some fast manipulations, see that it is <math>\boxed{\textbf{B)}\sqrt{2}{2}}</math><br />
<br />
~~BJHHar<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2020|ab=A|num-b=13|num-a=15}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12A_Problems/Problem_13&diff=1166942020 AMC 12A Problems/Problem 132020-02-03T02:22:31Z<p>Bjhhar: /* Solution 3 */</p>
<hr />
<div>== Problem ==<br />
<br />
There are integers <math>a, b,</math> and <math>c,</math> each greater than <math>1,</math> such that<br />
<br />
<cmath>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}} = \sqrt[36]{N^{25}}</cmath><br />
<br />
for all <math>N > 1</math>. What is <math>b</math>?<br />
<br />
<math>\textbf{(A) } 2 \qquad \textbf{(B) } 3 \qquad \textbf{(C) } 4 \qquad \textbf{(D) } 5 \qquad \textbf{(E) } 6</math><br />
<br />
== Solution ==<br />
<br />
<math>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}}</math> can be simplified to <math>N^{\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}}.</math><br />
<br />
The equation is then <math>N^{\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}}=N^{\frac{25}{36}}</math> which implies that <math>\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}=\frac{25}{36}.</math><br />
<br />
<math>a</math> has to be <math>2</math> since <math>\frac{25}{36}>\frac{7}{12}</math>. <math>\frac{7}{12}</math> is the result when <math>a, b,</math> and <math>c</math> are <math>3, 2,</math> and <math>2</math> <br />
<br />
<math>b</math> being <math>3</math> will make the fraction <math>\frac{2}{3}</math> which is close to <math>\frac{25}{36}</math>. <br />
<br />
Finally, with <math>c</math> being <math>6</math>, the fraction becomes <math>\frac{25}{36}</math>. In this case <math>a, b,</math> and <math>c</math> work, which means that <math>b</math> must equal <math>\boxed{\textbf{(B) } 3.}</math>~lopkiloinm<br />
<br />
== Solution 2 ==<br />
<br />
As above, notice that you get <math>\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}=\frac{25}{36}.</math> <br />
<br />
Now, combine the fractions to get <math>\frac{bc+c+1}{abc}=\frac{25}{36}</math>.<br />
<br />
Assume that <math>bc+c+1=25</math> and <math>abc=36</math>.<br />
<br />
From the first equation we get <math>c(b+1)=24</math>. Note also that from the second equation, <math>b</math> and <math>c</math> must both be factors of 36.<br />
<br />
After some casework we find that <math>c=6</math> and <math>b=3</math> works, with <math>a=2</math>. So our answer is <math>\boxed{\textbf{(B) } 3.}</math><br />
<br />
~Silverdragon<br />
<br />
== Solution 3 ==<br />
Collapsed, <math>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}} = \sqrt[abc]{N^{bc+c+1}}</math>. Comparing this to <math>\sqrt[36]{N^{25}}</math>, observe that <math>bc+c+1=25</math> and <math>abc=36</math>. The first can be rewritten as <math>c(b+1)=24</math>. Then, <math>b+1</math> has to factor into 24 while 1 less than that also must factor into 36. The prime factorizations are as follows <math>36=2^2 3^2</math> and <math>24=2^33</math>. Then, <math>b=\boxed{\textbf{D)}3}</math>, as only 4 and 3 factor into 36 and 24 while being 1 apart.<br />
<br />
(b=1 technically works but I don't care. a,b,c>1 as in the question)<br />
<br />
~~BJHHar<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2020|ab=A|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12A_Problems/Problem_13&diff=1166932020 AMC 12A Problems/Problem 132020-02-03T02:21:06Z<p>Bjhhar: /* Solution 3 */</p>
<hr />
<div>== Problem ==<br />
<br />
There are integers <math>a, b,</math> and <math>c,</math> each greater than <math>1,</math> such that<br />
<br />
<cmath>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}} = \sqrt[36]{N^{25}}</cmath><br />
<br />
for all <math>N > 1</math>. What is <math>b</math>?<br />
<br />
<math>\textbf{(A) } 2 \qquad \textbf{(B) } 3 \qquad \textbf{(C) } 4 \qquad \textbf{(D) } 5 \qquad \textbf{(E) } 6</math><br />
<br />
== Solution ==<br />
<br />
<math>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}}</math> can be simplified to <math>N^{\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}}.</math><br />
<br />
The equation is then <math>N^{\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}}=N^{\frac{25}{36}}</math> which implies that <math>\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}=\frac{25}{36}.</math><br />
<br />
<math>a</math> has to be <math>2</math> since <math>\frac{25}{36}>\frac{7}{12}</math>. <math>\frac{7}{12}</math> is the result when <math>a, b,</math> and <math>c</math> are <math>3, 2,</math> and <math>2</math> <br />
<br />
<math>b</math> being <math>3</math> will make the fraction <math>\frac{2}{3}</math> which is close to <math>\frac{25}{36}</math>. <br />
<br />
Finally, with <math>c</math> being <math>6</math>, the fraction becomes <math>\frac{25}{36}</math>. In this case <math>a, b,</math> and <math>c</math> work, which means that <math>b</math> must equal <math>\boxed{\textbf{(B) } 3.}</math>~lopkiloinm<br />
<br />
== Solution 2 ==<br />
<br />
As above, notice that you get <math>\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}=\frac{25}{36}.</math> <br />
<br />
Now, combine the fractions to get <math>\frac{bc+c+1}{abc}=\frac{25}{36}</math>.<br />
<br />
Assume that <math>bc+c+1=25</math> and <math>abc=36</math>.<br />
<br />
From the first equation we get <math>c(b+1)=24</math>. Note also that from the second equation, <math>b</math> and <math>c</math> must both be factors of 36.<br />
<br />
After some casework we find that <math>c=6</math> and <math>b=3</math> works, with <math>a=2</math>. So our answer is <math>\boxed{\textbf{(B) } 3.}</math><br />
<br />
~Silverdragon<br />
<br />
== Solution 3 ==<br />
Collapsed, <math>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}} = \sqrt[abc]{N^{bc+c+1}</math>. Comparing this to <math>\sqrt[36]{N^{25}}</math>, observe that <math>bc+c+1=25</math> and <math>abc=36</math>. The first can be rewritten as <math>c(b+1)=24</math>. Then, <math>b+1</math> has to factor into 24 while 1 less than that also must factor into 36. The prime factorizations are as follows <math>36=2^2 3^2</math> and <math>24=2^33</math>. Then, <math>b=\boxed{\textbf{D)}3</math>, as only 4 and 3 factor into 36 and 24 while being 1 apart.<br />
<br />
(b=1 technically works but I don't care. a,b,c>1 as in the question)<br />
<br />
~~BJHHar<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2020|ab=A|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12A_Problems/Problem_13&diff=1166922020 AMC 12A Problems/Problem 132020-02-03T02:20:52Z<p>Bjhhar: </p>
<hr />
<div>== Problem ==<br />
<br />
There are integers <math>a, b,</math> and <math>c,</math> each greater than <math>1,</math> such that<br />
<br />
<cmath>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}} = \sqrt[36]{N^{25}}</cmath><br />
<br />
for all <math>N > 1</math>. What is <math>b</math>?<br />
<br />
<math>\textbf{(A) } 2 \qquad \textbf{(B) } 3 \qquad \textbf{(C) } 4 \qquad \textbf{(D) } 5 \qquad \textbf{(E) } 6</math><br />
<br />
== Solution ==<br />
<br />
<math>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}}</math> can be simplified to <math>N^{\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}}.</math><br />
<br />
The equation is then <math>N^{\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}}=N^{\frac{25}{36}}</math> which implies that <math>\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}=\frac{25}{36}.</math><br />
<br />
<math>a</math> has to be <math>2</math> since <math>\frac{25}{36}>\frac{7}{12}</math>. <math>\frac{7}{12}</math> is the result when <math>a, b,</math> and <math>c</math> are <math>3, 2,</math> and <math>2</math> <br />
<br />
<math>b</math> being <math>3</math> will make the fraction <math>\frac{2}{3}</math> which is close to <math>\frac{25}{36}</math>. <br />
<br />
Finally, with <math>c</math> being <math>6</math>, the fraction becomes <math>\frac{25}{36}</math>. In this case <math>a, b,</math> and <math>c</math> work, which means that <math>b</math> must equal <math>\boxed{\textbf{(B) } 3.}</math>~lopkiloinm<br />
<br />
== Solution 2 ==<br />
<br />
As above, notice that you get <math>\frac{1}{a}+\frac{1}{ab}+\frac{1}{abc}=\frac{25}{36}.</math> <br />
<br />
Now, combine the fractions to get <math>\frac{bc+c+1}{abc}=\frac{25}{36}</math>.<br />
<br />
Assume that <math>bc+c+1=25</math> and <math>abc=36</math>.<br />
<br />
From the first equation we get <math>c(b+1)=24</math>. Note also that from the second equation, <math>b</math> and <math>c</math> must both be factors of 36.<br />
<br />
After some casework we find that <math>c=6</math> and <math>b=3</math> works, with <math>a=2</math>. So our answer is <math>\boxed{\textbf{(B) } 3.}</math><br />
<br />
~Silverdragon<br />
<br />
== Solution 3 ==<br />
Collapsed, <math></math>\sqrt[a]{N\sqrt[b]{N\sqrt[c]{N}}} = \sqrt[abc]{N^{bc+c+1}<math>. Comparing this to </math>\sqrt[36]{N^{25}}<math>, observe that </math>bc+c+1=25<math> and </math>abc=36<math>. The first can be rewritten as </math>c(b+1)=24<math>. Then, </math>b+1<math> has to factor into 24 while 1 less than that also must factor into 36. The prime factorizations are as follows </math>36=2^2 3^2<math> and </math>24=2^33<math>. Then, </math>b=\boxed{\textbf{D)}3$, as only 4 and 3 factor into 36 and 24 while being 1 apart.<br />
<br />
(b=1 technically works but I don't care. a,b,c>1 as in the question)<br />
<br />
~~BJHHar<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2020|ab=A|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2011_AMC_12B_Problems/Problem_17&diff=1157072011 AMC 12B Problems/Problem 172020-01-27T23:38:51Z<p>Bjhhar: /* Solution 2 (Quick, Non-Rigorous Trends) */</p>
<hr />
<div>==Problem==<br />
Let <math>f(x) = 10^{10x}, g(x) = \log_{10}\left(\frac{x}{10}\right), h_1(x) = g(f(x))</math>, and <math>h_n(x) = h_1(h_{n-1}(x))</math> for integers <math>n \geq 2</math>. What is the sum of the digits of <math>h_{2011}(1)</math>?<br />
<br />
<math>\textbf{(A)}\ 16081 \qquad \textbf{(B)}\ 16089 \qquad \textbf{(C)}\ 18089 \qquad \textbf{(D)}\ 18098 \qquad \textbf{(E)}\ 18099</math><br />
<br />
==Solution==<br />
<br />
<math>g(x)=\log_{10}\left(\frac{x}{10}\right)=\log_{10}\left({x}\right) - 1</math><br />
<br />
<math>h_{1}(x)=g(f(x))\text{ = }g(10^{10x}=\log_{10}\left({10^{10x}}\right){ - 1 = 10x - 1}</math><br />
<br />
Proof by induction that <math>h_{n}(x)\text{ = }10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math>:<br />
<br />
For <math>n=1</math>, <math>h_{1}(x)=10x - 1</math><br />
<br />
Assume <math>h_{n}(x)=10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math> is true for n:<br />
<br />
<cmath>\begin{align*}<br />
h_{n+1}(x)&= h_{1}(h_{n}(x))\\<br />
&=10 h_{n}(x) - 1\\<br />
&=10 (10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})) - 1\\<br />
&= 10^{n+1} x - (10 + 10^2 + ... + 10^{n}) - 1\\<br />
&= 10^{n+1} x - (1 + 10 + 10^2 + ... + 10^{(n+1)-1})<br />
\end{align*}</cmath><br />
<br />
Therefore, if it is true for n, then it is true for n+1; since it is also true for n = 1, it is true for all positive integers n.<br />
<br />
<math>h_{2011}(1) = 10^{2011}\times 1{ - }(1 + 10 + 10^2 + ... + 10^{2010})</math>, which is the 2011-digit number 8888...8889<br />
<br />
The sum of the digits is 8 times 2010 plus 9, or <math>\boxed{16089\textbf{(B)}}</math><br />
<br />
==Solution 2 (Quick, Non-Rigorous Trends)==<br />
As before, <math>h_1(x)=10x-1</math>. Compute <math>h_1(x)</math>, <math>h_2(x)</math>, and <math>h_3(x)</math> to yield 9, 89, and 889. Notice how this trend will evidently repeat this trend (multiply by 10, subtract 1, repeat). As such, <math>h_{2011}</math> is just 2010 8's followed by a nine. <math>2010(8)+9=\boxed{\textbf{B)}16089}</math>.<br />
<br />
~~BJHHar<br />
<br />
== See also ==<br />
{{AMC12 box|year=2011|num-b=16|num-a=18|ab=B}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2011_AMC_12B_Problems/Problem_17&diff=1157062011 AMC 12B Problems/Problem 172020-01-27T23:38:30Z<p>Bjhhar: /* Solution 2 (Quick, Non-Rigorous Trends) */</p>
<hr />
<div>==Problem==<br />
Let <math>f(x) = 10^{10x}, g(x) = \log_{10}\left(\frac{x}{10}\right), h_1(x) = g(f(x))</math>, and <math>h_n(x) = h_1(h_{n-1}(x))</math> for integers <math>n \geq 2</math>. What is the sum of the digits of <math>h_{2011}(1)</math>?<br />
<br />
<math>\textbf{(A)}\ 16081 \qquad \textbf{(B)}\ 16089 \qquad \textbf{(C)}\ 18089 \qquad \textbf{(D)}\ 18098 \qquad \textbf{(E)}\ 18099</math><br />
<br />
==Solution==<br />
<br />
<math>g(x)=\log_{10}\left(\frac{x}{10}\right)=\log_{10}\left({x}\right) - 1</math><br />
<br />
<math>h_{1}(x)=g(f(x))\text{ = }g(10^{10x}=\log_{10}\left({10^{10x}}\right){ - 1 = 10x - 1}</math><br />
<br />
Proof by induction that <math>h_{n}(x)\text{ = }10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math>:<br />
<br />
For <math>n=1</math>, <math>h_{1}(x)=10x - 1</math><br />
<br />
Assume <math>h_{n}(x)=10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math> is true for n:<br />
<br />
<cmath>\begin{align*}<br />
h_{n+1}(x)&= h_{1}(h_{n}(x))\\<br />
&=10 h_{n}(x) - 1\\<br />
&=10 (10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})) - 1\\<br />
&= 10^{n+1} x - (10 + 10^2 + ... + 10^{n}) - 1\\<br />
&= 10^{n+1} x - (1 + 10 + 10^2 + ... + 10^{(n+1)-1})<br />
\end{align*}</cmath><br />
<br />
Therefore, if it is true for n, then it is true for n+1; since it is also true for n = 1, it is true for all positive integers n.<br />
<br />
<math>h_{2011}(1) = 10^{2011}\times 1{ - }(1 + 10 + 10^2 + ... + 10^{2010})</math>, which is the 2011-digit number 8888...8889<br />
<br />
The sum of the digits is 8 times 2010 plus 9, or <math>\boxed{16089\textbf{(B)}}</math><br />
<br />
==Solution 2 (Quick, Non-Rigorous Trends)==<br />
As before, <math>h_1(x)=10x-1</math>. Compute <math>h_1(x)</math>, <math>h_2(x)</math>, and <math>h_3(x)</math> to yield 9, 89, and 889. Notice how this trend will evidently repeat this trend (multiply by 10, subtract 1, repeat). As such, <math>h_2011</math> is just 2010 8's followed by a nine. <math>2010(8)+9=\boxed{\textbf{B)}16089}</math>.<br />
<br />
~~BJHHar<br />
<br />
== See also ==<br />
{{AMC12 box|year=2011|num-b=16|num-a=18|ab=B}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2011_AMC_12B_Problems/Problem_17&diff=1157052011 AMC 12B Problems/Problem 172020-01-27T23:37:39Z<p>Bjhhar: /* Solution 2 (Non-Rigorous Trends) */</p>
<hr />
<div>==Problem==<br />
Let <math>f(x) = 10^{10x}, g(x) = \log_{10}\left(\frac{x}{10}\right), h_1(x) = g(f(x))</math>, and <math>h_n(x) = h_1(h_{n-1}(x))</math> for integers <math>n \geq 2</math>. What is the sum of the digits of <math>h_{2011}(1)</math>?<br />
<br />
<math>\textbf{(A)}\ 16081 \qquad \textbf{(B)}\ 16089 \qquad \textbf{(C)}\ 18089 \qquad \textbf{(D)}\ 18098 \qquad \textbf{(E)}\ 18099</math><br />
<br />
==Solution==<br />
<br />
<math>g(x)=\log_{10}\left(\frac{x}{10}\right)=\log_{10}\left({x}\right) - 1</math><br />
<br />
<math>h_{1}(x)=g(f(x))\text{ = }g(10^{10x}=\log_{10}\left({10^{10x}}\right){ - 1 = 10x - 1}</math><br />
<br />
Proof by induction that <math>h_{n}(x)\text{ = }10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math>:<br />
<br />
For <math>n=1</math>, <math>h_{1}(x)=10x - 1</math><br />
<br />
Assume <math>h_{n}(x)=10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math> is true for n:<br />
<br />
<cmath>\begin{align*}<br />
h_{n+1}(x)&= h_{1}(h_{n}(x))\\<br />
&=10 h_{n}(x) - 1\\<br />
&=10 (10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})) - 1\\<br />
&= 10^{n+1} x - (10 + 10^2 + ... + 10^{n}) - 1\\<br />
&= 10^{n+1} x - (1 + 10 + 10^2 + ... + 10^{(n+1)-1})<br />
\end{align*}</cmath><br />
<br />
Therefore, if it is true for n, then it is true for n+1; since it is also true for n = 1, it is true for all positive integers n.<br />
<br />
<math>h_{2011}(1) = 10^{2011}\times 1{ - }(1 + 10 + 10^2 + ... + 10^{2010})</math>, which is the 2011-digit number 8888...8889<br />
<br />
The sum of the digits is 8 times 2010 plus 9, or <math>\boxed{16089\textbf{(B)}}</math><br />
<br />
==Solution 2 (Quick, Non-Rigorous Trends)==<br />
As before, <math>h_1(x)=10x-1</math>. Compute <math>h_1</math>, <math>h_2</math>, and <math>h_3</math> for <math>x=1</math> to yield 9, 89, and 889. Notice how this trend will evidently repeat this trend (multiply by 10, subtract 1, repeat). As such, <math>h_2011</math> is just 2010 8's followed by a nine. <math>2010(8)+9=\boxed{\textbf{B)}16089}</math>.<br />
<br />
~~BJHHar<br />
<br />
== See also ==<br />
{{AMC12 box|year=2011|num-b=16|num-a=18|ab=B}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2011_AMC_12B_Problems/Problem_17&diff=1157042011 AMC 12B Problems/Problem 172020-01-27T23:37:25Z<p>Bjhhar: /* Solution 2 (Non-Rigorous Trends) */</p>
<hr />
<div>==Problem==<br />
Let <math>f(x) = 10^{10x}, g(x) = \log_{10}\left(\frac{x}{10}\right), h_1(x) = g(f(x))</math>, and <math>h_n(x) = h_1(h_{n-1}(x))</math> for integers <math>n \geq 2</math>. What is the sum of the digits of <math>h_{2011}(1)</math>?<br />
<br />
<math>\textbf{(A)}\ 16081 \qquad \textbf{(B)}\ 16089 \qquad \textbf{(C)}\ 18089 \qquad \textbf{(D)}\ 18098 \qquad \textbf{(E)}\ 18099</math><br />
<br />
==Solution==<br />
<br />
<math>g(x)=\log_{10}\left(\frac{x}{10}\right)=\log_{10}\left({x}\right) - 1</math><br />
<br />
<math>h_{1}(x)=g(f(x))\text{ = }g(10^{10x}=\log_{10}\left({10^{10x}}\right){ - 1 = 10x - 1}</math><br />
<br />
Proof by induction that <math>h_{n}(x)\text{ = }10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math>:<br />
<br />
For <math>n=1</math>, <math>h_{1}(x)=10x - 1</math><br />
<br />
Assume <math>h_{n}(x)=10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math> is true for n:<br />
<br />
<cmath>\begin{align*}<br />
h_{n+1}(x)&= h_{1}(h_{n}(x))\\<br />
&=10 h_{n}(x) - 1\\<br />
&=10 (10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})) - 1\\<br />
&= 10^{n+1} x - (10 + 10^2 + ... + 10^{n}) - 1\\<br />
&= 10^{n+1} x - (1 + 10 + 10^2 + ... + 10^{(n+1)-1})<br />
\end{align*}</cmath><br />
<br />
Therefore, if it is true for n, then it is true for n+1; since it is also true for n = 1, it is true for all positive integers n.<br />
<br />
<math>h_{2011}(1) = 10^{2011}\times 1{ - }(1 + 10 + 10^2 + ... + 10^{2010})</math>, which is the 2011-digit number 8888...8889<br />
<br />
The sum of the digits is 8 times 2010 plus 9, or <math>\boxed{16089\textbf{(B)}}</math><br />
<br />
==Solution 2 (Non-Rigorous Trends)==<br />
As before, <math>h_1(x)=10x-1</math>. Compute <math>h_1</math>, <math>h_2</math>, and <math>h_3</math> for <math>x=1</math> to yield 9, 89, and 889. Notice how this trend will evidently repeat this trend (multiply by 10, subtract 1, repeat). As such, <math>h_2011</math> is just 2010 8's followed by a nine. <math>2010(8)+9=\boxed{\textbf{B)}16089}</math>.<br />
<br />
~~BJHHar<br />
<br />
== See also ==<br />
{{AMC12 box|year=2011|num-b=16|num-a=18|ab=B}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2011_AMC_12B_Problems/Problem_17&diff=1157032011 AMC 12B Problems/Problem 172020-01-27T23:36:26Z<p>Bjhhar: </p>
<hr />
<div>==Problem==<br />
Let <math>f(x) = 10^{10x}, g(x) = \log_{10}\left(\frac{x}{10}\right), h_1(x) = g(f(x))</math>, and <math>h_n(x) = h_1(h_{n-1}(x))</math> for integers <math>n \geq 2</math>. What is the sum of the digits of <math>h_{2011}(1)</math>?<br />
<br />
<math>\textbf{(A)}\ 16081 \qquad \textbf{(B)}\ 16089 \qquad \textbf{(C)}\ 18089 \qquad \textbf{(D)}\ 18098 \qquad \textbf{(E)}\ 18099</math><br />
<br />
==Solution==<br />
<br />
<math>g(x)=\log_{10}\left(\frac{x}{10}\right)=\log_{10}\left({x}\right) - 1</math><br />
<br />
<math>h_{1}(x)=g(f(x))\text{ = }g(10^{10x}=\log_{10}\left({10^{10x}}\right){ - 1 = 10x - 1}</math><br />
<br />
Proof by induction that <math>h_{n}(x)\text{ = }10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math>:<br />
<br />
For <math>n=1</math>, <math>h_{1}(x)=10x - 1</math><br />
<br />
Assume <math>h_{n}(x)=10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})</math> is true for n:<br />
<br />
<cmath>\begin{align*}<br />
h_{n+1}(x)&= h_{1}(h_{n}(x))\\<br />
&=10 h_{n}(x) - 1\\<br />
&=10 (10^n x - (1 + 10 + 10^2 + ... + 10^{n-1})) - 1\\<br />
&= 10^{n+1} x - (10 + 10^2 + ... + 10^{n}) - 1\\<br />
&= 10^{n+1} x - (1 + 10 + 10^2 + ... + 10^{(n+1)-1})<br />
\end{align*}</cmath><br />
<br />
Therefore, if it is true for n, then it is true for n+1; since it is also true for n = 1, it is true for all positive integers n.<br />
<br />
<math>h_{2011}(1) = 10^{2011}\times 1{ - }(1 + 10 + 10^2 + ... + 10^{2010})</math>, which is the 2011-digit number 8888...8889<br />
<br />
The sum of the digits is 8 times 2010 plus 9, or <math>\boxed{16089\textbf{(B)}}</math><br />
<br />
==Solution 2 (Non-Rigorous Trends)==<br />
As before, combine the functions to see that <math>h_1(x)=10x-1</math>. Compute <math>h_1</math>, <math>h_2</math>, and <math>h_3</math> for <math>x=1</math> to yield 9, 89, and 889. In computing, notice how this trend will evidently continue, because it repeats (multiply by 10 and subtract 1. Multiply by 10 and subtract 1. And so forth). As such, <math>h_2011</math> is 2010 8's followed by a nine. <math>2010(8)+9=\boxed{\textbf{B)}16089}</math>.<br />
<br />
~~BJHHar<br />
<br />
<br />
== See also ==<br />
{{AMC12 box|year=2011|num-b=16|num-a=18|ab=B}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_18&diff=1150192012 AMC 12B Problems/Problem 182020-01-20T04:49:16Z<p>Bjhhar: /* Solution 2 */</p>
<hr />
<div>== Problem 18 ==<br />
<br />
Let <math>(a_1,a_2, \dots ,a_{10})</math> be a list of the first 10 positive integers such that for each <math>2 \le i \le 10</math> either <math>a_i+1</math> or <math>a_i-1</math> or both appear somewhere before <math>a_i</math> in the list. How many such lists are there?<br />
<br />
<math>\textbf{(A)}\ 120\qquad\textbf{(B)}\ 512\qquad\textbf{(C)}\ 1024\qquad\textbf{(D)}\ 181,440\qquad\textbf{(E)}\ 362,880</math><br />
<br />
== Solution 1==<br />
Let <math>1\leq k\leq 10</math>. Assume that <math>a_1=k</math>. If <math>k<10</math>, the first number appear after <math>k</math> that is greater than <math>k</math> must be <math>k+1</math>, otherwise if it is any number <math>x</math> larger than <math>k+1</math>, there will be neither <math>x-1</math> nor <math>x+1</math> appearing before <math>x</math>. Similarly, one can conclude that if <math>k+1<10</math>, the first number appear after <math>k+1</math> that is larger than <math>k+1</math> must be <math>k+2</math>, and so forth.<br />
<br />
On the other hand, if <math>k>1</math>, the first number appear after <math>k</math> that is less than <math>k</math> must be <math>k-1</math>, and then <math>k-2</math>, and so forth.<br />
<br />
To count the number of possibilities when <math>a_1=k</math> is given, we set up <math>9</math> spots after <math>k</math>, and assign <math>k-1</math> of them to the numbers less than <math>k</math> and the rest to the numbers greater than <math>k</math>. The number of ways in doing so is <math>9</math> choose <math>k-1</math>.<br />
<br />
Therefore, when summing up the cases from <math>k=1</math> to <math>10</math>, we get<br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512 ...... \framebox{B}</cmath><br />
<br />
== Solution 2==<br />
This problem is worded awkwardly. More simply, it asks: “How many ways can you order numbers 1-10 so that each number is one above or below some previous term?”<br />
<br />
<br />
Then, the method becomes clear. For some initial number, WLOG examine the numbers greater than it. They always must appear in ascending order later in the list, though not necessarily as adjacent terms. Then, for some initial number, the number of possible lists is just the number of combination where this number of terms can be placed in 9 slots. For 9, that’s 1 number in 9 potential slots. For 8, that’s 2 numbers in 9 potential slots. <br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} =512 \implies \boxed{B}</cmath><br />
<br />
~~BJHHar<br />
<br />
== Solution 3 (Noticing Stuff)==<br />
If there is only 1 number, the number of ways to order would be 1.<br />
If there are 2 numbers, the number of ways to order would be 2.<br />
If there are 3 numbers, by listing out, the number of ways is 4.<br />
We can then make a conjecture that the problem is simply powers of 2. <br />
<math>2^{10-1}=512</math>.<br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2012|ab=B|num-b=17|num-a=19}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_18&diff=1150182012 AMC 12B Problems/Problem 182020-01-20T04:48:37Z<p>Bjhhar: /* Solution 2 */</p>
<hr />
<div>== Problem 18 ==<br />
<br />
Let <math>(a_1,a_2, \dots ,a_{10})</math> be a list of the first 10 positive integers such that for each <math>2 \le i \le 10</math> either <math>a_i+1</math> or <math>a_i-1</math> or both appear somewhere before <math>a_i</math> in the list. How many such lists are there?<br />
<br />
<math>\textbf{(A)}\ 120\qquad\textbf{(B)}\ 512\qquad\textbf{(C)}\ 1024\qquad\textbf{(D)}\ 181,440\qquad\textbf{(E)}\ 362,880</math><br />
<br />
== Solution 1==<br />
Let <math>1\leq k\leq 10</math>. Assume that <math>a_1=k</math>. If <math>k<10</math>, the first number appear after <math>k</math> that is greater than <math>k</math> must be <math>k+1</math>, otherwise if it is any number <math>x</math> larger than <math>k+1</math>, there will be neither <math>x-1</math> nor <math>x+1</math> appearing before <math>x</math>. Similarly, one can conclude that if <math>k+1<10</math>, the first number appear after <math>k+1</math> that is larger than <math>k+1</math> must be <math>k+2</math>, and so forth.<br />
<br />
On the other hand, if <math>k>1</math>, the first number appear after <math>k</math> that is less than <math>k</math> must be <math>k-1</math>, and then <math>k-2</math>, and so forth.<br />
<br />
To count the number of possibilities when <math>a_1=k</math> is given, we set up <math>9</math> spots after <math>k</math>, and assign <math>k-1</math> of them to the numbers less than <math>k</math> and the rest to the numbers greater than <math>k</math>. The number of ways in doing so is <math>9</math> choose <math>k-1</math>.<br />
<br />
Therefore, when summing up the cases from <math>k=1</math> to <math>10</math>, we get<br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512 ...... \framebox{B}</cmath><br />
<br />
== Solution 2==<br />
This problem is worded awkwardly. More simply, it asks: “How many ways can you order numbers 1-10 so that each number is one above or below some previous term?”<br />
<br />
<br />
Then, the method becomes clear. For some initial number, WLOG examine the numbers greater than it. They always must appear in ascending order later in the list, though not necessarily as adjacent terms. Then, for some initial number, the number of possible lists is just the number of combination where this number of terms can be placed in 9 slots. For 9, that’s 1 number in 9 potential slots. For 8, that’s 2 numbers in 9 potential slots. <br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} =512 ... \boxed{B}</cmath><br />
<br />
~~BJHHar<br />
<br />
== Solution 3 (Noticing Stuff)==<br />
If there is only 1 number, the number of ways to order would be 1.<br />
If there are 2 numbers, the number of ways to order would be 2.<br />
If there are 3 numbers, by listing out, the number of ways is 4.<br />
We can then make a conjecture that the problem is simply powers of 2. <br />
<math>2^{10-1}=512</math>.<br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2012|ab=B|num-b=17|num-a=19}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_18&diff=1150172012 AMC 12B Problems/Problem 182020-01-20T04:47:08Z<p>Bjhhar: /* Solution 2 */</p>
<hr />
<div>== Problem 18 ==<br />
<br />
Let <math>(a_1,a_2, \dots ,a_{10})</math> be a list of the first 10 positive integers such that for each <math>2 \le i \le 10</math> either <math>a_i+1</math> or <math>a_i-1</math> or both appear somewhere before <math>a_i</math> in the list. How many such lists are there?<br />
<br />
<math>\textbf{(A)}\ 120\qquad\textbf{(B)}\ 512\qquad\textbf{(C)}\ 1024\qquad\textbf{(D)}\ 181,440\qquad\textbf{(E)}\ 362,880</math><br />
<br />
== Solution 1==<br />
Let <math>1\leq k\leq 10</math>. Assume that <math>a_1=k</math>. If <math>k<10</math>, the first number appear after <math>k</math> that is greater than <math>k</math> must be <math>k+1</math>, otherwise if it is any number <math>x</math> larger than <math>k+1</math>, there will be neither <math>x-1</math> nor <math>x+1</math> appearing before <math>x</math>. Similarly, one can conclude that if <math>k+1<10</math>, the first number appear after <math>k+1</math> that is larger than <math>k+1</math> must be <math>k+2</math>, and so forth.<br />
<br />
On the other hand, if <math>k>1</math>, the first number appear after <math>k</math> that is less than <math>k</math> must be <math>k-1</math>, and then <math>k-2</math>, and so forth.<br />
<br />
To count the number of possibilities when <math>a_1=k</math> is given, we set up <math>9</math> spots after <math>k</math>, and assign <math>k-1</math> of them to the numbers less than <math>k</math> and the rest to the numbers greater than <math>k</math>. The number of ways in doing so is <math>9</math> choose <math>k-1</math>.<br />
<br />
Therefore, when summing up the cases from <math>k=1</math> to <math>10</math>, we get<br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512 ...... \framebox{B}</cmath><br />
<br />
== Solution 2==<br />
This problem is worded awkwardly. More simply, it asks: “How many ways can you order numbers 1-10 so that each number is one above or below some previous term?”<br />
<br />
<br />
Then, the method becomes clear. For some initial number, WLOG examine the numbers greater than it. They always must appear in ascending order later in the list, only separated by the other numbers below it. Then, for some initial number, the number of possible lists is just the number of combination where this number of terms can be placed in 9 slots. For 9, that’s 1 number in 9 potential slots. For 8, that’s 2 numbers in 9 potential slots. <br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} =512 ... \boxed{B}</cmath><br />
<br />
~~BJHHar<br />
<br />
== Solution 3 (Noticing Stuff)==<br />
If there is only 1 number, the number of ways to order would be 1.<br />
If there are 2 numbers, the number of ways to order would be 2.<br />
If there are 3 numbers, by listing out, the number of ways is 4.<br />
We can then make a conjecture that the problem is simply powers of 2. <br />
<math>2^{10-1}=512</math>.<br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2012|ab=B|num-b=17|num-a=19}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_18&diff=1150162012 AMC 12B Problems/Problem 182020-01-20T04:46:31Z<p>Bjhhar: </p>
<hr />
<div>== Problem 18 ==<br />
<br />
Let <math>(a_1,a_2, \dots ,a_{10})</math> be a list of the first 10 positive integers such that for each <math>2 \le i \le 10</math> either <math>a_i+1</math> or <math>a_i-1</math> or both appear somewhere before <math>a_i</math> in the list. How many such lists are there?<br />
<br />
<math>\textbf{(A)}\ 120\qquad\textbf{(B)}\ 512\qquad\textbf{(C)}\ 1024\qquad\textbf{(D)}\ 181,440\qquad\textbf{(E)}\ 362,880</math><br />
<br />
== Solution 1==<br />
Let <math>1\leq k\leq 10</math>. Assume that <math>a_1=k</math>. If <math>k<10</math>, the first number appear after <math>k</math> that is greater than <math>k</math> must be <math>k+1</math>, otherwise if it is any number <math>x</math> larger than <math>k+1</math>, there will be neither <math>x-1</math> nor <math>x+1</math> appearing before <math>x</math>. Similarly, one can conclude that if <math>k+1<10</math>, the first number appear after <math>k+1</math> that is larger than <math>k+1</math> must be <math>k+2</math>, and so forth.<br />
<br />
On the other hand, if <math>k>1</math>, the first number appear after <math>k</math> that is less than <math>k</math> must be <math>k-1</math>, and then <math>k-2</math>, and so forth.<br />
<br />
To count the number of possibilities when <math>a_1=k</math> is given, we set up <math>9</math> spots after <math>k</math>, and assign <math>k-1</math> of them to the numbers less than <math>k</math> and the rest to the numbers greater than <math>k</math>. The number of ways in doing so is <math>9</math> choose <math>k-1</math>.<br />
<br />
Therefore, when summing up the cases from <math>k=1</math> to <math>10</math>, we get<br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} = 2^9=512 ...... \framebox{B}</cmath><br />
<br />
== Solution 2==<br />
This problem is worded awkwardly. More simply, it asks: “How many ways can you order numbers 1-10 so that each term greater than 1 is one above or below some previous term?”<br />
<br />
<br />
Then, the method becomes clear. For some initial number, WLOG examine the numbers greater than it. They always must appear in ascending order later in the list, only separated by the other numbers below it. Then, for some initial number, the number of possible lists is just the number of combination where this number of terms can be placed in 9 slots. For 9, that’s 1 number in 9 potential slots. For 8, that’s 2 numbers in 9 potential slots. <br />
<br />
<cmath>\binom{9}{0} + \binom{9}{1} + \cdots + \binom{9}{9} =512 ... \boxed{B}</cmath><br />
<br />
~~BJHHar<br />
<br />
<br />
== Solution 3 (Noticing Stuff)==<br />
If there is only 1 number, the number of ways to order would be 1.<br />
If there are 2 numbers, the number of ways to order would be 2.<br />
If there are 3 numbers, by listing out, the number of ways is 4.<br />
We can then make a conjecture that the problem is simply powers of 2. <br />
<math>2^{10-1}=512</math>.<br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2012|ab=B|num-b=17|num-a=19}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2008_AMC_12A_Problems/Problem_11&diff=1146322008 AMC 12A Problems/Problem 112020-01-12T18:24:42Z<p>Bjhhar: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
Three cubes are each formed from the pattern shown. They are then stacked on a table one on top of another so that the <math>13</math> visible numbers have the greatest possible sum. What is that sum?<br />
<br />
<asy><br />
unitsize(.8cm);<br />
<br />
pen p = linewidth(1);<br />
draw(shift(-2,0)*unitsquare,p);<br />
label("1",(-1.5,0.5));<br />
draw(shift(-1,0)*unitsquare,p);<br />
label("2",(-0.5,0.5));<br />
draw(unitsquare,p);<br />
label("32",(0.5,0.5));<br />
draw(shift(1,0)*unitsquare,p);<br />
label("16",(1.5,0.5));<br />
draw(shift(0,1)*unitsquare,p);<br />
label("4",(0.5,1.5));<br />
draw(shift(0,-1)*unitsquare,p);<br />
label("8",(0.5,-0.5));<br />
</asy><br />
<br />
<math>\mathrm{(A)}\ 154\qquad\mathrm{(B)}\ 159\qquad\mathrm{(C)}\ 164\qquad\mathrm{(D)}\ 167\qquad\mathrm{(E)}\ 189</math><br />
<br />
==Solution==<br />
To maximize the sum of the <math>13</math> faces that are showing, we can minimize the sum of the numbers of the <math>5</math> faces that are not showing. <br />
<br />
The bottom <math>2</math> cubes each have a pair of opposite faces that are covered up. When the cube is folded, <math>(1,32)</math>; <math>(2,16)</math>; and <math>(4,8)</math> are opposite pairs. Clearly <math>4+8=12</math> has the smallest sum. <br />
<br />
The top cube has 1 number that is not showing. The smallest number on a face is <math>1</math>. <br />
<br />
So, the minimum sum of the <math>5</math> unexposed faces is <math>2\cdot12+1=25</math>. Since the sum of the numbers on all the cubes is <math>3(32+16+8+4+2+1)=189</math>, the maximum possible sum of <math>13</math> visible numbers is <math>189-25=164 \Rightarrow C</math>. <br />
<br />
==Solution 2==<br />
Conversely, maximize the sum. Two cubes have 4 exposed faces. Since <math>32>16+8+4+2</math>, 32 must be on the side. There are two distinct (asymmetrical) configurations with 32 on the side, but <math>(32,16,2,1)</math> is the greatest at 51. There are 2 such cubes, so 51*2. The top cube has one unexposed face, so use 1 as the unexposed face. <math>2(51)+32+16+8+4+2=164 \implies \boxed{\textbf{C)}164}</math> <br />
<br />
~BJHHar<br />
<br />
==See Also==<br />
{{AMC12 box|year=2008|num-b=10|num-a=12|ab=A}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2008_AMC_12A_Problems/Problem_11&diff=1146312008 AMC 12A Problems/Problem 112020-01-12T18:22:58Z<p>Bjhhar: </p>
<hr />
<div>==Problem==<br />
Three cubes are each formed from the pattern shown. They are then stacked on a table one on top of another so that the <math>13</math> visible numbers have the greatest possible sum. What is that sum?<br />
<br />
<asy><br />
unitsize(.8cm);<br />
<br />
pen p = linewidth(1);<br />
draw(shift(-2,0)*unitsquare,p);<br />
label("1",(-1.5,0.5));<br />
draw(shift(-1,0)*unitsquare,p);<br />
label("2",(-0.5,0.5));<br />
draw(unitsquare,p);<br />
label("32",(0.5,0.5));<br />
draw(shift(1,0)*unitsquare,p);<br />
label("16",(1.5,0.5));<br />
draw(shift(0,1)*unitsquare,p);<br />
label("4",(0.5,1.5));<br />
draw(shift(0,-1)*unitsquare,p);<br />
label("8",(0.5,-0.5));<br />
</asy><br />
<br />
<math>\mathrm{(A)}\ 154\qquad\mathrm{(B)}\ 159\qquad\mathrm{(C)}\ 164\qquad\mathrm{(D)}\ 167\qquad\mathrm{(E)}\ 189</math><br />
<br />
==Solution==<br />
To maximize the sum of the <math>13</math> faces that are showing, we can minimize the sum of the numbers of the <math>5</math> faces that are not showing. <br />
<br />
The bottom <math>2</math> cubes each have a pair of opposite faces that are covered up. When the cube is folded, <math>(1,32)</math>; <math>(2,16)</math>; and <math>(4,8)</math> are opposite pairs. Clearly <math>4+8=12</math> has the smallest sum. <br />
<br />
The top cube has 1 number that is not showing. The smallest number on a face is <math>1</math>. <br />
<br />
So, the minimum sum of the <math>5</math> unexposed faces is <math>2\cdot12+1=25</math>. Since the sum of the numbers on all the cubes is <math>3(32+16+8+4+2+1)=189</math>, the maximum possible sum of <math>13</math> visible numbers is <math>189-25=164 \Rightarrow C</math>. <br />
<br />
==Solution 2==<br />
Conversely, maximize the sum. The first two cubes have 4 numbers out facing. Since <math>32>16+8+4+2</math>, 32 must be on the side. There are two distinct (asymmetrical) configurations with 32 on the side, but <math>(32,16,2,1)</math> is the greatest at 51. There are 2 such cubes, so 51*2. The cube on top only hides 1 number, so simply use 1 as the unexposed face. <math>2(51)+32+16+8+4+2=164implies \boxed{\textbf{C)}164}</math> <br />
<br />
~BJHHar<br />
<br />
==See Also==<br />
{{AMC12 box|year=2008|num-b=10|num-a=12|ab=A}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_13&diff=1145252010 AMC 12A Problems/Problem 132020-01-09T02:56:34Z<p>Bjhhar: /* Solution 4 (Quick) */</p>
<hr />
<div>== Problem ==<br />
For how many integer values of <math>k</math> do the graphs of <math>x^2+y^2=k^2</math> and <math>xy = k</math> not intersect?<br />
<br />
<math>\textbf{(A)}\ 0 \qquad \textbf{(B)}\ 1 \qquad \textbf{(C)}\ 2 \qquad \textbf{(D)}\ 4 \qquad \textbf{(E)}\ 8</math><br />
<br />
== Solution 1==<br />
<br />
The image below shows the two curves for <math>k=4</math>. The blue curve is <math>x^2+y^2=k^2</math>, which is clearly a circle with radius <math>k</math>, and the red curve is a part of the curve <math>xy=k</math>.<br />
<br />
<asy><br />
import graph;<br />
size(200);<br />
<br />
real f(real x) {return 4/x;};<br />
real g1(real x) {return sqrt(4*4-x*x);};<br />
real g2(real x) {return -sqrt(4*4-x*x);};<br />
draw(graph(f,-20./3,-0.6),red);<br />
draw(graph(f,0.6,20./3),red);<br />
draw(graph(g1,-4,4),blue);<br />
draw(graph(g2,-4,4),blue);<br />
axes("$x$","$y$");<br />
</asy><br />
<br />
In the special case <math>k=0</math> the blue curve is just the point <math>(0,0)</math>, and as <math>0\cdot 0=0</math>, this point is on the red curve as well, hence they intersect. <br />
<br />
The case <math>k<0</math> is symmetric to <math>k>0</math>: the blue curve remains the same and the red curve is flipped according to the <math>x</math> axis. Hence we just need to focus on <math>k>0</math>.<br />
<br />
Clearly, on the red curve there will always be points arbitrarily far from the origin: for example, as <math>x</math> approaches 0, <math>y</math> approaches <math>\infty</math>. Hence the red curve intersects the blue one if and only if it contains a point whose distance from the origin is at most <math>k</math>.<br />
<br />
<br />
At this point we can guess that on the red curve the point where <math>x=y</math> is always closest to the origin, and skip the rest of this solution.<br />
<br />
<br />
For an exact solution, fix <math>k</math> and consider any point <math>(x,y)</math> on the red curve. Its distance from the origin is <math>\sqrt{ x^2 + (k/x)^2 }</math>. To minimize this distance, it is enough to minimize <math>x^2 + (k/x)^2</math>. By the [[Arithmetic Mean-Geometric Mean Inequality]] we get that this value is at least <math>2k</math>, and that equality holds whenever <math>x^2 = (k/x)^2</math>, i.e., <math>x=\pm\sqrt k</math>.<br />
<br />
<br />
Now recall that the red curve intersects the blue one if and only if its closest point is at most <math>k</math> from the origin. We just computed that the distance between the origin and the closest point on the red curve is <math>\sqrt{2k}</math>. Therefore, we want to find all positive integers <math>k</math> such that <math>\sqrt{2k} > k</math>.<br />
<br />
Clearly the only such integer is <math>k=1</math>, hence the two curves are only disjoint for <math>k=1</math> and <math>k=-1</math>. <br />
This is a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 2 ==<br />
<br />
<br />
From the graph shown above, we see that there is a specific point closest to the center of the circle. Using some logic, we realize that as long as said furthest point is not inside or on the graph of the circle. This should be enough to conclude that the hyperbola does not intersect the circle. <br />
<br />
Therefore, for each value of k, we only need to check said value to determine intersection. Let said point, closest to the circle have coordinates <math> (x, k/x) </math> derived from the equation. Then, all coordinates that satisfy <math>\sqrt{ x^2+ (k/x)^2 } \leq k </math> intersect the circle.<br />
Squaring, we find <math> x^2+(k/x)^2 \leq k^2. </math><br />
After multiplying through by <math> x^2 </math> and rearranging, we find <math> x^4-x^2k^2+k^2 \leq 0 </math>.<br />
We see this is a quadratic in <math> x^2 </math> and consider taking the determinant, which tells us that solutions are real when, after factoring:<br />
<math> k^2(k^2-4) \geq 0 </math><br />
We plot this inequality on the number line to find it is satisfied for all values except: <math> (-1, 0, 1) </math>.<br />
We then eliminate 0 because it is extraneous as both <math> xy=0 </math> and <math> x^2+y^2=0 </math> are points which coincide.<br />
Therefore, there are a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 3 (Algebra) ==<br />
<br />
Since <math>xy=k</math>, multiply the equation by 2 on both sides to get <math>2xy=2k</math>. Now we can add the two equations to get <math>(x+y)^2=k^2+2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>-1</math>, as that makes the RHS negative. Similarly, if we subtract the two equations, we obtain <math>(x-y)^2=k^2-2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>1</math>, for the same reason above.<br />
<br />
Thus, the only values are <math>k = 1, -1</math>, giving us a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
~ ccx09 (Roy Short)<br />
<br />
== Solution 4 (Quick) ==<br />
Multiply <math>k=xy</math> by and substitute it into <math>k^2=x^2+y^2</math>. Then, <math>k=\frac{x^2+y^2}{xy}</math>. Recognize it? It's also <math>k=\frac{x}{y}+\frac{y}{x}</math>. The minimum of this function (more accurately the minimum absolute value of the function) is k=2, -2 (when x=y or x=-y). As long as k>2 or k<-2, the function is valid. As such, <math>k\neq1,-1 \implies \boxed{2\ \textbf{(C)}}</math>. Elegant, huh?<br />
<br />
~~BJHHar<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=12|num-a=14|ab=A}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_13&diff=1145242010 AMC 12A Problems/Problem 132020-01-09T02:52:45Z<p>Bjhhar: /* Solution 4 (Quick) */</p>
<hr />
<div>== Problem ==<br />
For how many integer values of <math>k</math> do the graphs of <math>x^2+y^2=k^2</math> and <math>xy = k</math> not intersect?<br />
<br />
<math>\textbf{(A)}\ 0 \qquad \textbf{(B)}\ 1 \qquad \textbf{(C)}\ 2 \qquad \textbf{(D)}\ 4 \qquad \textbf{(E)}\ 8</math><br />
<br />
== Solution 1==<br />
<br />
The image below shows the two curves for <math>k=4</math>. The blue curve is <math>x^2+y^2=k^2</math>, which is clearly a circle with radius <math>k</math>, and the red curve is a part of the curve <math>xy=k</math>.<br />
<br />
<asy><br />
import graph;<br />
size(200);<br />
<br />
real f(real x) {return 4/x;};<br />
real g1(real x) {return sqrt(4*4-x*x);};<br />
real g2(real x) {return -sqrt(4*4-x*x);};<br />
draw(graph(f,-20./3,-0.6),red);<br />
draw(graph(f,0.6,20./3),red);<br />
draw(graph(g1,-4,4),blue);<br />
draw(graph(g2,-4,4),blue);<br />
axes("$x$","$y$");<br />
</asy><br />
<br />
In the special case <math>k=0</math> the blue curve is just the point <math>(0,0)</math>, and as <math>0\cdot 0=0</math>, this point is on the red curve as well, hence they intersect. <br />
<br />
The case <math>k<0</math> is symmetric to <math>k>0</math>: the blue curve remains the same and the red curve is flipped according to the <math>x</math> axis. Hence we just need to focus on <math>k>0</math>.<br />
<br />
Clearly, on the red curve there will always be points arbitrarily far from the origin: for example, as <math>x</math> approaches 0, <math>y</math> approaches <math>\infty</math>. Hence the red curve intersects the blue one if and only if it contains a point whose distance from the origin is at most <math>k</math>.<br />
<br />
<br />
At this point we can guess that on the red curve the point where <math>x=y</math> is always closest to the origin, and skip the rest of this solution.<br />
<br />
<br />
For an exact solution, fix <math>k</math> and consider any point <math>(x,y)</math> on the red curve. Its distance from the origin is <math>\sqrt{ x^2 + (k/x)^2 }</math>. To minimize this distance, it is enough to minimize <math>x^2 + (k/x)^2</math>. By the [[Arithmetic Mean-Geometric Mean Inequality]] we get that this value is at least <math>2k</math>, and that equality holds whenever <math>x^2 = (k/x)^2</math>, i.e., <math>x=\pm\sqrt k</math>.<br />
<br />
<br />
Now recall that the red curve intersects the blue one if and only if its closest point is at most <math>k</math> from the origin. We just computed that the distance between the origin and the closest point on the red curve is <math>\sqrt{2k}</math>. Therefore, we want to find all positive integers <math>k</math> such that <math>\sqrt{2k} > k</math>.<br />
<br />
Clearly the only such integer is <math>k=1</math>, hence the two curves are only disjoint for <math>k=1</math> and <math>k=-1</math>. <br />
This is a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 2 ==<br />
<br />
<br />
From the graph shown above, we see that there is a specific point closest to the center of the circle. Using some logic, we realize that as long as said furthest point is not inside or on the graph of the circle. This should be enough to conclude that the hyperbola does not intersect the circle. <br />
<br />
Therefore, for each value of k, we only need to check said value to determine intersection. Let said point, closest to the circle have coordinates <math> (x, k/x) </math> derived from the equation. Then, all coordinates that satisfy <math>\sqrt{ x^2+ (k/x)^2 } \leq k </math> intersect the circle.<br />
Squaring, we find <math> x^2+(k/x)^2 \leq k^2. </math><br />
After multiplying through by <math> x^2 </math> and rearranging, we find <math> x^4-x^2k^2+k^2 \leq 0 </math>.<br />
We see this is a quadratic in <math> x^2 </math> and consider taking the determinant, which tells us that solutions are real when, after factoring:<br />
<math> k^2(k^2-4) \geq 0 </math><br />
We plot this inequality on the number line to find it is satisfied for all values except: <math> (-1, 0, 1) </math>.<br />
We then eliminate 0 because it is extraneous as both <math> xy=0 </math> and <math> x^2+y^2=0 </math> are points which coincide.<br />
Therefore, there are a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 3 (Algebra) ==<br />
<br />
Since <math>xy=k</math>, multiply the equation by 2 on both sides to get <math>2xy=2k</math>. Now we can add the two equations to get <math>(x+y)^2=k^2+2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>-1</math>, as that makes the RHS negative. Similarly, if we subtract the two equations, we obtain <math>(x-y)^2=k^2-2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>1</math>, for the same reason above.<br />
<br />
Thus, the only values are <math>k = 1, -1</math>, giving us a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
~ ccx09 (Roy Short)<br />
<br />
== Solution 4 (Quick) ==<br />
Multiply <math>k</math> to <math>k=xy</math> and substitute it in for <math>k^2=x^2+y^2</math>. Then, <math>k=\frac{x^2+y^2}{xy}</math>. Recognize it? It's also <math>k=\frac{x}{y}+\frac{y}{x}</math>. The minimum of this function (more accurately the minimum absolute value of the function) is k=2, -2 (when x=y or x=-y). As long as k>2 or k<-2, the function is valid. As such, <math>k\neq1,-1 \implies \boxed{2\ \textbf{(C)}}</math>. Elegant, huh?<br />
<br />
~~BJHHar<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=12|num-a=14|ab=A}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_13&diff=1145232010 AMC 12A Problems/Problem 132020-01-09T02:52:31Z<p>Bjhhar: /* Solution 4 (Quick) */</p>
<hr />
<div>== Problem ==<br />
For how many integer values of <math>k</math> do the graphs of <math>x^2+y^2=k^2</math> and <math>xy = k</math> not intersect?<br />
<br />
<math>\textbf{(A)}\ 0 \qquad \textbf{(B)}\ 1 \qquad \textbf{(C)}\ 2 \qquad \textbf{(D)}\ 4 \qquad \textbf{(E)}\ 8</math><br />
<br />
== Solution 1==<br />
<br />
The image below shows the two curves for <math>k=4</math>. The blue curve is <math>x^2+y^2=k^2</math>, which is clearly a circle with radius <math>k</math>, and the red curve is a part of the curve <math>xy=k</math>.<br />
<br />
<asy><br />
import graph;<br />
size(200);<br />
<br />
real f(real x) {return 4/x;};<br />
real g1(real x) {return sqrt(4*4-x*x);};<br />
real g2(real x) {return -sqrt(4*4-x*x);};<br />
draw(graph(f,-20./3,-0.6),red);<br />
draw(graph(f,0.6,20./3),red);<br />
draw(graph(g1,-4,4),blue);<br />
draw(graph(g2,-4,4),blue);<br />
axes("$x$","$y$");<br />
</asy><br />
<br />
In the special case <math>k=0</math> the blue curve is just the point <math>(0,0)</math>, and as <math>0\cdot 0=0</math>, this point is on the red curve as well, hence they intersect. <br />
<br />
The case <math>k<0</math> is symmetric to <math>k>0</math>: the blue curve remains the same and the red curve is flipped according to the <math>x</math> axis. Hence we just need to focus on <math>k>0</math>.<br />
<br />
Clearly, on the red curve there will always be points arbitrarily far from the origin: for example, as <math>x</math> approaches 0, <math>y</math> approaches <math>\infty</math>. Hence the red curve intersects the blue one if and only if it contains a point whose distance from the origin is at most <math>k</math>.<br />
<br />
<br />
At this point we can guess that on the red curve the point where <math>x=y</math> is always closest to the origin, and skip the rest of this solution.<br />
<br />
<br />
For an exact solution, fix <math>k</math> and consider any point <math>(x,y)</math> on the red curve. Its distance from the origin is <math>\sqrt{ x^2 + (k/x)^2 }</math>. To minimize this distance, it is enough to minimize <math>x^2 + (k/x)^2</math>. By the [[Arithmetic Mean-Geometric Mean Inequality]] we get that this value is at least <math>2k</math>, and that equality holds whenever <math>x^2 = (k/x)^2</math>, i.e., <math>x=\pm\sqrt k</math>.<br />
<br />
<br />
Now recall that the red curve intersects the blue one if and only if its closest point is at most <math>k</math> from the origin. We just computed that the distance between the origin and the closest point on the red curve is <math>\sqrt{2k}</math>. Therefore, we want to find all positive integers <math>k</math> such that <math>\sqrt{2k} > k</math>.<br />
<br />
Clearly the only such integer is <math>k=1</math>, hence the two curves are only disjoint for <math>k=1</math> and <math>k=-1</math>. <br />
This is a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 2 ==<br />
<br />
<br />
From the graph shown above, we see that there is a specific point closest to the center of the circle. Using some logic, we realize that as long as said furthest point is not inside or on the graph of the circle. This should be enough to conclude that the hyperbola does not intersect the circle. <br />
<br />
Therefore, for each value of k, we only need to check said value to determine intersection. Let said point, closest to the circle have coordinates <math> (x, k/x) </math> derived from the equation. Then, all coordinates that satisfy <math>\sqrt{ x^2+ (k/x)^2 } \leq k </math> intersect the circle.<br />
Squaring, we find <math> x^2+(k/x)^2 \leq k^2. </math><br />
After multiplying through by <math> x^2 </math> and rearranging, we find <math> x^4-x^2k^2+k^2 \leq 0 </math>.<br />
We see this is a quadratic in <math> x^2 </math> and consider taking the determinant, which tells us that solutions are real when, after factoring:<br />
<math> k^2(k^2-4) \geq 0 </math><br />
We plot this inequality on the number line to find it is satisfied for all values except: <math> (-1, 0, 1) </math>.<br />
We then eliminate 0 because it is extraneous as both <math> xy=0 </math> and <math> x^2+y^2=0 </math> are points which coincide.<br />
Therefore, there are a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 3 (Algebra) ==<br />
<br />
Since <math>xy=k</math>, multiply the equation by 2 on both sides to get <math>2xy=2k</math>. Now we can add the two equations to get <math>(x+y)^2=k^2+2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>-1</math>, as that makes the RHS negative. Similarly, if we subtract the two equations, we obtain <math>(x-y)^2=k^2-2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>1</math>, for the same reason above.<br />
<br />
Thus, the only values are <math>k = 1, -1</math>, giving us a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
~ ccx09 (Roy Short)<br />
<br />
== Solution 4 (Quick) ==<br />
Multiply <math>k</math> to <math>k=xy</math> and substitute it in for <math>k^2=x^2+y^2</math>. Then, <math>k=\frac{x^2+y^2}{xy}</math>. Recognize it? It's also <math>k=\frac{x}{y}+\frac{y}{x}</math>. The minimum of this function (more accurately the minimum absolute value of the function) is k=2, -2 (when x=y or x=-y). As long as k>2 or k<-2, the function is valid. As such, <math>k\neq1,-1 \implies \boxed{2\ \textbf{(C)}}</math><br />
<br />
~~BJHHar<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=12|num-a=14|ab=A}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_13&diff=1145222010 AMC 12A Problems/Problem 132020-01-09T02:51:50Z<p>Bjhhar: /* Solution 4 (Quick) */</p>
<hr />
<div>== Problem ==<br />
For how many integer values of <math>k</math> do the graphs of <math>x^2+y^2=k^2</math> and <math>xy = k</math> not intersect?<br />
<br />
<math>\textbf{(A)}\ 0 \qquad \textbf{(B)}\ 1 \qquad \textbf{(C)}\ 2 \qquad \textbf{(D)}\ 4 \qquad \textbf{(E)}\ 8</math><br />
<br />
== Solution 1==<br />
<br />
The image below shows the two curves for <math>k=4</math>. The blue curve is <math>x^2+y^2=k^2</math>, which is clearly a circle with radius <math>k</math>, and the red curve is a part of the curve <math>xy=k</math>.<br />
<br />
<asy><br />
import graph;<br />
size(200);<br />
<br />
real f(real x) {return 4/x;};<br />
real g1(real x) {return sqrt(4*4-x*x);};<br />
real g2(real x) {return -sqrt(4*4-x*x);};<br />
draw(graph(f,-20./3,-0.6),red);<br />
draw(graph(f,0.6,20./3),red);<br />
draw(graph(g1,-4,4),blue);<br />
draw(graph(g2,-4,4),blue);<br />
axes("$x$","$y$");<br />
</asy><br />
<br />
In the special case <math>k=0</math> the blue curve is just the point <math>(0,0)</math>, and as <math>0\cdot 0=0</math>, this point is on the red curve as well, hence they intersect. <br />
<br />
The case <math>k<0</math> is symmetric to <math>k>0</math>: the blue curve remains the same and the red curve is flipped according to the <math>x</math> axis. Hence we just need to focus on <math>k>0</math>.<br />
<br />
Clearly, on the red curve there will always be points arbitrarily far from the origin: for example, as <math>x</math> approaches 0, <math>y</math> approaches <math>\infty</math>. Hence the red curve intersects the blue one if and only if it contains a point whose distance from the origin is at most <math>k</math>.<br />
<br />
<br />
At this point we can guess that on the red curve the point where <math>x=y</math> is always closest to the origin, and skip the rest of this solution.<br />
<br />
<br />
For an exact solution, fix <math>k</math> and consider any point <math>(x,y)</math> on the red curve. Its distance from the origin is <math>\sqrt{ x^2 + (k/x)^2 }</math>. To minimize this distance, it is enough to minimize <math>x^2 + (k/x)^2</math>. By the [[Arithmetic Mean-Geometric Mean Inequality]] we get that this value is at least <math>2k</math>, and that equality holds whenever <math>x^2 = (k/x)^2</math>, i.e., <math>x=\pm\sqrt k</math>.<br />
<br />
<br />
Now recall that the red curve intersects the blue one if and only if its closest point is at most <math>k</math> from the origin. We just computed that the distance between the origin and the closest point on the red curve is <math>\sqrt{2k}</math>. Therefore, we want to find all positive integers <math>k</math> such that <math>\sqrt{2k} > k</math>.<br />
<br />
Clearly the only such integer is <math>k=1</math>, hence the two curves are only disjoint for <math>k=1</math> and <math>k=-1</math>. <br />
This is a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 2 ==<br />
<br />
<br />
From the graph shown above, we see that there is a specific point closest to the center of the circle. Using some logic, we realize that as long as said furthest point is not inside or on the graph of the circle. This should be enough to conclude that the hyperbola does not intersect the circle. <br />
<br />
Therefore, for each value of k, we only need to check said value to determine intersection. Let said point, closest to the circle have coordinates <math> (x, k/x) </math> derived from the equation. Then, all coordinates that satisfy <math>\sqrt{ x^2+ (k/x)^2 } \leq k </math> intersect the circle.<br />
Squaring, we find <math> x^2+(k/x)^2 \leq k^2. </math><br />
After multiplying through by <math> x^2 </math> and rearranging, we find <math> x^4-x^2k^2+k^2 \leq 0 </math>.<br />
We see this is a quadratic in <math> x^2 </math> and consider taking the determinant, which tells us that solutions are real when, after factoring:<br />
<math> k^2(k^2-4) \geq 0 </math><br />
We plot this inequality on the number line to find it is satisfied for all values except: <math> (-1, 0, 1) </math>.<br />
We then eliminate 0 because it is extraneous as both <math> xy=0 </math> and <math> x^2+y^2=0 </math> are points which coincide.<br />
Therefore, there are a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 3 (Algebra) ==<br />
<br />
Since <math>xy=k</math>, multiply the equation by 2 on both sides to get <math>2xy=2k</math>. Now we can add the two equations to get <math>(x+y)^2=k^2+2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>-1</math>, as that makes the RHS negative. Similarly, if we subtract the two equations, we obtain <math>(x-y)^2=k^2-2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>1</math>, for the same reason above.<br />
<br />
Thus, the only values are <math>k = 1, -1</math>, giving us a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
~ ccx09 (Roy Short)<br />
<br />
== Solution 4 (Quick) ==<br />
Multiply <math>k</math> to <math>k=xy</math> and substitute it in for <math>k^2=x^2+y^2</math>. Then, <math>k=\frac{x^2+y^2}{xy}</math>. Recognize it? It's also <math>k=\frac{x}{y}+\frac{y}{x}</math>. The minimum of this function (more accurately the minimum absolute value of the function) is k=2, -2 (when x=y or x=-y). As long as k>2 or k<-2, the function is valid. As such, <math>k!=1,-1 \implies \boxed{2\ \textbf{(C)}}</math><br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=12|num-a=14|ab=A}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_13&diff=1145212010 AMC 12A Problems/Problem 132020-01-09T02:51:30Z<p>Bjhhar: </p>
<hr />
<div>== Problem ==<br />
For how many integer values of <math>k</math> do the graphs of <math>x^2+y^2=k^2</math> and <math>xy = k</math> not intersect?<br />
<br />
<math>\textbf{(A)}\ 0 \qquad \textbf{(B)}\ 1 \qquad \textbf{(C)}\ 2 \qquad \textbf{(D)}\ 4 \qquad \textbf{(E)}\ 8</math><br />
<br />
== Solution 1==<br />
<br />
The image below shows the two curves for <math>k=4</math>. The blue curve is <math>x^2+y^2=k^2</math>, which is clearly a circle with radius <math>k</math>, and the red curve is a part of the curve <math>xy=k</math>.<br />
<br />
<asy><br />
import graph;<br />
size(200);<br />
<br />
real f(real x) {return 4/x;};<br />
real g1(real x) {return sqrt(4*4-x*x);};<br />
real g2(real x) {return -sqrt(4*4-x*x);};<br />
draw(graph(f,-20./3,-0.6),red);<br />
draw(graph(f,0.6,20./3),red);<br />
draw(graph(g1,-4,4),blue);<br />
draw(graph(g2,-4,4),blue);<br />
axes("$x$","$y$");<br />
</asy><br />
<br />
In the special case <math>k=0</math> the blue curve is just the point <math>(0,0)</math>, and as <math>0\cdot 0=0</math>, this point is on the red curve as well, hence they intersect. <br />
<br />
The case <math>k<0</math> is symmetric to <math>k>0</math>: the blue curve remains the same and the red curve is flipped according to the <math>x</math> axis. Hence we just need to focus on <math>k>0</math>.<br />
<br />
Clearly, on the red curve there will always be points arbitrarily far from the origin: for example, as <math>x</math> approaches 0, <math>y</math> approaches <math>\infty</math>. Hence the red curve intersects the blue one if and only if it contains a point whose distance from the origin is at most <math>k</math>.<br />
<br />
<br />
At this point we can guess that on the red curve the point where <math>x=y</math> is always closest to the origin, and skip the rest of this solution.<br />
<br />
<br />
For an exact solution, fix <math>k</math> and consider any point <math>(x,y)</math> on the red curve. Its distance from the origin is <math>\sqrt{ x^2 + (k/x)^2 }</math>. To minimize this distance, it is enough to minimize <math>x^2 + (k/x)^2</math>. By the [[Arithmetic Mean-Geometric Mean Inequality]] we get that this value is at least <math>2k</math>, and that equality holds whenever <math>x^2 = (k/x)^2</math>, i.e., <math>x=\pm\sqrt k</math>.<br />
<br />
<br />
Now recall that the red curve intersects the blue one if and only if its closest point is at most <math>k</math> from the origin. We just computed that the distance between the origin and the closest point on the red curve is <math>\sqrt{2k}</math>. Therefore, we want to find all positive integers <math>k</math> such that <math>\sqrt{2k} > k</math>.<br />
<br />
Clearly the only such integer is <math>k=1</math>, hence the two curves are only disjoint for <math>k=1</math> and <math>k=-1</math>. <br />
This is a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 2 ==<br />
<br />
<br />
From the graph shown above, we see that there is a specific point closest to the center of the circle. Using some logic, we realize that as long as said furthest point is not inside or on the graph of the circle. This should be enough to conclude that the hyperbola does not intersect the circle. <br />
<br />
Therefore, for each value of k, we only need to check said value to determine intersection. Let said point, closest to the circle have coordinates <math> (x, k/x) </math> derived from the equation. Then, all coordinates that satisfy <math>\sqrt{ x^2+ (k/x)^2 } \leq k </math> intersect the circle.<br />
Squaring, we find <math> x^2+(k/x)^2 \leq k^2. </math><br />
After multiplying through by <math> x^2 </math> and rearranging, we find <math> x^4-x^2k^2+k^2 \leq 0 </math>.<br />
We see this is a quadratic in <math> x^2 </math> and consider taking the determinant, which tells us that solutions are real when, after factoring:<br />
<math> k^2(k^2-4) \geq 0 </math><br />
We plot this inequality on the number line to find it is satisfied for all values except: <math> (-1, 0, 1) </math>.<br />
We then eliminate 0 because it is extraneous as both <math> xy=0 </math> and <math> x^2+y^2=0 </math> are points which coincide.<br />
Therefore, there are a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
== Solution 3 (Algebra) ==<br />
<br />
Since <math>xy=k</math>, multiply the equation by 2 on both sides to get <math>2xy=2k</math>. Now we can add the two equations to get <math>(x+y)^2=k^2+2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>-1</math>, as that makes the RHS negative. Similarly, if we subtract the two equations, we obtain <math>(x-y)^2=k^2-2k</math>, for which the only value of <math>k</math> that does not satisfy the equation is <math>1</math>, for the same reason above.<br />
<br />
Thus, the only values are <math>k = 1, -1</math>, giving us a total of <math>\boxed{2\ \textbf{(C)}}</math> values.<br />
<br />
~ ccx09 (Roy Short)<br />
<br />
== Solution 4 (Quick) ==<br />
Multiply <math>k</math> to <math>k=xy</math> and substitute it in for <math>k^2=x^2+y^2</math>. <br />
<cmath>k=\frac{x^2+y^2}{xy}</cmath><br />
Recognize it? It's also <math>k=\frac{x}{y}+\frac{y}{x}</math>. The minimum of this function (more accurately the minimum absolute value of the function) is k=2, -2 (when x=y or x=-y). As long as k>2 or k<-2, the function is valid. As such, <math>k!=1,-1 \implies \boxed{2\ \textbf{(C)}}</math><br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=12|num-a=14|ab=A}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2012_AMC_10A_Problems/Problem_20&diff=1145122012 AMC 10A Problems/Problem 202020-01-09T00:47:06Z<p>Bjhhar: </p>
<hr />
<div>{{duplicate|[[2012 AMC 12A Problems|2012 AMC 12A #15]] and [[2012 AMC 10A Problems|2012 AMC 10A #20]]}}<br />
<br />
==Problem 20==<br />
<br />
A <math>3 \times 3</math> square is partitioned into <math>9</math> unit squares. Each unit square is painted either white or black with each color being equally likely, chosen independently and at random. The square is then rotated <math>90\,^{\circ}</math> clockwise about its center, and every white square in a position formerly occupied by a black square is painted black. The colors of all other squares are left unchanged. What is the probability the grid is now entirely black?<br />
<br />
<math> \textbf{(A)}\ \frac{49}{512}\qquad\textbf{(B)}\ \frac{7}{64}\qquad\textbf{(C)}\ \frac{121}{1024}\qquad\textbf{(D)}\ \frac{81}{512}\qquad\textbf{(E)}\ \frac{9}{32} </math><br />
<br />
== Solution 1==<br />
First, look for invariants. The center, unaffected by rotation, must be black. So automatically, the chance is less than 1/2. Note that a 90 degree rotation requires that black squares be across from each other across a vertical or horizontal axis. <br />
<br />
<br />
As such, 2 squares directly across from each other must be black in the 4 edge squares. Since there are 2 configurations for this to be possible (top and bottom, right and left), this is a chance of<br />
<cmath>(\frac{1}{2} \cdot \frac{1}{2})+(\frac{1}{2} \cdot \frac{1}{2})=\frac{1}{2}</cmath> <br />
<br />
<br />
However, by PIE, subtract the chance all 4 are black and both configurations are met: <math>\frac{1}{2}-(\frac{1}{2} \cdot \frac{1}{2})*(\frac{1}{2} \cdot \frac{1}{2})=\frac{7}{16}</math>. Through symmetrical reasoning, the corners also have a <math>\frac{7}{16}</math> chance of having a configuration that yields all black corners. <br />
<br />
Then, the chance that all squares black is the union of all these probabilities is <math>\frac{1}{2}(\frac{7}{16})(\frac{7}{16}) = \boxed{\textbf{(A)}\ \frac{49}{512}}</math> <br />
<br />
<br />
Psst. Great article for PIE. -> https://artofproblemsolving.com/wiki/index.php/Principle_of_Inclusion-Exclusion <br />
<br />
~BJHHar<br />
<br />
== Solution 2==<br />
First, there is only one way for the middle square to be black because it is not affected by the rotation. Then we can consider the corners and edges separately. Let's first just consider the number of ways we can color the corners. There is <math>1</math> case with all black squares. There are four cases with one white square and all <math>4</math> work. There are six cases with two white squares, but only the <math>2</math> with the white squares diagonal from each other work. There are no cases with three white squares or four white squares. Then the total number of ways to color the corners is <math>1+4+2=7</math>. In essence, the edges work the same way, so there are also <math>7</math> ways to color them. The number of ways to fit the conditions over the number of ways to color the squares is<br />
<br />
<cmath>\frac{7\times7}{2^9}=\boxed{\textbf{(A)}\ \frac{49}{512}}</cmath><br />
<br />
==Solution 3==<br />
We proceed by casework.<br />
Note that the middle square must be black because when rotated 90 degrees, it must keep its position. Now we have to deal with the following cases: <br><br />
Case 1: 0 white squares.<br />
There is exactly <math> 1 </math> way to color the grid this way. <br><br />
Case 2: 1 white square.<br />
Note that the white square can be anywhere on the grid except for the middle square because when rotating 90 degrees it can never land on itself. Thus, there are <math>8</math> cases.<br><br />
Case 3: 2 white squares. <br />
We have <math>\binom{8}{2}=28</math> ways to color two white squares without restrictions (the middle square must be black, giving us 8 squares to choose from). However, we must subtract the ways in which two white squares differ by a rotation of 90 degrees about the middle of the square. There are a total of 8 cases we must subtract (these are not too hard to see). Thus, there are <math>20</math> ways from this.<br><br />
Case 4: 3 white squares.<br />
Since we can not change the middle square, there are <math>\binom{8}{3}=56</math> ways to color this. However, we must consider the cases where at least two squares differ by a rotation of 90 degrees. We can count this with PIE: by the Principle of Exclusion, the number of cases we want to exclude is the number of cases where 2 squares differ by a rotation of 90 degrees and minus when there are 3 squares such that two of them differ by rotation of 90 and 1 of them differs by rotation of 180, because of the overcount from our first case. <br />
From case 2, there are 8 causes such that two squares differ by a rotation of 90. There are also 6 other places we can place the third square (it can't be the middle of the two that we already colored), for a total of 48 ways. We have to subtract the second case. Note that there are 8 ways in which we can arrange two squares differing by 180 degrees. Out of these, each one has two ways to put another square such that two differ by 90 degrees and 1 pair differs by 180. However, this is overcounted by a factor of 2, so there are actually 8*2/2=8 ways. <br />
Thus, we have <math>56-(48-8)=16</math> ways in this case.<br><br />
Case 5: 4 white squares.<br />
Note that two of them have to be on one of the 4 corner squares, and two of them have to be on one of the 4 edge squares. Each solution yields two combinations, for a total of 2*2=4.<br><br />
Adding up our cases yields <math>1+8+20+16+4=49</math> ways. There are 512 ways to color the square without restrictions. Thus, the answer is <math>\boxed{\textbf{(A)}\ 49/512}</math><br />
<br />
== See Also ==<br />
<br />
{{AMC10 box|year=2012|ab=A|num-b=19|num-a=21}}<br />
{{AMC12 box|year=2012|ab=A|num-b=14|num-a=16}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2012_AMC_10A_Problems/Problem_20&diff=1145112012 AMC 10A Problems/Problem 202020-01-09T00:37:26Z<p>Bjhhar: </p>
<hr />
<div>{{duplicate|[[2012 AMC 12A Problems|2012 AMC 12A #15]] and [[2012 AMC 10A Problems|2012 AMC 10A #20]]}}<br />
<br />
==Problem 20==<br />
<br />
A <math>3 \times 3</math> square is partitioned into <math>9</math> unit squares. Each unit square is painted either white or black with each color being equally likely, chosen independently and at random. The square is then rotated <math>90\,^{\circ}</math> clockwise about its center, and every white square in a position formerly occupied by a black square is painted black. The colors of all other squares are left unchanged. What is the probability the grid is now entirely black?<br />
<br />
<math> \textbf{(A)}\ \frac{49}{512}\qquad\textbf{(B)}\ \frac{7}{64}\qquad\textbf{(C)}\ \frac{121}{1024}\qquad\textbf{(D)}\ \frac{81}{512}\qquad\textbf{(E)}\ \frac{9}{32} </math><br />
<br />
== Solution 1==<br />
First, there is only one way for the middle square to be black because it is not affected by the rotation. Then we can consider the corners and edges separately. Let's first just consider the number of ways we can color the corners. There is <math>1</math> case with all black squares. There are four cases with one white square and all <math>4</math> work. There are six cases with two white squares, but only the <math>2</math> with the white squares diagonal from each other work. There are no cases with three white squares or four white squares. Then the total number of ways to color the corners is <math>1+4+2=7</math>. In essence, the edges work the same way, so there are also <math>7</math> ways to color them. The number of ways to fit the conditions over the number of ways to color the squares is<br />
<br />
<cmath>\frac{7\times7}{2^9}=\boxed{\textbf{(A)}\ \frac{49}{512}}</cmath><br />
<br />
==Solution 2==<br />
We proceed by casework.<br />
Note that the middle square must be black because when rotated 90 degrees, it must keep its position. Now we have to deal with the following cases: <br><br />
Case 1: 0 white squares.<br />
There is exactly <math> 1 </math> way to color the grid this way. <br><br />
Case 2: 1 white square.<br />
Note that the white square can be anywhere on the grid except for the middle square because when rotating 90 degrees it can never land on itself. Thus, there are <math>8</math> cases.<br><br />
Case 3: 2 white squares. <br />
We have <math>\binom{8}{2}=28</math> ways to color two white squares without restrictions (the middle square must be black, giving us 8 squares to choose from). However, we must subtract the ways in which two white squares differ by a rotation of 90 degrees about the middle of the square. There are a total of 8 cases we must subtract (these are not too hard to see). Thus, there are <math>20</math> ways from this.<br><br />
Case 4: 3 white squares.<br />
Since we can not change the middle square, there are <math>\binom{8}{3}=56</math> ways to color this. However, we must consider the cases where at least two squares differ by a rotation of 90 degrees. We can count this with PIE: by the Principle of Exclusion, the number of cases we want to exclude is the number of cases where 2 squares differ by a rotation of 90 degrees and minus when there are 3 squares such that two of them differ by rotation of 90 and 1 of them differs by rotation of 180, because of the overcount from our first case. <br />
From case 2, there are 8 causes such that two squares differ by a rotation of 90. There are also 6 other places we can place the third square (it can't be the middle of the two that we already colored), for a total of 48 ways. We have to subtract the second case. Note that there are 8 ways in which we can arrange two squares differing by 180 degrees. Out of these, each one has two ways to put another square such that two differ by 90 degrees and 1 pair differs by 180. However, this is overcounted by a factor of 2, so there are actually 8*2/2=8 ways. <br />
Thus, we have <math>56-(48-8)=16</math> ways in this case.<br><br />
Case 5: 4 white squares.<br />
Note that two of them have to be on one of the 4 corner squares, and two of them have to be on one of the 4 edge squares. Each solution yields two combinations, for a total of 2*2=4.<br><br />
Adding up our cases yields <math>1+8+20+16+4=49</math> ways. There are 512 ways to color the square without restrictions. Thus, the answer is <math>\boxed{\textbf{(A)}\ 49/512}</math><br />
<br />
== See Also ==<br />
<br />
{{AMC10 box|year=2012|ab=A|num-b=19|num-a=21}}<br />
{{AMC12 box|year=2012|ab=A|num-b=14|num-a=16}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_3&diff=1139352014 AIME II Problems/Problem 32020-01-01T04:30:39Z<p>Bjhhar: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
<br />
A rectangle has sides of length <math>a</math> and 36. A hinge is installed at each vertex of the rectangle, and at the midpoint of each side of length 36. The sides of length <math>a</math> can be pressed toward each other keeping those two sides parallel so the rectangle becomes a convex hexagon as shown. When the figure is a hexagon with the sides of length <math>a</math> parallel and separated by a distance of 24, the hexagon has the same area as the original rectangle. Find <math>a^2</math>. <br />
<br />
<asy><br />
pair A,B,C,D,E,F,R,S,T,X,Y,Z;<br />
dotfactor = 2;<br />
unitsize(.1cm);<br />
A = (0,0);<br />
B = (0,18);<br />
C = (0,36);<br />
// don't look here<br />
D = (12*2.236, 36);<br />
E = (12*2.236, 18);<br />
F = (12*2.236, 0);<br />
draw(A--B--C--D--E--F--cycle);<br />
dot(" ",A,NW);<br />
dot(" ",B,NW);<br />
dot(" ",C,NW);<br />
dot(" ",D,NW);<br />
dot(" ",E,NW);<br />
dot(" ",F,NW);<br />
//don't look here<br />
R = (12*2.236 +22,0);<br />
S = (12*2.236 + 22 - 13.4164,12);<br />
T = (12*2.236 + 22,24);<br />
X = (12*4.472+ 22,24);<br />
Y = (12*4.472+ 22 + 13.4164,12);<br />
Z = (12*4.472+ 22,0);<br />
draw(R--S--T--X--Y--Z--cycle);<br />
dot(" ",R,NW);<br />
dot(" ",S,NW);<br />
dot(" ",T,NW);<br />
dot(" ",X,NW);<br />
dot(" ",Y,NW);<br />
dot(" ",Z,NW);<br />
// sqrt180 = 13.4164<br />
// sqrt5 = 2.236</asy><br />
<br />
==Solution==<br />
<br />
When we squish the rectangle, the hexagon is composed of a rectangle and two isosceles triangles with side lengths 18, 18, and 24 as shown below.<br />
<br />
<asy><br />
pair R,S,T,X,Y,Z;<br />
dotfactor = 2;<br />
unitsize(.1cm);<br />
R = (12*2.236 +22,0);<br />
S = (12*2.236 + 22 - 13.4164,12);<br />
T = (12*2.236 + 22,24);<br />
X = (12*4.472+ 22,24);<br />
Y = (12*4.472+ 22 + 13.4164,12);<br />
Z = (12*4.472+ 22,0);<br />
draw(R--S--T--X--Y--Z--cycle);<br />
draw(T--R,red);<br />
draw(X--Z,red);<br />
dot(" ",R,NW);<br />
dot(" ",S,NW);<br />
dot(" ",T,NW);<br />
dot(" ",X,NW);<br />
dot(" ",Y,NW);<br />
dot(" ",Z,NW);<br />
// sqrt180 = 13.4164<br />
// sqrt5 = 2.236</asy><br />
<br />
By Heron's Formula, the area of each isosceles triangle is <math>\sqrt{(30)(12)(12)(6)}=\sqrt{180\times 12^2}=72\sqrt{5}</math>. So the area of both is <math>144\sqrt{5}</math>. From the rectangle, our original area is <math>36a</math>. The area of the rectangle in the hexagon is <math>24a</math>. So we have <cmath>24a+144\sqrt{5}=36a\implies 12a=144\sqrt{5}\implies a=12\sqrt{5}\implies a^2=\boxed{720}.</cmath><br />
<br />
==Solution 2==<br />
Alternatively, use basic geometry. First, scale everything down by dividing everything by 6. Let <math>a/6=p</math>. Then, the dimensions of the central rectangle in the hexagon is p x 4, and the original rectangle is 6 x p. By Pythagorean theorem and splitting the end triangles of the hexagon into two right triangles, the altitude of the end triangles is <math>\sqrt{3^2-2^2}=\sqrt{5}</math> given 2 as the base of the constituent right triangles. The two end triangles form a large rectangle of area <math>\sqrt{5}</math> x <math>4</math>. Then, the area of the hexagon is <math>4p+4\sqrt{5}</math>, and the area of the rectangle is <math>6p</math>. Equating them, <math>p=2\sqrt{5}</math>. Multiply by scale factor of 6 and square it to get <math>36(20)= 720 \implies a^2=\boxed{720}</math>.<br />
<br />
~BJHHar<br />
<br />
== See also ==<br />
{{AIME box|year=2014|n=II|num-b=2|num-a=4}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_3&diff=1139342014 AIME II Problems/Problem 32020-01-01T04:30:07Z<p>Bjhhar: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
<br />
A rectangle has sides of length <math>a</math> and 36. A hinge is installed at each vertex of the rectangle, and at the midpoint of each side of length 36. The sides of length <math>a</math> can be pressed toward each other keeping those two sides parallel so the rectangle becomes a convex hexagon as shown. When the figure is a hexagon with the sides of length <math>a</math> parallel and separated by a distance of 24, the hexagon has the same area as the original rectangle. Find <math>a^2</math>. <br />
<br />
<asy><br />
pair A,B,C,D,E,F,R,S,T,X,Y,Z;<br />
dotfactor = 2;<br />
unitsize(.1cm);<br />
A = (0,0);<br />
B = (0,18);<br />
C = (0,36);<br />
// don't look here<br />
D = (12*2.236, 36);<br />
E = (12*2.236, 18);<br />
F = (12*2.236, 0);<br />
draw(A--B--C--D--E--F--cycle);<br />
dot(" ",A,NW);<br />
dot(" ",B,NW);<br />
dot(" ",C,NW);<br />
dot(" ",D,NW);<br />
dot(" ",E,NW);<br />
dot(" ",F,NW);<br />
//don't look here<br />
R = (12*2.236 +22,0);<br />
S = (12*2.236 + 22 - 13.4164,12);<br />
T = (12*2.236 + 22,24);<br />
X = (12*4.472+ 22,24);<br />
Y = (12*4.472+ 22 + 13.4164,12);<br />
Z = (12*4.472+ 22,0);<br />
draw(R--S--T--X--Y--Z--cycle);<br />
dot(" ",R,NW);<br />
dot(" ",S,NW);<br />
dot(" ",T,NW);<br />
dot(" ",X,NW);<br />
dot(" ",Y,NW);<br />
dot(" ",Z,NW);<br />
// sqrt180 = 13.4164<br />
// sqrt5 = 2.236</asy><br />
<br />
==Solution==<br />
<br />
When we squish the rectangle, the hexagon is composed of a rectangle and two isosceles triangles with side lengths 18, 18, and 24 as shown below.<br />
<br />
<asy><br />
pair R,S,T,X,Y,Z;<br />
dotfactor = 2;<br />
unitsize(.1cm);<br />
R = (12*2.236 +22,0);<br />
S = (12*2.236 + 22 - 13.4164,12);<br />
T = (12*2.236 + 22,24);<br />
X = (12*4.472+ 22,24);<br />
Y = (12*4.472+ 22 + 13.4164,12);<br />
Z = (12*4.472+ 22,0);<br />
draw(R--S--T--X--Y--Z--cycle);<br />
draw(T--R,red);<br />
draw(X--Z,red);<br />
dot(" ",R,NW);<br />
dot(" ",S,NW);<br />
dot(" ",T,NW);<br />
dot(" ",X,NW);<br />
dot(" ",Y,NW);<br />
dot(" ",Z,NW);<br />
// sqrt180 = 13.4164<br />
// sqrt5 = 2.236</asy><br />
<br />
By Heron's Formula, the area of each isosceles triangle is <math>\sqrt{(30)(12)(12)(6)}=\sqrt{180\times 12^2}=72\sqrt{5}</math>. So the area of both is <math>144\sqrt{5}</math>. From the rectangle, our original area is <math>36a</math>. The area of the rectangle in the hexagon is <math>24a</math>. So we have <cmath>24a+144\sqrt{5}=36a\implies 12a=144\sqrt{5}\implies a=12\sqrt{5}\implies a^2=\boxed{720}.</cmath><br />
<br />
==Solution 2==<br />
Alternatively, use basic geometry. First, scale everything down by dividing everything by 6. Let <math>a/6=p</math>. Then, the dimensions of the central rectangle in the hexagon is p x 4, and the original rectangle is 6 x p. By Pythagorean theorem and splitting the end triangles of the hexagon into two right triangles, the altitude of the end triangles is <math>\sqrt{3^2-2^2}=\sqrt{5}</math> given 2 as the base of the constituent right triangles. The two end triangles form a large rectangle of area <math>\sqrt{5} x 4</math>. Then, the area of the hexagon is <math>4p+4\sqrt{5}</math>, and the area of the rectangle is <math>6p</math>. Equating them, <math>p=2\sqrt{5}</math>. Multiply by scale factor of 6 and square it to get <math>36(20)= 720 \implies a^2=\boxed{720}</math>.<br />
<br />
~BJHHar<br />
<br />
== See also ==<br />
{{AIME box|year=2014|n=II|num-b=2|num-a=4}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_3&diff=1139332014 AIME II Problems/Problem 32020-01-01T04:29:30Z<p>Bjhhar: </p>
<hr />
<div>==Problem==<br />
<br />
A rectangle has sides of length <math>a</math> and 36. A hinge is installed at each vertex of the rectangle, and at the midpoint of each side of length 36. The sides of length <math>a</math> can be pressed toward each other keeping those two sides parallel so the rectangle becomes a convex hexagon as shown. When the figure is a hexagon with the sides of length <math>a</math> parallel and separated by a distance of 24, the hexagon has the same area as the original rectangle. Find <math>a^2</math>. <br />
<br />
<asy><br />
pair A,B,C,D,E,F,R,S,T,X,Y,Z;<br />
dotfactor = 2;<br />
unitsize(.1cm);<br />
A = (0,0);<br />
B = (0,18);<br />
C = (0,36);<br />
// don't look here<br />
D = (12*2.236, 36);<br />
E = (12*2.236, 18);<br />
F = (12*2.236, 0);<br />
draw(A--B--C--D--E--F--cycle);<br />
dot(" ",A,NW);<br />
dot(" ",B,NW);<br />
dot(" ",C,NW);<br />
dot(" ",D,NW);<br />
dot(" ",E,NW);<br />
dot(" ",F,NW);<br />
//don't look here<br />
R = (12*2.236 +22,0);<br />
S = (12*2.236 + 22 - 13.4164,12);<br />
T = (12*2.236 + 22,24);<br />
X = (12*4.472+ 22,24);<br />
Y = (12*4.472+ 22 + 13.4164,12);<br />
Z = (12*4.472+ 22,0);<br />
draw(R--S--T--X--Y--Z--cycle);<br />
dot(" ",R,NW);<br />
dot(" ",S,NW);<br />
dot(" ",T,NW);<br />
dot(" ",X,NW);<br />
dot(" ",Y,NW);<br />
dot(" ",Z,NW);<br />
// sqrt180 = 13.4164<br />
// sqrt5 = 2.236</asy><br />
<br />
==Solution==<br />
<br />
When we squish the rectangle, the hexagon is composed of a rectangle and two isosceles triangles with side lengths 18, 18, and 24 as shown below.<br />
<br />
<asy><br />
pair R,S,T,X,Y,Z;<br />
dotfactor = 2;<br />
unitsize(.1cm);<br />
R = (12*2.236 +22,0);<br />
S = (12*2.236 + 22 - 13.4164,12);<br />
T = (12*2.236 + 22,24);<br />
X = (12*4.472+ 22,24);<br />
Y = (12*4.472+ 22 + 13.4164,12);<br />
Z = (12*4.472+ 22,0);<br />
draw(R--S--T--X--Y--Z--cycle);<br />
draw(T--R,red);<br />
draw(X--Z,red);<br />
dot(" ",R,NW);<br />
dot(" ",S,NW);<br />
dot(" ",T,NW);<br />
dot(" ",X,NW);<br />
dot(" ",Y,NW);<br />
dot(" ",Z,NW);<br />
// sqrt180 = 13.4164<br />
// sqrt5 = 2.236</asy><br />
<br />
By Heron's Formula, the area of each isosceles triangle is <math>\sqrt{(30)(12)(12)(6)}=\sqrt{180\times 12^2}=72\sqrt{5}</math>. So the area of both is <math>144\sqrt{5}</math>. From the rectangle, our original area is <math>36a</math>. The area of the rectangle in the hexagon is <math>24a</math>. So we have <cmath>24a+144\sqrt{5}=36a\implies 12a=144\sqrt{5}\implies a=12\sqrt{5}\implies a^2=\boxed{720}.</cmath><br />
<br />
==Solution 2==<br />
Alternatively, use basic geometry. First, scale everything down by dividing everything by 6. Let <math>a/6=p</math>. Then, the dimensions of the central rectangle in the hexagon is p x 4, and the original rectangle is 6 x p. By Pythagorean theorem and splitting the end triangles of the hexagon into two right triangles, the altitude of the end triangles is <math>\sqrt{3^2-2^2}=\sqrt{5}</math> given 2 as the base of the constituent right triangles. The two end triangles form a large rectangle of area <math>\sqrt{5} x 4</math>. Then, the area of the hexagon is <math>4p+4sqrt{5}</math>, and the area of the rectangle is <math>6p</math>. Equating them, <math>p=2sqrt{5}</math>. Multiply by scale factor of 6 and square it to get <math>36(20)= 720 \implies a^2=\boxed{720}</math>.<br />
<br />
~BJHHar<br />
<br />
<br />
== See also ==<br />
{{AIME box|year=2014|n=II|num-b=2|num-a=4}}<br />
<br />
[[Category:Introductory Geometry Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_11&diff=1136702010 AMC 12B Problems/Problem 112019-12-29T04:49:42Z<p>Bjhhar: </p>
<hr />
<div>== Problem 11 ==<br />
A palindrome between <math>1000</math> and <math>10,000</math> is chosen at random. What is the probability that it is divisible by <math>7</math>?<br />
<br />
<math>\textbf{(A)}\ \dfrac{1}{10} \qquad \textbf{(B)}\ \dfrac{1}{9} \qquad \textbf{(C)}\ \dfrac{1}{7} \qquad \textbf{(D)}\ \dfrac{1}{6} \qquad \textbf{(E)}\ \dfrac{1}{5}</math><br />
<br />
== Solution ==<br />
View the palindrome as some number with form (decimal representation):<br />
<math>a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0</math>. But because the number is a palindrome, <math>a_3 = a_0, a_2 = a_1</math>. Recombining this yields <math>1001a_3 + 110a_2</math>. 1001 is divisible by 7, which means that as long as <math>a_2 = 0</math>, the palindrome will be divisible by 7. This yields 9 palindromes out of 90 (<math>9 \cdot 10</math>) possibilities for palindromes. However, if <math>a_2 = 7</math>, then this gives another case in which the palindrome is divisible by 7. This adds another 9 palindromes to the list, bringing our total to <math>18/90 = \boxed {\frac{1}{5} } = \boxed {E}</math><br />
<br />
== Addendum (Alternate) == <br />
<math>7\mid 1001a^3+110b^2</math> and <math>1001 \equiv 0 (\textrm{mod} 7)</math>. Knowing that <math>a</math> does not factor (pun intended) into the problem, note 110's prime factorization and <math>7\mid b</math>. There are only 10 possible digits for b (0-9), but <math>7\mid b</math> only holds if <math>b=0, 7</math>. This is 2 of the 10 digits, so <math>\frac{2}{10}=\boxed{\textbf{E)}\frac{1}{5}}</math><br />
<br />
~BJHHar<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=10|num-a=12|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136142010 AMC 12B Problems/Problem 172019-12-28T19:51:04Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
Observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right. <br />
<br />
<br />
*'''Case 1: Center 4'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant. So, there are 3 cases each and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7 as above. Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
<cmath>12+18+12=\boxed{\textbf{D)}42}</cmath><br />
<br />
<br />
~BJHHar<br />
<br />
<br />
''P.S.: I like the tetris approach used in Solution 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem. If the initial observations are unclear, make a tableau with a range of possible numbers in each square''.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136132010 AMC 12B Problems/Problem 172019-12-28T19:50:18Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
Observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right. <br />
<br />
<br />
*'''Case 1: Center 4'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant. So, there are 3 cases each and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7 as above. Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
<cmath>12+18+12=\boxed{\textbf{D)42}}</cmath><br />
<br />
<br />
~BJHHar<br />
<br />
<br />
''P.S.: I like the tetris approach used in Solution 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem. If the initial observations are unclear, make a tableau with a range of possible numbers in each square''.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136122010 AMC 12B Problems/Problem 172019-12-28T19:48:30Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
Observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right. <br />
<br />
*'''Case 1: Center 4'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
With 4 in center, 3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7 as above. Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
<cmath>12+18+12=\boxed{\textbf{D)42}}</cmath><br />
<br />
<br />
~BJHHar<br />
<br />
<br />
''P.S.: I like the tetris approach used in Solution 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem. If the initial observations are unclear, make a tableau with a range of possible numbers in each square''.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136112010 AMC 12B Problems/Problem 172019-12-28T19:45:36Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right. <br />
<br />
*'''Case 1: Center 4'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
With 4 in center, 3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7 as above. Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
<br />
<br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136102010 AMC 12B Problems/Problem 172019-12-28T19:44:53Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right. <br />
<br />
*'''Case 1: Center 4'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
With 4 in center, 3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7 as above. Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136092010 AMC 12B Problems/Problem 172019-12-28T19:44:30Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right. <br />
<br />
*'''Case 1: Center 4'''<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math>.<br />
<br />
With 4 in center, 3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
<cmath>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</cmath><br />
<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7 as above. Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136082010 AMC 12B Problems/Problem 172019-12-28T19:41:03Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right. <br />
<br />
*'''Case 1: Center 4'''<br />
With 4 in center, 3 necessarily must be placed <br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math>.<br />
<br />
Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7.<br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math><br />
<br />
Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136072010 AMC 12B Problems/Problem 172019-12-28T19:39:41Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the top left square to the bottom right square diagonal. <br />
<br />
*'''Case 1: Center 4'''<br />
With 4 in center, 3 necessarily must be placed <br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math>.<br />
<br />
Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7.<br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math><br />
<br />
Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136062010 AMC 12B Problems/Problem 172019-12-28T19:36:18Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and the middle square having either of 4-6. Also note that each tableau has a valid symmetrical tableau across the top left square to the bottom right square diagonal. Then, the number of charts is double the following cases.<br />
<br />
<br />
*'''Case 1: Center 4'''<br />
With 4 in center, 3 necessarily must be placed <br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math>.<br />
<br />
Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7.<br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math><br />
<br />
Remembering that <math>4<5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136052010 AMC 12B Problems/Problem 172019-12-28T19:35:07Z<p>Bjhhar: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and the middle square having either of 4-6. Also note that each tableau has a valid symmetrical tableau across the top left square to the bottom right square diagonal. Then, the number of charts is double the following cases.<br />
<br />
<br />
*'''Case 1: Center 4'''<br />
With 4 in center, 3 necessarily must be placed <br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math>.<br />
<br />
Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. One more level of casework.<br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math><br />
<br />
Remembering that <math>4<5</math> and <math>6,7>5</math>, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&diff=1136042010 AMC 12B Problems/Problem 172019-12-28T19:27:35Z<p>Bjhhar: </p>
<hr />
<div>== Problem ==<br />
The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?<br />
<br />
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math><br />
<br />
== Solution 1 ==<br />
First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and the middle square having either of 4-6. Also note that each tableau has a valid symmetrical tableau across the top left square to the bottom right square diagonal. Then, the number of charts is double the following cases.<br />
<br />
*'''Case 1: Center 4'''<br />
With 4 in center, 3 necessarily must be placed <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&4&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math>, leaving the numbers 5,6,7. <br />
<br />
Any number could fit into the isolated square in each case, but the next 2 must follow sequentially in the remaining 2 slots. As there are 3 numbers, there are 3 cases for each tableau, leaving 6 overall cases with 4 in the center. Given the diagonal symmetry observed before, the other placements of the 2s and 8s are symmetrical, so multiply by 2. <math>2*6=12</math><br />
<br />
*'''Case 2: Center 5'''<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline &5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline &5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math>. No 3s or 7s are assured, so this is only a bit trickier and messier. One more level of casework.<br />
<br />
<math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&\\<br />
\hline &8&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\<br />
\hline 3&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\<br />
\hline 4&5&8\\<br />
\hline &&9\\<br />
\hline \end{tabular}</math><br />
<br />
Remembering that 4 cannot go after 5, the numbers of cases are then 2,3,3,1 respectively. As before, multiply by 2 because of symmetry. <math>2*9=18</math><br />
<br />
*'''Case 3: Center 6'''<br />
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.<br />
<math>2*6=12</math><br />
<br />
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math><br />
<br />
~BJHHar<br />
<br />
<br />
P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem. <br />
<br />
<br />
== Solution 2==<br />
The first 4 numbers will form one of 3 tetris "shapes".<br />
<br />
First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & 4 & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\<br />
\hline 2 & & \\<br />
\hline 3 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\<br />
\hline 2 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\<br />
\hline 3 & & \\<br />
\hline 4 & & \\<br />
\hline \end{tabular}</math><br />
<br />
Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\<br />
\hline 4 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\<br />
\hline 3 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\<br />
\hline 2 & & \\<br />
\hline & & \\<br />
\hline \end{tabular}</math><br />
<br />
Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).<br />
<br />
If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.<br />
<br />
So what shapes will physically fit in the 3x3 grid, together?<br />
<br />
<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\<br />
O & J & 2\times 3 = 6 \\<br />
O & L & 2\times 3 = 6 \\<br />
J & O & 3\times 2 = 6 \\<br />
J & J & 3 \times 3 = 9 \\<br />
L & O & 3 \times 2 = 6 \\<br />
L & L & 3 \times 3 = 9 \\<br />
O & O & \qquad \text{They don't fit} \\<br />
J & L & \qquad \text{They don't fit} \\<br />
L & J & \qquad \text{They don't fit} \\<br />
\end{array}</math><br />
<br />
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.<br />
<br />
== Solution 3==<br />
This solution is trivial by the hook length theorem. The hooks look like this:<br />
<br />
<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\<br />
\hline 4 & 3 & 2\\<br />
\hline 3 & 2 & 1\\<br />
\hline \end{tabular}</math><br />
<br />
So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math><br />
<br />
P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}<br />
<br />
[[Category:Introductory Combinatorics Problems]]<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_1&diff=1130122019 AIME I Problems/Problem 12019-12-18T01:00:29Z<p>Bjhhar: /* Solution 3 */</p>
<hr />
<div>==Problem 1==<br />
<br />
Consider the integer <cmath>N = 9 + 99 + 999 + 9999 + \cdots + \underbrace{99\ldots 99}_\text{321 digits}.</cmath>Find the sum of the digits of <math>N</math>.<br />
<br />
==Solution==<br />
Let's express the number in terms of <math>10^n</math>. We can obtain <math>(10-1)+(10^2-1)+(10^3-1)+\cdots+(10^{321}-1)</math>. By the commutative and associative property, we can group it into <math>(10+10^2+10^3+\cdots+10^{321})-321</math>. We know the former will yield <math>1111....10</math>, so we only have to figure out what the last few digits are. There are currently <math>321</math> 1's. We know the last 4 digits are 1110, and that the others will not be affected if we subtract <math>321</math>. If we do so, we get that <math>1110-321=789</math>. This method will remove 3 1's, and add a 7, 8 and 9. Therefore, the sum of the digits is <math>(321-3)+7+8+9=\boxed{342}</math>.<br />
<br />
-eric2020<br />
<br />
<br />
<br />
A similar and simpler way to consider the initial manipulations is to observe that adding 1 to each term results in <math>(10+100+... 10^{320}+10^{321})</math>. There are 321 terms, so it becomes <math>11...0</math>, where there are 322 digits in <math>11...0</math>. Then, subtract the 321 you initially added. <br />
<br />
~ BJHHar<br />
<br />
==Solution 2==<br />
We can see that <math>9=9</math>, <math>9+99=108</math>, <math>9+99+999=1107</math>, all the way to ten nines when we have <math>11111111100</math>. Then, when we add more nines, we repeat the same process, and quickly get that the sum of digits is <math>\boxed{342}</math> since we have to add <math>9\lfloor \log 321 \rfloor</math> to the sum of digits, which is <math>9\lceil \frac{321}9 \rceil</math>.<br />
<br />
<br />
==Solution 3 (Pattern)==<br />
Observe how adding results in the last term but with a 1 concatenated in front and also a 1 subtracted (09, 108, 1107, 11106). Then for any index of terms, <math>n</math>, the sum is <math>11...10-n</math>, where the first term is of length <math>n+1</math>. Here, that is <math>\boxed{342}</math>.<br />
<br />
~BJHHar<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=JFHjpxoYLDk<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2019|n=I|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_1&diff=1130112019 AIME I Problems/Problem 12019-12-18T00:59:56Z<p>Bjhhar: </p>
<hr />
<div>==Problem 1==<br />
<br />
Consider the integer <cmath>N = 9 + 99 + 999 + 9999 + \cdots + \underbrace{99\ldots 99}_\text{321 digits}.</cmath>Find the sum of the digits of <math>N</math>.<br />
<br />
==Solution==<br />
Let's express the number in terms of <math>10^n</math>. We can obtain <math>(10-1)+(10^2-1)+(10^3-1)+\cdots+(10^{321}-1)</math>. By the commutative and associative property, we can group it into <math>(10+10^2+10^3+\cdots+10^{321})-321</math>. We know the former will yield <math>1111....10</math>, so we only have to figure out what the last few digits are. There are currently <math>321</math> 1's. We know the last 4 digits are 1110, and that the others will not be affected if we subtract <math>321</math>. If we do so, we get that <math>1110-321=789</math>. This method will remove 3 1's, and add a 7, 8 and 9. Therefore, the sum of the digits is <math>(321-3)+7+8+9=\boxed{342}</math>.<br />
<br />
-eric2020<br />
<br />
<br />
<br />
A similar and simpler way to consider the initial manipulations is to observe that adding 1 to each term results in <math>(10+100+... 10^{320}+10^{321})</math>. There are 321 terms, so it becomes <math>11...0</math>, where there are 322 digits in <math>11...0</math>. Then, subtract the 321 you initially added. <br />
<br />
~ BJHHar<br />
<br />
==Solution 2==<br />
We can see that <math>9=9</math>, <math>9+99=108</math>, <math>9+99+999=1107</math>, all the way to ten nines when we have <math>11111111100</math>. Then, when we add more nines, we repeat the same process, and quickly get that the sum of digits is <math>\boxed{342}</math> since we have to add <math>9\lfloor \log 321 \rfloor</math> to the sum of digits, which is <math>9\lceil \frac{321}9 \rceil</math>.<br />
<br />
<br />
==Solution 3==<br />
Observe how adding results in the last term but with a 1 concatenated in front and also a 1 subtracted (09, 108, 1107, 11106). Then for any index of terms, <math>n</math>, the sum is <math>11...10-n</math>, where the first term is of length <math>n+1</math>. Here, that is <math>\boxed{342}</math>.<br />
<br />
~BJHHar<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=JFHjpxoYLDk<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2019|n=I|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_1&diff=1130102019 AIME I Problems/Problem 12019-12-18T00:51:00Z<p>Bjhhar: /* Solution */</p>
<hr />
<div>==Problem 1==<br />
<br />
Consider the integer <cmath>N = 9 + 99 + 999 + 9999 + \cdots + \underbrace{99\ldots 99}_\text{321 digits}.</cmath>Find the sum of the digits of <math>N</math>.<br />
<br />
==Solution==<br />
Let's express the number in terms of <math>10^n</math>. We can obtain <math>(10-1)+(10^2-1)+(10^3-1)+\cdots+(10^{321}-1)</math>. By the commutative and associative property, we can group it into <math>(10+10^2+10^3+\cdots+10^{321})-321</math>. We know the former will yield <math>1111....10</math>, so we only have to figure out what the last few digits are. There are currently <math>321</math> 1's. We know the last 4 digits are 1110, and that the others will not be affected if we subtract <math>321</math>. If we do so, we get that <math>1110-321=789</math>. This method will remove 3 1's, and add a 7, 8 and 9. Therefore, the sum of the digits is <math>(321-3)+7+8+9=\boxed{342}</math>.<br />
<br />
-eric2020<br />
<br />
<br />
<br />
A similar and simpler way to consider the initial manipulations is to observe that adding 1 to each term results in <math>(10+100+... 10^{320}+10^{321})</math>. There are 321 terms, so it becomes <math>11...0</math>, where there are 322 digits in <math>11...0</math>. Then, subtract the 321 you initially added. <br />
<br />
~ BJHHar<br />
<br />
==Solution 2==<br />
We can see that <math>9=9</math>, <math>9+99=108</math>, <math>9+99+999=1107</math>, all the way to ten nines when we have <math>11111111100</math>. Then, when we add more nines, we repeat the same process, and quickly get that the sum of digits is <math>\boxed{342}</math> since we have to add <math>9\lfloor \log 321 \rfloor</math> to the sum of digits, which is <math>9\lceil \frac{321}9 \rceil</math>.<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=JFHjpxoYLDk<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2019|n=I|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_1&diff=1130092019 AIME I Problems/Problem 12019-12-18T00:50:37Z<p>Bjhhar: /* Solution */</p>
<hr />
<div>==Problem 1==<br />
<br />
Consider the integer <cmath>N = 9 + 99 + 999 + 9999 + \cdots + \underbrace{99\ldots 99}_\text{321 digits}.</cmath>Find the sum of the digits of <math>N</math>.<br />
<br />
==Solution==<br />
Let's express the number in terms of <math>10^n</math>. We can obtain <math>(10-1)+(10^2-1)+(10^3-1)+\cdots+(10^{321}-1)</math>. By the commutative and associative property, we can group it into <math>(10+10^2+10^3+\cdots+10^{321})-321</math>. We know the former will yield <math>1111....10</math>, so we only have to figure out what the last few digits are. There are currently <math>321</math> 1's. We know the last 4 digits are 1110, and that the others will not be affected if we subtract <math>321</math>. If we do so, we get that <math>1110-321=789</math>. This method will remove 3 1's, and add a 7, 8 and 9. Therefore, the sum of the digits is <math>(321-3)+7+8+9=\boxed{342}</math>.<br />
<br />
-eric2020<br />
<br />
<br />
<br />
A similar and simpler way to consider the initial manipulations is to observe that adding 1 to each term results in <math>10+100+... 10^{320}+10^{321})</math>. There are 321 terms, so it becomes <math>11...0</math>, where there are 322 digits in <math>11...0</math>. Then, subtract the 321 you initially added <br />
<br />
~ BJHHar<br />
<br />
==Solution 2==<br />
We can see that <math>9=9</math>, <math>9+99=108</math>, <math>9+99+999=1107</math>, all the way to ten nines when we have <math>11111111100</math>. Then, when we add more nines, we repeat the same process, and quickly get that the sum of digits is <math>\boxed{342}</math> since we have to add <math>9\lfloor \log 321 \rfloor</math> to the sum of digits, which is <math>9\lceil \frac{321}9 \rceil</math>.<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=JFHjpxoYLDk<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2019|n=I|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_1&diff=1130082019 AIME I Problems/Problem 12019-12-18T00:50:12Z<p>Bjhhar: /* Solution */</p>
<hr />
<div>==Problem 1==<br />
<br />
Consider the integer <cmath>N = 9 + 99 + 999 + 9999 + \cdots + \underbrace{99\ldots 99}_\text{321 digits}.</cmath>Find the sum of the digits of <math>N</math>.<br />
<br />
==Solution==<br />
Let's express the number in terms of <math>10^n</math>. We can obtain <math>(10-1)+(10^2-1)+(10^3-1)+\cdots+(10^{321}-1)</math>. By the commutative and associative property, we can group it into <math>(10+10^2+10^3+\cdots+10^{321})-321</math>. We know the former will yield <math>1111....10</math>, so we only have to figure out what the last few digits are. There are currently <math>321</math> 1's. We know the last 4 digits are 1110, and that the others will not be affected if we subtract <math>321</math>. If we do so, we get that <math>1110-321=789</math>. This method will remove 3 1's, and add a 7, 8 and 9. Therefore, the sum of the digits is <math>(321-3)+7+8+9=\boxed{342}</math>.<br />
<br />
-eric2020<br />
<br />
<br />
<br />
A similar, but separate way to consider the initial manipulations is to observe that adding 1 to each term results in <math>10+100+... 10^{320}+10^{321})</math>. There are 321 terms, so it becomes <math>11...0</math>, where there are 322 digits in <math>11...0</math>. Then, subtract the 321 you initially added <br />
<br />
~ BJHHar<br />
<br />
==Solution 2==<br />
We can see that <math>9=9</math>, <math>9+99=108</math>, <math>9+99+999=1107</math>, all the way to ten nines when we have <math>11111111100</math>. Then, when we add more nines, we repeat the same process, and quickly get that the sum of digits is <math>\boxed{342}</math> since we have to add <math>9\lfloor \log 321 \rfloor</math> to the sum of digits, which is <math>9\lceil \frac{321}9 \rceil</math>.<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=JFHjpxoYLDk<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2019|n=I|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_1&diff=1130072019 AIME I Problems/Problem 12019-12-18T00:49:02Z<p>Bjhhar: /* Solution */</p>
<hr />
<div>==Problem 1==<br />
<br />
Consider the integer <cmath>N = 9 + 99 + 999 + 9999 + \cdots + \underbrace{99\ldots 99}_\text{321 digits}.</cmath>Find the sum of the digits of <math>N</math>.<br />
<br />
==Solution==<br />
Let's express the number in terms of <math>10^n</math>. We can obtain <math>(10-1)+(10^2-1)+(10^3-1)+\cdots+(10^{321}-1)</math>. By the commutative and associative property, we can group it into <math>(10+10^2+10^3+\cdots+10^{321})-321</math>. We know the former will yield <math>1111....10</math>, so we only have to figure out what the last few digits are. There are currently <math>321</math> 1's. We know the last 4 digits are 1110, and that the others will not be affected if we subtract <math>321</math>. If we do so, we get that <math>1110-321=789</math>. This method will remove 3 1's, and add a 7, 8 and 9. Therefore, the sum of the digits is <math>(321-3)+7+8+9=\boxed{342}</math>.<br />
<br />
-eric2020<br />
<br />
A similar, but separate way to consider the initial calculations is to observe that adding 1 to each term results in <math>10+100+... 10^320+10^321)</math>. There are 321 terms, so it becomes <math>11...0-321</math>, where there are 322 digits in <math>11...0</math>. ~ BJHHar<br />
<br />
==Solution 2==<br />
We can see that <math>9=9</math>, <math>9+99=108</math>, <math>9+99+999=1107</math>, all the way to ten nines when we have <math>11111111100</math>. Then, when we add more nines, we repeat the same process, and quickly get that the sum of digits is <math>\boxed{342}</math> since we have to add <math>9\lfloor \log 321 \rfloor</math> to the sum of digits, which is <math>9\lceil \frac{321}9 \rceil</math>.<br />
<br />
==Video Solution==<br />
https://www.youtube.com/watch?v=JFHjpxoYLDk<br />
<br />
==See Also==<br />
<br />
{{AIME box|year=2019|n=I|before=First Problem|num-a=2}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_13&diff=1128412019 AMC 12B Problems/Problem 132019-12-14T04:56:54Z<p>Bjhhar: </p>
<hr />
<div>{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #17]] and [[2019 AMC 12B Problems|2019 AMC 12B #13]]}}<br />
==Problem==<br />
<br />
A red ball and a green ball are randomly and independently tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>k</math> is <math>2^{-k}</math> for <math>k = 1,2,3....</math> What is the probability that the red ball is tossed into a higher-numbered bin than the green ball?<br><br />
<math>\textbf{(A) } \frac{1}{4} \qquad\textbf{(B) } \frac{2}{7} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{3}{8} \qquad\textbf{(E) } \frac{3}{7}</math><br />
<br />
==Solution 1==<br />
By symmetry, the probability of the red ball landing in a higher-numbered bin is the same as the probability of the green ball landing in a higher-numbered bin. Clearly, the probability of both landing in the same bin is <math>\sum_{k=1}^{\infty}{2^{-k} \cdot 2^{-k}} = \sum_{k=1}^{\infty}2^{-2k} = \frac{1}{3}</math> (by the geometric series sum formula). Therefore the other two probabilities have to both be <math>\frac{1-\frac{1}{3}}{2} = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 2==<br />
Suppose the green ball goes in bin <math>i</math>, for some <math>i \ge 1</math>. The probability of this occurring is <math>\frac{1}{2^i}</math>. Given that this occurs, the probability that the red ball goes in a higher-numbered bin is <math>\frac{1}{2^{i+1}} + \frac{1}{2^{i+2}} + \ldots = \frac{1}{2^i}</math> (by the geometric series sum formula). Thus the probability that the green ball goes in bin <math>i</math>, and the red ball goes in a bin greater than <math>i</math>, is <math>\left(\frac{1}{2^i}\right)^2 = \frac{1}{4^i}</math>. Summing from <math>i=1</math> to infinity, we get<br />
<br />
<cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
where we again used the geometric series sum formula. (Alternatively, if this sum equals <math>n</math>, then by writing out the terms and multiplying both sides by <math>4</math>, we see <math>4n = n+1</math>, which gives <math>n = \frac{1}{3}</math>.)<br />
<br />
==Solution 3 (Summations)==<br />
For red ball in bin <math>k</math>, <math>\Pr(\text{Green Below Red})=\sum\limits_{i=1}^{k-1}2^{-i}</math> (GBR) and <math>\Pr(\text{Red in Bin k}=2^{-k}</math> (RB). <br />
<cmath>\Pr(\text{GBR}|\text{RB})=\sum\limits_{k=1}^{\infty}2^{-k}\sum\limits_{i=1}^{k-1}2^{-i}=\sum\limits_{k=1}^{\infty}2^{-k}\cdot\frac{1}{2}(\frac{1-(1/2)^{k-1}}{1-1/2})</cmath><br />
<cmath>\sum\limits_{k=1}^{\infty}\frac{1}{2^{-k}}-2\sum\limits_{k=1}^\infty\frac{1}{(2^2)^{-k}}\implies 1-2/3=\boxed{\textbf{D}) \frac{1}{3}}</cmath><br />
<br />
~BJHHar<br />
<br />
<br />
==Solution 4==<br />
The probability that the two balls will go into adjacent bins is <math>\frac{1}{2\times4} + \frac{1}{4\times8} + \frac{1}{8 \times 16} + ... = \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots = \frac{1}{6}</math> by the geometric series sum formula. Similarly, the probability that the two balls will go into bins that have a distance of <math>2</math> from each other is <math>\frac{1}{2 \times 8} + \frac{1}{4 \times 16} + \frac{1}{8 \times 32} + \cdots = \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{12}</math> (again recognizing a geometric series). We can see that each time we add a bin between the two balls, the probability halves. Thus, our answer is <math>\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \cdots</math>, which, by the geometric series sum formula, is <math>\boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
-fidgetboss_4000<br />
<br />
==Solution 5 (quick, conceptual)==<br />
Define a win as a ball appearing in higher numbered box.<br />
<br />
Start from the first box. <br />
<br />
There are <math>4</math> possible results in the box: Red, Green, Red and Green, or none, with an equal probability of <math>\frac{1}{4}</math> for each. If none of the balls is in the first box, the game restarts at the second box with the same kind of probability distribution, so if <math>p</math> is the probability that Red wins, we can write <math>p = \frac{1}{4} + \frac{1}{4}p</math>: there is a <math>\frac{1}{4}</math> probability that "Red" wins immediately, a <math>0</math> probability in the cases "Green" or "Red and Green", and in the "None" case (which occurs with <math>\frac{1}{4}</math> probability), we then start again, giving the same probability <math>p</math>. Hence, solving the equation, we get <math>p = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 6==<br />
Write out the infinite geometric series as <math>\frac{1}{2}</math>, <math>\frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \cdots</math>. To find the probablilty that red goes in a higher-numbered bin than green, we can simply remove all odd-index terms (i.e term <math>1</math>, term <math>3</math>, etc.), and then sum the remaining terms - this is in fact precisely equivalent to the method of Solution 2. Writing this out as another infinite geometric sequence, we are left with <math>\frac{1}{4}, \frac{1}{16}, \frac{1}{64}, \cdots</math>. Summing, we get <cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
<br />
==Video Solution==<br />
For those who want a video solution: https://youtu.be/VP7ltu-XEq8<br />
<br />
==See Also==<br />
{{AMC10 box|year=2019|ab=B|num-b=16|num-a=18}}<br />
{{AMC12 box|year=2019|ab=B|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_13&diff=1128402019 AMC 12B Problems/Problem 132019-12-14T04:52:48Z<p>Bjhhar: /* Solution 6 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #17]] and [[2019 AMC 12B Problems|2019 AMC 12B #13]]}}<br />
==Problem==<br />
<br />
A red ball and a green ball are randomly and independently tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>k</math> is <math>2^{-k}</math> for <math>k = 1,2,3....</math> What is the probability that the red ball is tossed into a higher-numbered bin than the green ball?<br><br />
<math>\textbf{(A) } \frac{1}{4} \qquad\textbf{(B) } \frac{2}{7} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{3}{8} \qquad\textbf{(E) } \frac{3}{7}</math><br />
<br />
==Solution 1==<br />
By symmetry, the probability of the red ball landing in a higher-numbered bin is the same as the probability of the green ball landing in a higher-numbered bin. Clearly, the probability of both landing in the same bin is <math>\sum_{k=1}^{\infty}{2^{-k} \cdot 2^{-k}} = \sum_{k=1}^{\infty}2^{-2k} = \frac{1}{3}</math> (by the geometric series sum formula). Therefore the other two probabilities have to both be <math>\frac{1-\frac{1}{3}}{2} = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 2==<br />
Suppose the green ball goes in bin <math>i</math>, for some <math>i \ge 1</math>. The probability of this occurring is <math>\frac{1}{2^i}</math>. Given that this occurs, the probability that the red ball goes in a higher-numbered bin is <math>\frac{1}{2^{i+1}} + \frac{1}{2^{i+2}} + \ldots = \frac{1}{2^i}</math> (by the geometric series sum formula). Thus the probability that the green ball goes in bin <math>i</math>, and the red ball goes in a bin greater than <math>i</math>, is <math>\left(\frac{1}{2^i}\right)^2 = \frac{1}{4^i}</math>. Summing from <math>i=1</math> to infinity, we get<br />
<br />
<cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
where we again used the geometric series sum formula. (Alternatively, if this sum equals <math>n</math>, then by writing out the terms and multiplying both sides by <math>4</math>, we see <math>4n = n+1</math>, which gives <math>n = \frac{1}{3}</math>.)<br />
<br />
==Solution 3==<br />
The probability that the two balls will go into adjacent bins is <math>\frac{1}{2\times4} + \frac{1}{4\times8} + \frac{1}{8 \times 16} + ... = \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots = \frac{1}{6}</math> by the geometric series sum formula. Similarly, the probability that the two balls will go into bins that have a distance of <math>2</math> from each other is <math>\frac{1}{2 \times 8} + \frac{1}{4 \times 16} + \frac{1}{8 \times 32} + \cdots = \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{12}</math> (again recognizing a geometric series). We can see that each time we add a bin between the two balls, the probability halves. Thus, our answer is <math>\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \cdots</math>, which, by the geometric series sum formula, is <math>\boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
-fidgetboss_4000<br />
<br />
==Solution 4 (quick, conceptual)==<br />
Define a win as a ball appearing in higher numbered box.<br />
<br />
Start from the first box. <br />
<br />
There are <math>4</math> possible results in the box: Red, Green, Red and Green, or none, with an equal probability of <math>\frac{1}{4}</math> for each. If none of the balls is in the first box, the game restarts at the second box with the same kind of probability distribution, so if <math>p</math> is the probability that Red wins, we can write <math>p = \frac{1}{4} + \frac{1}{4}p</math>: there is a <math>\frac{1}{4}</math> probability that "Red" wins immediately, a <math>0</math> probability in the cases "Green" or "Red and Green", and in the "None" case (which occurs with <math>\frac{1}{4}</math> probability), we then start again, giving the same probability <math>p</math>. Hence, solving the equation, we get <math>p = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 5==<br />
Write out the infinite geometric series as <math>\frac{1}{2}</math>, <math>\frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \cdots</math>. To find the probablilty that red goes in a higher-numbered bin than green, we can simply remove all odd-index terms (i.e term <math>1</math>, term <math>3</math>, etc.), and then sum the remaining terms - this is in fact precisely equivalent to the method of Solution 2. Writing this out as another infinite geometric sequence, we are left with <math>\frac{1}{4}, \frac{1}{16}, \frac{1}{64}, \cdots</math>. Summing, we get <cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
<br />
==Solution 6 ==<br />
For red ball in bin <math>k</math>, <math>\P(\text{Green Below Red})=\sum\limits_{i=1}^{k-1}2^{-i}</math> (GBR) and <math>\P(\text{Red in Bin k}=2^{-k}</math> (RB). <br />
<cmath>P(\text{GBR}|\text{RB})=\sum\limits_{k=1}^{\infty}2^{-k}\sum\limits_{i=1}^{k-1}2^{-i}=\sum\limits_{k=1}^{\infty}2^{-k}\cdot\frac{1}{2}(\frac{1-(1/2)^{k-1}}{1-1/2})</cmath>. Simplifying:<br />
<cmath>\sum\limits_{k=1}^{\infty}\frac{1}{2^{-k}}-2\sum\limits_{k=1}^\infty\frac{1}{(2^2)^{-k}}\implies 1-2/3=\boxed{\textbf{D}) \frac{1}{3}}</cmath><br />
<br />
~BJHHar<br />
<br />
==Video Solution==<br />
For those who want a video solution: https://youtu.be/VP7ltu-XEq8<br />
<br />
==See Also==<br />
{{AMC10 box|year=2019|ab=B|num-b=16|num-a=18}}<br />
{{AMC12 box|year=2019|ab=B|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_13&diff=1128392019 AMC 12B Problems/Problem 132019-12-14T04:47:30Z<p>Bjhhar: /* Solution 6 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #17]] and [[2019 AMC 12B Problems|2019 AMC 12B #13]]}}<br />
==Problem==<br />
<br />
A red ball and a green ball are randomly and independently tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>k</math> is <math>2^{-k}</math> for <math>k = 1,2,3....</math> What is the probability that the red ball is tossed into a higher-numbered bin than the green ball?<br><br />
<math>\textbf{(A) } \frac{1}{4} \qquad\textbf{(B) } \frac{2}{7} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{3}{8} \qquad\textbf{(E) } \frac{3}{7}</math><br />
<br />
==Solution 1==<br />
By symmetry, the probability of the red ball landing in a higher-numbered bin is the same as the probability of the green ball landing in a higher-numbered bin. Clearly, the probability of both landing in the same bin is <math>\sum_{k=1}^{\infty}{2^{-k} \cdot 2^{-k}} = \sum_{k=1}^{\infty}2^{-2k} = \frac{1}{3}</math> (by the geometric series sum formula). Therefore the other two probabilities have to both be <math>\frac{1-\frac{1}{3}}{2} = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 2==<br />
Suppose the green ball goes in bin <math>i</math>, for some <math>i \ge 1</math>. The probability of this occurring is <math>\frac{1}{2^i}</math>. Given that this occurs, the probability that the red ball goes in a higher-numbered bin is <math>\frac{1}{2^{i+1}} + \frac{1}{2^{i+2}} + \ldots = \frac{1}{2^i}</math> (by the geometric series sum formula). Thus the probability that the green ball goes in bin <math>i</math>, and the red ball goes in a bin greater than <math>i</math>, is <math>\left(\frac{1}{2^i}\right)^2 = \frac{1}{4^i}</math>. Summing from <math>i=1</math> to infinity, we get<br />
<br />
<cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
where we again used the geometric series sum formula. (Alternatively, if this sum equals <math>n</math>, then by writing out the terms and multiplying both sides by <math>4</math>, we see <math>4n = n+1</math>, which gives <math>n = \frac{1}{3}</math>.)<br />
<br />
==Solution 3==<br />
The probability that the two balls will go into adjacent bins is <math>\frac{1}{2\times4} + \frac{1}{4\times8} + \frac{1}{8 \times 16} + ... = \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots = \frac{1}{6}</math> by the geometric series sum formula. Similarly, the probability that the two balls will go into bins that have a distance of <math>2</math> from each other is <math>\frac{1}{2 \times 8} + \frac{1}{4 \times 16} + \frac{1}{8 \times 32} + \cdots = \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{12}</math> (again recognizing a geometric series). We can see that each time we add a bin between the two balls, the probability halves. Thus, our answer is <math>\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \cdots</math>, which, by the geometric series sum formula, is <math>\boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
-fidgetboss_4000<br />
<br />
==Solution 4 (quick, conceptual)==<br />
Define a win as a ball appearing in higher numbered box.<br />
<br />
Start from the first box. <br />
<br />
There are <math>4</math> possible results in the box: Red, Green, Red and Green, or none, with an equal probability of <math>\frac{1}{4}</math> for each. If none of the balls is in the first box, the game restarts at the second box with the same kind of probability distribution, so if <math>p</math> is the probability that Red wins, we can write <math>p = \frac{1}{4} + \frac{1}{4}p</math>: there is a <math>\frac{1}{4}</math> probability that "Red" wins immediately, a <math>0</math> probability in the cases "Green" or "Red and Green", and in the "None" case (which occurs with <math>\frac{1}{4}</math> probability), we then start again, giving the same probability <math>p</math>. Hence, solving the equation, we get <math>p = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 5==<br />
Write out the infinite geometric series as <math>\frac{1}{2}</math>, <math>\frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \cdots</math>. To find the probablilty that red goes in a higher-numbered bin than green, we can simply remove all odd-index terms (i.e term <math>1</math>, term <math>3</math>, etc.), and then sum the remaining terms - this is in fact precisely equivalent to the method of Solution 2. Writing this out as another infinite geometric sequence, we are left with <math>\frac{1}{4}, \frac{1}{16}, \frac{1}{64}, \cdots</math>. Summing, we get <cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
<br />
==Solution 6 ==<br />
Probability that the green ball is in a bin below red for red in bin <math>k</math> is <math>\sum\limits_{i=1}^{k-1}2^{-i}</math>. There's a <math>2^{-k}</math> chance for red to be in that bin. Then, <math>P(\text{Green below Red}|\text{Red}=k)=\sum\limits_{k=1}^{\infty}2^{-k}\sum\limits_{i=1}^{k-1}2^{-i}</math>. By geometric series formula his is <br />
<math>\sum\limits_{k=1}^{\infty}2^{-k}\cdot\frac{1}{2}(\frac{1-(1/2)^{k-1}}{1-1/2})</math><br />
<cmath>\sum\limits_{k=1}^{\infty}\frac{1}{2^{-k}}-2\sum\limits_{k=1}^\infty\frac{1}{(2^2)^{-k}}\implies 1-2/3=\boxed{\textbf{D}) \frac{1}{3}}</cmath><br />
<br />
~BJHHar<br />
<br />
==Video Solution==<br />
For those who want a video solution: https://youtu.be/VP7ltu-XEq8<br />
<br />
==See Also==<br />
{{AMC10 box|year=2019|ab=B|num-b=16|num-a=18}}<br />
{{AMC12 box|year=2019|ab=B|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_13&diff=1128382019 AMC 12B Problems/Problem 132019-12-14T04:47:08Z<p>Bjhhar: /* Solution 6 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #17]] and [[2019 AMC 12B Problems|2019 AMC 12B #13]]}}<br />
==Problem==<br />
<br />
A red ball and a green ball are randomly and independently tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>k</math> is <math>2^{-k}</math> for <math>k = 1,2,3....</math> What is the probability that the red ball is tossed into a higher-numbered bin than the green ball?<br><br />
<math>\textbf{(A) } \frac{1}{4} \qquad\textbf{(B) } \frac{2}{7} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{3}{8} \qquad\textbf{(E) } \frac{3}{7}</math><br />
<br />
==Solution 1==<br />
By symmetry, the probability of the red ball landing in a higher-numbered bin is the same as the probability of the green ball landing in a higher-numbered bin. Clearly, the probability of both landing in the same bin is <math>\sum_{k=1}^{\infty}{2^{-k} \cdot 2^{-k}} = \sum_{k=1}^{\infty}2^{-2k} = \frac{1}{3}</math> (by the geometric series sum formula). Therefore the other two probabilities have to both be <math>\frac{1-\frac{1}{3}}{2} = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 2==<br />
Suppose the green ball goes in bin <math>i</math>, for some <math>i \ge 1</math>. The probability of this occurring is <math>\frac{1}{2^i}</math>. Given that this occurs, the probability that the red ball goes in a higher-numbered bin is <math>\frac{1}{2^{i+1}} + \frac{1}{2^{i+2}} + \ldots = \frac{1}{2^i}</math> (by the geometric series sum formula). Thus the probability that the green ball goes in bin <math>i</math>, and the red ball goes in a bin greater than <math>i</math>, is <math>\left(\frac{1}{2^i}\right)^2 = \frac{1}{4^i}</math>. Summing from <math>i=1</math> to infinity, we get<br />
<br />
<cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
where we again used the geometric series sum formula. (Alternatively, if this sum equals <math>n</math>, then by writing out the terms and multiplying both sides by <math>4</math>, we see <math>4n = n+1</math>, which gives <math>n = \frac{1}{3}</math>.)<br />
<br />
==Solution 3==<br />
The probability that the two balls will go into adjacent bins is <math>\frac{1}{2\times4} + \frac{1}{4\times8} + \frac{1}{8 \times 16} + ... = \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots = \frac{1}{6}</math> by the geometric series sum formula. Similarly, the probability that the two balls will go into bins that have a distance of <math>2</math> from each other is <math>\frac{1}{2 \times 8} + \frac{1}{4 \times 16} + \frac{1}{8 \times 32} + \cdots = \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{12}</math> (again recognizing a geometric series). We can see that each time we add a bin between the two balls, the probability halves. Thus, our answer is <math>\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \cdots</math>, which, by the geometric series sum formula, is <math>\boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
-fidgetboss_4000<br />
<br />
==Solution 4 (quick, conceptual)==<br />
Define a win as a ball appearing in higher numbered box.<br />
<br />
Start from the first box. <br />
<br />
There are <math>4</math> possible results in the box: Red, Green, Red and Green, or none, with an equal probability of <math>\frac{1}{4}</math> for each. If none of the balls is in the first box, the game restarts at the second box with the same kind of probability distribution, so if <math>p</math> is the probability that Red wins, we can write <math>p = \frac{1}{4} + \frac{1}{4}p</math>: there is a <math>\frac{1}{4}</math> probability that "Red" wins immediately, a <math>0</math> probability in the cases "Green" or "Red and Green", and in the "None" case (which occurs with <math>\frac{1}{4}</math> probability), we then start again, giving the same probability <math>p</math>. Hence, solving the equation, we get <math>p = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 5==<br />
Write out the infinite geometric series as <math>\frac{1}{2}</math>, <math>\frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \cdots</math>. To find the probablilty that red goes in a higher-numbered bin than green, we can simply remove all odd-index terms (i.e term <math>1</math>, term <math>3</math>, etc.), and then sum the remaining terms - this is in fact precisely equivalent to the method of Solution 2. Writing this out as another infinite geometric sequence, we are left with <math>\frac{1}{4}, \frac{1}{16}, \frac{1}{64}, \cdots</math>. Summing, we get <cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
<br />
==Solution 6 ==<br />
Probability that the green ball is in a bin below red for red in bin <math>k</math> is <math>\sum\limits_{i=1}^{k-1}2^{-i}</math>. There's a <math>2^{-k}</math> chance for red to be in that bin. Then, <math>P(\text{Green below Red}|\text{Red}=k)=\sum\limits_{k=1}^{\infty}2^{-k}\sum\limits_{i=1}^{k-1}2^{-i}</math>. By geometric series formula his is <br />
<math>\sum\limits_{i=1}^{\infty}2^{-k}\cdot\frac{1}{2}(\frac{1-(1/2)^{k-1}}{1-1/2})</math><br />
<cmath>\sum\limits_{k=1}^{\infty}\frac{1}{2^{-k}}-2\sum\limits_{k=1}^\infty\frac{1}{(2^2)^{-k}}\implies 1-2/3=\boxed{\textbf{D}) \frac{1}{3}}</cmath><br />
<br />
~BJHHar<br />
<br />
==Video Solution==<br />
For those who want a video solution: https://youtu.be/VP7ltu-XEq8<br />
<br />
==See Also==<br />
{{AMC10 box|year=2019|ab=B|num-b=16|num-a=18}}<br />
{{AMC12 box|year=2019|ab=B|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_13&diff=1128372019 AMC 12B Problems/Problem 132019-12-14T04:46:11Z<p>Bjhhar: /* Solution 6 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #17]] and [[2019 AMC 12B Problems|2019 AMC 12B #13]]}}<br />
==Problem==<br />
<br />
A red ball and a green ball are randomly and independently tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>k</math> is <math>2^{-k}</math> for <math>k = 1,2,3....</math> What is the probability that the red ball is tossed into a higher-numbered bin than the green ball?<br><br />
<math>\textbf{(A) } \frac{1}{4} \qquad\textbf{(B) } \frac{2}{7} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{3}{8} \qquad\textbf{(E) } \frac{3}{7}</math><br />
<br />
==Solution 1==<br />
By symmetry, the probability of the red ball landing in a higher-numbered bin is the same as the probability of the green ball landing in a higher-numbered bin. Clearly, the probability of both landing in the same bin is <math>\sum_{k=1}^{\infty}{2^{-k} \cdot 2^{-k}} = \sum_{k=1}^{\infty}2^{-2k} = \frac{1}{3}</math> (by the geometric series sum formula). Therefore the other two probabilities have to both be <math>\frac{1-\frac{1}{3}}{2} = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 2==<br />
Suppose the green ball goes in bin <math>i</math>, for some <math>i \ge 1</math>. The probability of this occurring is <math>\frac{1}{2^i}</math>. Given that this occurs, the probability that the red ball goes in a higher-numbered bin is <math>\frac{1}{2^{i+1}} + \frac{1}{2^{i+2}} + \ldots = \frac{1}{2^i}</math> (by the geometric series sum formula). Thus the probability that the green ball goes in bin <math>i</math>, and the red ball goes in a bin greater than <math>i</math>, is <math>\left(\frac{1}{2^i}\right)^2 = \frac{1}{4^i}</math>. Summing from <math>i=1</math> to infinity, we get<br />
<br />
<cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
where we again used the geometric series sum formula. (Alternatively, if this sum equals <math>n</math>, then by writing out the terms and multiplying both sides by <math>4</math>, we see <math>4n = n+1</math>, which gives <math>n = \frac{1}{3}</math>.)<br />
<br />
==Solution 3==<br />
The probability that the two balls will go into adjacent bins is <math>\frac{1}{2\times4} + \frac{1}{4\times8} + \frac{1}{8 \times 16} + ... = \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots = \frac{1}{6}</math> by the geometric series sum formula. Similarly, the probability that the two balls will go into bins that have a distance of <math>2</math> from each other is <math>\frac{1}{2 \times 8} + \frac{1}{4 \times 16} + \frac{1}{8 \times 32} + \cdots = \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{12}</math> (again recognizing a geometric series). We can see that each time we add a bin between the two balls, the probability halves. Thus, our answer is <math>\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \cdots</math>, which, by the geometric series sum formula, is <math>\boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
-fidgetboss_4000<br />
<br />
==Solution 4 (quick, conceptual)==<br />
Define a win as a ball appearing in higher numbered box.<br />
<br />
Start from the first box. <br />
<br />
There are <math>4</math> possible results in the box: Red, Green, Red and Green, or none, with an equal probability of <math>\frac{1}{4}</math> for each. If none of the balls is in the first box, the game restarts at the second box with the same kind of probability distribution, so if <math>p</math> is the probability that Red wins, we can write <math>p = \frac{1}{4} + \frac{1}{4}p</math>: there is a <math>\frac{1}{4}</math> probability that "Red" wins immediately, a <math>0</math> probability in the cases "Green" or "Red and Green", and in the "None" case (which occurs with <math>\frac{1}{4}</math> probability), we then start again, giving the same probability <math>p</math>. Hence, solving the equation, we get <math>p = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 5==<br />
Write out the infinite geometric series as <math>\frac{1}{2}</math>, <math>\frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \cdots</math>. To find the probablilty that red goes in a higher-numbered bin than green, we can simply remove all odd-index terms (i.e term <math>1</math>, term <math>3</math>, etc.), and then sum the remaining terms - this is in fact precisely equivalent to the method of Solution 2. Writing this out as another infinite geometric sequence, we are left with <math>\frac{1}{4}, \frac{1}{16}, \frac{1}{64}, \cdots</math>. Summing, we get <cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
<br />
==Solution 6 ==<br />
Probability that the green ball is in a bin below red for red in bin <math>k</math> is <math>\sum\limits_{i=1}^{k-1}2^{-i}</math>. There's a <math>2^{-k}</math> chance for red to be in that bin. Then, <math>P(\text{Green below Red}|\text{Red}=k)=\sum\limits_{k=1}^{\infty}2^{-k}\sum\limits_{i=1}^{k-1}2^{-i}</math>. By geometric series formula his is <br />
<math>\sum\limits_{i=1}^{\infty}2^{-i}\cdot\frac{1}{2}(\frac{1-(1/2)^{k-1}}{1-1/2})</math><br />
<cmath>\sum\limits_{i=1}^{\infty}\frac{1}{2^{-i}}-2\sum\limits_{i=1}^\infty\frac{1}{(2^2)^{-i}}\implies 1-2/3=\boxed{\textbf{D}) \frac{1}{3}}</cmath><br />
<br />
~BJHHar<br />
<br />
==Video Solution==<br />
For those who want a video solution: https://youtu.be/VP7ltu-XEq8<br />
<br />
==See Also==<br />
{{AMC10 box|year=2019|ab=B|num-b=16|num-a=18}}<br />
{{AMC12 box|year=2019|ab=B|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhharhttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_12B_Problems/Problem_13&diff=1128362019 AMC 12B Problems/Problem 132019-12-14T04:45:11Z<p>Bjhhar: </p>
<hr />
<div>{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #17]] and [[2019 AMC 12B Problems|2019 AMC 12B #13]]}}<br />
==Problem==<br />
<br />
A red ball and a green ball are randomly and independently tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>k</math> is <math>2^{-k}</math> for <math>k = 1,2,3....</math> What is the probability that the red ball is tossed into a higher-numbered bin than the green ball?<br><br />
<math>\textbf{(A) } \frac{1}{4} \qquad\textbf{(B) } \frac{2}{7} \qquad\textbf{(C) } \frac{1}{3} \qquad\textbf{(D) } \frac{3}{8} \qquad\textbf{(E) } \frac{3}{7}</math><br />
<br />
==Solution 1==<br />
By symmetry, the probability of the red ball landing in a higher-numbered bin is the same as the probability of the green ball landing in a higher-numbered bin. Clearly, the probability of both landing in the same bin is <math>\sum_{k=1}^{\infty}{2^{-k} \cdot 2^{-k}} = \sum_{k=1}^{\infty}2^{-2k} = \frac{1}{3}</math> (by the geometric series sum formula). Therefore the other two probabilities have to both be <math>\frac{1-\frac{1}{3}}{2} = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 2==<br />
Suppose the green ball goes in bin <math>i</math>, for some <math>i \ge 1</math>. The probability of this occurring is <math>\frac{1}{2^i}</math>. Given that this occurs, the probability that the red ball goes in a higher-numbered bin is <math>\frac{1}{2^{i+1}} + \frac{1}{2^{i+2}} + \ldots = \frac{1}{2^i}</math> (by the geometric series sum formula). Thus the probability that the green ball goes in bin <math>i</math>, and the red ball goes in a bin greater than <math>i</math>, is <math>\left(\frac{1}{2^i}\right)^2 = \frac{1}{4^i}</math>. Summing from <math>i=1</math> to infinity, we get<br />
<br />
<cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
where we again used the geometric series sum formula. (Alternatively, if this sum equals <math>n</math>, then by writing out the terms and multiplying both sides by <math>4</math>, we see <math>4n = n+1</math>, which gives <math>n = \frac{1}{3}</math>.)<br />
<br />
==Solution 3==<br />
The probability that the two balls will go into adjacent bins is <math>\frac{1}{2\times4} + \frac{1}{4\times8} + \frac{1}{8 \times 16} + ... = \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots = \frac{1}{6}</math> by the geometric series sum formula. Similarly, the probability that the two balls will go into bins that have a distance of <math>2</math> from each other is <math>\frac{1}{2 \times 8} + \frac{1}{4 \times 16} + \frac{1}{8 \times 32} + \cdots = \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{12}</math> (again recognizing a geometric series). We can see that each time we add a bin between the two balls, the probability halves. Thus, our answer is <math>\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \cdots</math>, which, by the geometric series sum formula, is <math>\boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
-fidgetboss_4000<br />
<br />
==Solution 4 (quick, conceptual)==<br />
Define a win as a ball appearing in higher numbered box.<br />
<br />
Start from the first box. <br />
<br />
There are <math>4</math> possible results in the box: Red, Green, Red and Green, or none, with an equal probability of <math>\frac{1}{4}</math> for each. If none of the balls is in the first box, the game restarts at the second box with the same kind of probability distribution, so if <math>p</math> is the probability that Red wins, we can write <math>p = \frac{1}{4} + \frac{1}{4}p</math>: there is a <math>\frac{1}{4}</math> probability that "Red" wins immediately, a <math>0</math> probability in the cases "Green" or "Red and Green", and in the "None" case (which occurs with <math>\frac{1}{4}</math> probability), we then start again, giving the same probability <math>p</math>. Hence, solving the equation, we get <math>p = \boxed{\textbf{(C) } \frac{1}{3}}</math>.<br />
<br />
==Solution 5==<br />
Write out the infinite geometric series as <math>\frac{1}{2}</math>, <math>\frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \cdots</math>. To find the probablilty that red goes in a higher-numbered bin than green, we can simply remove all odd-index terms (i.e term <math>1</math>, term <math>3</math>, etc.), and then sum the remaining terms - this is in fact precisely equivalent to the method of Solution 2. Writing this out as another infinite geometric sequence, we are left with <math>\frac{1}{4}, \frac{1}{16}, \frac{1}{64}, \cdots</math>. Summing, we get <cmath>\sum_{i=1}^{\infty} \frac{1}{4^i} = \boxed{\textbf{(C) } \frac{1}{3}}</cmath><br />
<br />
==Solution 6 ==<br />
Probability that the green ball is in a bin below red for red in bin <math>k</math> is <math>\sum\limits_{i=1}^{k-1}2^{-i}</math>. There's a <math>2^{-k}</math> chance for red to be in that bin. Then, <math>P(\text{Green below Red}|\text{Red}=k)=\sum\limits_{k=1}^{\infty}2^{-k}\sum\limits_{i=1}^{k-1}2^{-i}</math>. By geometric series formula his is <br />
<math>\sum\limits_{i=1}^{\infty}2^{-i}\cdot\frac{1}{2}(\frac{1-(1/2)^k-1}{1-1/2})</math> or,<br />
<cmath>\sum\limits_{i=1}^{\infty}\frac{1}{2^{-i}}-2\sum\limits_{i=1}^\infty\frac{1}{(2^2)^{-i}}\implies 1-2/3=\boxed{\textbf{D}) \frac{1}{3}}</cmath><br />
<br />
~BJHHar<br />
<br />
==Video Solution==<br />
For those who want a video solution: https://youtu.be/VP7ltu-XEq8<br />
<br />
==See Also==<br />
{{AMC10 box|year=2019|ab=B|num-b=16|num-a=18}}<br />
{{AMC12 box|year=2019|ab=B|num-b=12|num-a=14}}<br />
{{MAA Notice}}</div>Bjhhar