https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Rejas&feedformat=atomAoPS Wiki - User contributions [en]2024-03-19T03:44:23ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_19&diff=1174422020 AMC 12B Problems/Problem 192020-02-08T16:11:35Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>Square <math>ABCD</math> in the coordinate plane has vertices at the points <math>A(1,1), B(-1,1), C(-1,-1),</math> and <math>D(1,-1).</math> Consider the following four transformations: <math>L,</math> a rotation of <math>90^{\circ}</math> counterclockwise around the origin; <math>R,</math> a rotation of <math>90^{\circ}</math> clockwise around the origin; <math>H,</math> a reflection across the <math>x</math>-axis; and <math>V,</math> a reflection across the <math>y</math>-axis.<br />
<br />
Each of these transformations maps the squares onto itself, but the positions of the labeled vertices will change. For example, applying <math>R</math> and then <math>V</math> would send the vertex <math>A</math> at <math>(1,1)</math> to <math>(-1,-1)</math> and would send the vertex <math>B</math> at <math>(-1,1)</math> to itself. How many sequences of <math>20</math> transformations chosen from <math>\{L, R, H, V\}</math> will send all of the labeled vertices back to their original positions? (For example, <math>R, R, V, H</math> is one sequence of <math>4</math> transformations that will send the vertices back to their original positions.)<br />
<br />
<math>\textbf{(A)}\ 2^{37} \qquad\textbf{(B)}\ 3\cdot 2^{36} \qquad\textbf{(C)}\ 2^{38} \qquad\textbf{(D)}\ 3\cdot 2^{37} \qquad\textbf{(E)}\ 2^{39}</math><br />
<br />
==Solution==<br />
<br />
Hopefully, someone will think of a better one, but here is an indirect answer, use only if you are really desperate.<br />
<math>20</math> moves can be made, and each move have <math>4</math> choices, so a total of <math>4^{20}=2^{40}</math> moves. First, after the <math>20</math> moves, Point A can only be in first quadrant <math>(1,1)</math> or third quadrant <math>(-1,-1)</math>. Only the one in the first quadrant works, so divide by <math>2</math>. Now, C must be in the opposite quadrant as A. B can be either in the second (<math>(-1, 1)</math>) or fourth quadrant (<math>(1, -1)</math>) , but we want it to be in the second quadrant, so divide by <math>2</math> again. Now as A and B satisfy the conditions, C and D will also be at their original spot. <math>\frac{2^{40}}{2\cdot2}=2^{38}</math>. The answer is <math>\boxed{C}</math> <br />
~Kinglogic<br />
<br />
==Solution 2==<br />
<br />
The total number of sequence is <math>4^{20}=2^{40}</math>.<br />
<br />
Note that there can only be even number of reflections since they result in the same anti-clockwise orientation of the verices <math>A,B,C,D</math>. Therefore, the probability of having the same anti-clockwise orientation with the original arrangement after the transformation is <math>\frac{1}{2}</math>.<br />
<br />
<br />
<br />
Next, even number of reflections mean that there must be even number of rotations since their sum is even. Even rotations result only in the original position or <math>180^{\circ}</math> rotation of it. <br />
<br />
Since rotation <math>R</math> and rotation <math>L</math> cancels each other out, the difference between the numbers of them define the final position. The probability of the transformation returning the vertices to the orginal position given that there are even number of rotations is equivalent to the probability that<br />
<br />
<center><math>|n(R)-n(L)|\equiv0\pmod{4}</math> when <math>|n(H)-n(V)|\equiv0\pmod{4}</math></center><br />
<center>or</center><br />
<center><math>|n(R)-n(L)|\equiv2\pmod{4}</math> when <math>|n(H)-n(V)|\equiv2\pmod{4}</math></center><br />
<br />
which is again, <math>\frac{1}{2}</math>.<br />
<br />
Therefore, <math>2^{40}\cdot\frac{1}{2}\cdot\frac{1}{2}=\boxed{\textbf{(C) }2^{38}}</math><br />
~joshuamh111<br />
<br />
==Solution 3==<br />
Notice that any pair of two of these transformations either swaps the x and y-coordinates, negates the x and y-coordinates, swaps and negates the x and y-coordinates, or leaves the original unchanged. Furthermore, notice that for each of these results, if we apply another pair of transformations, one of these results will happen again, and with equal probability. Therefore, no matter what state after we apply the first <math>19</math> pairs of transformations, there is a <math>\frac14</math> chance the last pair of transformations will return the figure to its original position. Therefore, the answer is <math>\frac{4^{20}}4 = 4^{19} = \boxed{\textbf{(C) }2^{38}}</math><br />
<br />
{{AMC12 box|year=2020|ab=B|num-b=18|num-a=20}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_24&diff=1174402020 AMC 12B Problems/Problem 242020-02-08T15:31:44Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>Let <math>D(n)</math> denote the number of ways of writing the positive integer <math>n</math> as a product<cmath>n = f_1\cdot f_2\cdots f_k,</cmath>where <math>k\ge1</math>, the <math>f_i</math> are integers strictly greater than <math>1</math>, and the order in which the factors are listed matters (that is, two representations that differ only in the order of the factors are counted as distinct). For example, the number <math>6</math> can be written as <math>6</math>, <math>2\cdot 3</math>, and <math>3\cdot2</math>, so <math>D(6) = 3</math>. What is <math>D(96)</math>?<br />
<br />
<math>\textbf{(A) } 112 \qquad\textbf{(B) } 128 \qquad\textbf{(C) } 144 \qquad\textbf{(D) } 172 \qquad\textbf{(E) } 184</math><br />
<br />
==Solution 1==<br />
To make a product of <math>n</math>, we can either have just <math>n</math>, or we can have a divisor <math>d</math> of <math>n</math>, <math>1 < d < n</math>, followed by a way to make a product of <math>\frac{n}{d}</math>. Thus, <math>D(n) = 1 + \sum D(\frac{n}{d})</math> for all possible <math>d</math>. It's easy to calculate <math>D(n)</math> for all powers of <math>2</math>, since powers of <math>2</math> only have powers of <math>2</math> as divisors. We have<br />
<cmath>D(2) = 1</cmath><br />
<cmath>D(4) = 2</cmath><br />
<cmath>D(8) = 4</cmath><br />
<cmath>D(16) = 8</cmath><br />
<cmath>D(32) = 16</cmath><br />
Now we will calculate <math>D(n)</math> for all <math>n</math> in the form <math>3 \cdot 2^k</math>, for <math>k \geq 0</math>. Note that each divisor of <math>3 \cdot 2^k</math> is either of the form <math>2^j</math> or <math>3 \cdot 2^j</math>. Therefore, to calculate each <math>D(3 \cdot 2^k)</math>, we will sum the first <math>k</math> values in both the tables we created, and add <math>1</math>. We have<br />
<cmath>D(3) = 1</cmath><br />
<cmath>D(6) = 3</cmath><br />
<cmath>D(12) = 8</cmath><br />
<cmath>D(24) = 20</cmath><br />
<cmath>D(48) = 48</cmath><br />
<cmath>D(96) = \boxed{\textbf{(A) }112}</cmath><br />
<br />
==Solution 2==<br />
Bash.<br />
Since <math>96=2^5\times 3</math>, for the number of <math>f_n</math>, we have the following cases:<br />
<br />
Case 1: <math>n=1</math>, we have <math>\{f_1\}=\{96\}</math>, only 1 case.<br />
<br />
Case 2: <math>n=2</math>, we have <math>\{f_1,f_2\}=\{3,2^5\}, \{6,2^4\},...,\{48,2\}</math>, totally <math>5\cdot 2!=10</math> cases.<br />
<br />
Case 3: <math>n=3</math>, we have <math>\{f_1,f_2,f_3\}=\{3,2^3,2^2\},\{3,2^1,2^4\},\{6,2^2,2^2\},\{6,2^3,2^1\}, \{12,2^2,2^1\},\{24,2,2\}</math>, totally <math>\frac{3!}{2!}\cdot 2+4\cdot 3!=30</math> cases.<br />
<br />
Case 4: <math>n=4</math>, we have <math>\{f_1,f_2,f_3,f_4\}=\{3,2^2,2^2,2\},\{3,2^3,2,2\},\{6,2^2,2,2\},\{12,2,2,2\}</math>, totally <math>\frac{4!}{2!}\cdot 3+\frac{4!}{3!}=40</math> cases.<br />
<br />
Case 5: <math>n=5</math>, we have <math>\{f_1,f_2,f_3,f_4,f_5\}=\{3,2^2,2,2,2\},\{6,2,2,2,2\}</math>, totally <math>\frac{5!}{3!}+\frac{5!}{4!}=25</math> cases.<br />
<br />
Case 6: <math>n=6</math>, we have <math>\{f_1,f_2,f_3,f_4,f_5,f_6\}=\{3,2,2,2,2,2\}</math>, totally <math>\frac{6!}{5!}=6</math> cases.<br />
<br />
Thus, add all of them together, we have <math>1+10+30+40+25+6=112</math> cases. Put <math>\boxed{\textbf{(A) }112}</math>.<br />
<br />
~FANYUCHEN20020715<br />
<br />
==See Also==<br />
<br />
<br />
{{AMC12 box|year=2020|ab=B|num-b=23|num-a=25}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_12B_Problems/Problem_24&diff=1174392020 AMC 12B Problems/Problem 242020-02-08T15:30:19Z<p>Rejas: /* Solution */</p>
<hr />
<div>Let <math>D(n)</math> denote the number of ways of writing the positive integer <math>n</math> as a product<cmath>n = f_1\cdot f_2\cdots f_k,</cmath>where <math>k\ge1</math>, the <math>f_i</math> are integers strictly greater than <math>1</math>, and the order in which the factors are listed matters (that is, two representations that differ only in the order of the factors are counted as distinct). For example, the number <math>6</math> can be written as <math>6</math>, <math>2\cdot 3</math>, and <math>3\cdot2</math>, so <math>D(6) = 3</math>. What is <math>D(96)</math>?<br />
<br />
<math>\textbf{(A) } 112 \qquad\textbf{(B) } 128 \qquad\textbf{(C) } 144 \qquad\textbf{(D) } 172 \qquad\textbf{(E) } 184</math><br />
<br />
==Solution 1==<br />
To make a product of <math>n</math>, we can either have just <math>n</math>, or we can have a divisor <math>d</math> of <math>n</math>, <math>1 < d < n</math>, followed by a way to make a product of <math>\frac{n}{d}</math>. Thus, <math>D(n) = 1 + \sum D(\frac{n}{d})</math> for all possible <math>d</math>. It's easy to calculate <math>D(n)</math> for all powers of <math>2</math>, since powers of <math>2</math> only have powers of <math>2</math> as divisors. We have<br />
<cmath>D(2) = 1</cmath><br />
<cmath>D(4) = 2</cmath><br />
<cmath>D(8) = 4</cmath><br />
<cmath>D(16) = 8</cmath><br />
<cmath>D(32) = 16</cmath><br />
Now we will calculate <math>D(n)</math> for all <math>n</math> in the form <math>3 \cdot 2^k</math>, for <math>k \geq 0</math>. Note that each divisor of <math>3 \cdot 2^k</math> is either of the form <math>2^j</math> or <math>3 \cdot 2^j</math>. Therefore, to calculate each <math>D(3 \cdot 2^k)</math>, we will sum the first <math>k</math> values in both the tables we created, and add <math>1</math>. We have<br />
<cmath>D(3) = 1</cmath><br />
<cmath>D(6) = 3</cmath><br />
<cmath>D(12) = 8</cmath><br />
<cmath>D(24) = 20</cmath><br />
<cmath>D(48) = 48</cmath><br />
<cmath>D(96) = \boxed{\textbf{(A) }112}</cmath><br />
<br />
==Solution 2==<br />
Bash.<br />
Since <math>96=2^5\times 3</math>, for the number of <math>f_n</math>, we have the following cases:<br />
<br />
Case 1: <math>n=1</math>, we have <math>\{f_1\}=\{96\}</math>, only 1 case.<br />
<br />
Case 2: <math>n=2</math>, we have <math>\{f_1,f_2\}=\{3,2^5\}, \{6,2^4\},...,\{48,2\}</math>, totally <math>5\cdot 2!=10</math> cases.<br />
<br />
Case 3: <math>n=3</math>, we have <math>\{f_1,f_2,f_3\}=\{3,2^3,2^2\},\{3,2^1,2^4\},\{6,2^2,2^2\},\{6,2^3,2^1\}, \{12,2^2,2^1\},\{24,2,2\}</math>, totally <math>\frac{3!}{2!}\cdot 2+4\cdot 3!=30</math> cases.<br />
<br />
Case 4: <math>n=4</math>, we have <math>\{f_1,f_2,f_3,f_4\}=\{3,2^2,2^2,2\},\{3,2^3,2,2\},\{6,2^2,2,2\},\{12,2,2,2\}</math>, totally <math>\frac{4!}{2!}\cdot 3+\frac{4!}{3!}=40</math> cases.<br />
<br />
Case 5: <math>n=5</math>, we have <math>\{f_1,f_2,f_3,f_4,f_5\}=\{3,2^2,2,2,2\},\{6,2,2,2,2\}</math>, totally <math>\frac{5!}{3!}+\frac{5!}{4!}=25</math> cases.<br />
<br />
Case 6: <math>n=6</math>, we have <math>\{f_1,f_2,f_3,f_4,f_5,f_6\}=\{3,2,2,2,2,2\}</math>, totally <math>\frac{6!}{5!}=6</math> cases.<br />
<br />
Thus, add all of them together, we have <math>1+10+30+40+25+6=112</math> cases. Put <math>\boxed{A}</math>.<br />
<br />
~FANYUCHEN20020715<br />
<br />
==See Also==<br />
<br />
<br />
{{AMC12 box|year=2020|ab=B|num-b=23|num-a=25}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1163302020 AMC 10A Problems/Problem 252020-02-01T20:35:21Z<p>Rejas: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution 1==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>, where <math>s \leq 7</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. The probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
if we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>. If we reroll two dice, we will roll <math>B</math> and <math>C</math>, and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than <math>7</math>. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have <math>1</math> dot and find the number of ways to distribute the remaining <math>4</math> dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==Another way to finish==<br />
As the denominator is very obviously <math>6^3=216</math>, we consider the numerator. When <math>a=1</math>, there are 3 choices for whether it is rolled 1st, 2nd, or 3rd, and in this case the other two rolls have to be at least 6. This give <math>3 \cdot 1^{2} =3</math> ways.<br />
Similarly, <math>a=2</math> gives <math>3 \cdot 2^{2} =12</math> because the 2 can be rolled in 3 places and the other two rolls are at least 5.<br />
<math>a=3</math> gives <math>3 \cdot 3^{2} =27</math>. <br />
Summing together gives the numerator of 42.<br />
<br />
== Video Solution ==<br />
<br />
https://youtu.be/7_mdreGBPvg - <math>Phineas1500</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1163292020 AMC 10A Problems/Problem 252020-02-01T20:34:04Z<p>Rejas: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution 1==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>, where <math>s \leq 7</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. The probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
if we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>. If we reroll two dice, we will roll <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than <math>7</math>. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have <math>1</math> dot and find the number of ways to distribute the remaining <math>4</math> dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==Another way to finish==<br />
As the denominator is very obviously <math>6^3=216</math>, we consider the numerator. When <math>a=1</math>, there are 3 choices for whether it is rolled 1st, 2nd, or 3rd, and in this case the other two rolls have to be at least 6. This give <math>3 \cdot 1^{2} =3</math> ways.<br />
Similarly, <math>a=2</math> gives <math>3 \cdot 2^{2} =12</math> because the 2 can be rolled in 3 places and the other two rolls are at least 5.<br />
<math>a=3</math> gives <math>3 \cdot 3^{2} =27</math>. <br />
Summing together gives the numerator of 42.<br />
<br />
== Video Solution ==<br />
<br />
https://youtu.be/7_mdreGBPvg - <math>Phineas1500</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1163282020 AMC 10A Problems/Problem 252020-02-01T20:33:35Z<p>Rejas: /* Solution 1 */</p>
<hr />
<div>==Problem==<br />
Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution 1==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>, where <math>s \leq 7</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
if we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>. If we reroll two dice, we will roll <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than <math>7</math>. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have <math>1</math> dot and find the number of ways to distribute the remaining <math>4</math> dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==Another way to finish==<br />
As the denominator is very obviously <math>6^3=216</math>, we consider the numerator. When <math>a=1</math>, there are 3 choices for whether it is rolled 1st, 2nd, or 3rd, and in this case the other two rolls have to be at least 6. This give <math>3 \cdot 1^{2} =3</math> ways.<br />
Similarly, <math>a=2</math> gives <math>3 \cdot 2^{2} =12</math> because the 2 can be rolled in 3 places and the other two rolls are at least 5.<br />
<math>a=3</math> gives <math>3 \cdot 3^{2} =27</math>. <br />
Summing together gives the numerator of 42.<br />
<br />
== Video Solution ==<br />
<br />
https://youtu.be/7_mdreGBPvg - <math>Phineas1500</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1161062020 AMC 10A Problems/Problem 252020-02-01T03:25:44Z<p>Rejas: /* Solution */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
if we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>. If we reroll two dice, we will roll <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than <math>7</math>. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have <math>1</math> dot and find the number of ways to distribute the remaining <math>4</math> dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1161052020 AMC 10A Problems/Problem 252020-02-01T03:25:07Z<p>Rejas: /* Solution */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
if we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>. If we reroll two dice, we will roll <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than <math>7</math>. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have 1 dot and find the number of ways to distribute the remaining 4 dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1161042020 AMC 10A Problems/Problem 252020-02-01T03:24:44Z<p>Rejas: /* Solution */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
if we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>. If we reroll two dice, we will roll both <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than <math>7</math>. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have 1 dot and find the number of ways to distribute the remaining 4 dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1161002020 AMC 10A Problems/Problem 252020-02-01T03:22:30Z<p>Rejas: /* Solution */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
If we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>.<br />
If we reroll two dice, we will roll both <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than <math>7</math>. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have 1 dot and find the number of ways to distribute the remaining 4 dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1160982020 AMC 10A Problems/Problem 252020-02-01T03:21:50Z<p>Rejas: /* Solution */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
If we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice <math>7</math>. This happens with probability <math>\frac16</math>.<br />
If we reroll two dice, we will roll both <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than 7. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have 1 dot and find the number of ways to distribute the remaining 4 dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1160942020 AMC 10A Problems/Problem 252020-02-01T03:20:57Z<p>Rejas: /* Solution */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice, which we will call <math>A</math>, <math>B</math>, and <math>C</math> respectively. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
If we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice 7. This happens with probability <math>\frac16</math>.<br />
If we reroll two dice, we will roll both <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than 7. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have 1 dot and find the number of ways to distribute the remaining 4 dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1160792020 AMC 10A Problems/Problem 252020-02-01T03:17:41Z<p>Rejas: /* Solution */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice <math>A</math>, <math>B</math>, and <math>C</math>. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
If we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice 7. This happens with probability <math>\frac16</math>.<br />
If we reroll two dice, we will roll both <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than 7. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have 1 dot and find the number of ways to distribute the remaining 4 dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
Thus, rerolling two dice is optimal if and only if <math>a \leq 3</math> and <math>a + b \geq 7</math>. The possible triplets <math>(a, b, c)</math> that satisfy these conditions, and the number of ways they can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> ways in which rerolling two dice is optimal, out of <math>6^3 = 216</math> possibilities, Therefore, the probability that Jason will reroll two dice is <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_25&diff=1160452020 AMC 10A Problems/Problem 252020-02-01T03:08:41Z<p>Rejas: /* See Also */</p>
<hr />
<div>Jason rolls three fair standard six-sided dice. Then he looks at the rolls and chooses a subset of the dice (possibly empty, possibly all three dice) to reroll. After rerolling, he wins if and only if the sum of the numbers face up on the three dice is exactly <math>7.</math> Jason always plays to optimize his chances of winning. What is the probability that he chooses to reroll exactly two of the dice?<br />
<br />
==Solution==<br />
Consider the probability that rolling two dice gives a sum of <math>s</math>. There are <math>s - 1</math> pairs that satisfy this, namely <math>(1, s - 1), (2, s - 2), ..., (s - 1, 1)</math>, out of <math>6^2 = 36</math> possible pairs. Thus, the probability is <math>\frac{s - 1}{36}</math>.<br />
<br />
Therefore, if one dice has a value of <math>a</math> and Jason rerolls the other two dice, then the probability of winning is <math>\frac{7 - a - 1}{36} = \frac{6 - a}{36}</math>.<br />
<br />
In order to maximize the probability of winning, <math>a</math> must be minimized. This means that if Jason rerolls two dice, he must choose the two dice with the maximum values.<br />
<br />
Thus, we can let <math>a \leq b \leq c</math> be the values of the three dice <math>A</math>, <math>B</math>, and <math>C</math>. Consider the case when <math>a + b < 7</math>. If <math>a + b + c = 7</math>, then we do not need to reroll any dice. Otherwise,<br />
If we reroll one dice, we can roll dice <math>C</math> in the hope that we get the value that makes the sum of the three dice 7. This happens with probability <math>\frac16</math>.<br />
If we reroll two dice, we will roll both <math>B</math> and <math>C</math> and the probability of winning is <math>\frac{6 - a}{36}</math>, as stated above.<br />
<br />
However, <math>\frac16 > \frac{6 - a}{36}</math>, so rolling one dice is always better than rolling two dice if <math>a + b < 7</math>.<br />
<br />
Now consider the case where <math>a + b \geq 7</math>. Rerolling one dice will not help us win since the sum of the three dice will always be greater than 7. If we reroll two dice, the probability of winning is, once again, <math>\frac{6 - a}{36}</math>. To find the probability of winning if we reroll all three dice, we can let each dice have 1 dot and find the number of ways to distribute the remaining 4 dots. By Stars and Bars, there are <math>{6\choose2} = 15</math> ways to do this, making the probability of winning <math>\frac{15}{6^3} = \frac5{72}</math>.<br />
<br />
In order for rolling two dice to be more favorable than rolling three dice, <math>\frac{6 - a}{36} > \frac5{72} \rightarrow a \leq 3</math>.<br />
<br />
The possible triplets <math>(a, b, c)</math> that satisfy <math>a \leq 3</math> and <math>a + b \geq 7</math>, and the number of ways each one can be permuted, are<br />
<math>(3, 4, 4) \rightarrow 3</math> ways.<br />
<math>(3, 4, 5) \rightarrow 6</math> ways.<br />
<math>(3, 4, 6) \rightarrow 6</math> ways.<br />
<math>(3, 5, 5) \rightarrow 3</math> ways.<br />
<math>(3, 5, 6) \rightarrow 6</math> ways.<br />
<math>(3, 6, 6) \rightarrow 3</math> ways.<br />
<math>(2, 5, 5) \rightarrow 3</math> ways.<br />
<math>(2, 5, 6) \rightarrow 6</math> ways.<br />
<math>(2, 6, 6) \rightarrow 3</math> ways.<br />
<math>(1, 6, 6) \rightarrow 3</math> ways.<br />
<br />
There are <math>3 + 6 + 6 + 3 + 6 + 3 + 3 + 6 + 3 + 3 = 42</math> favorable permuations out of <math>6^3 = 216</math> possibilities, making the overall probability <math>\frac{42}{216} = \boxed{\textbf{(A) }\frac7{36}}</math><br />
<br />
==See Also==<br />
{{AMC10 box|year=2020|ab=A|num-b=24|after=Last Problem}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_22&diff=1160302020 AMC 10A Problems/Problem 222020-02-01T03:02:24Z<p>Rejas: /* Solution */</p>
<hr />
<div>For how many positive integers <math>n \le 1000</math> is<cmath>\left\lfloor \dfrac{998}{n} \right\rfloor+\left\lfloor \dfrac{999}{n} \right\rfloor+\left\lfloor \dfrac{1000}{n}\right \rfloor</cmath>not divisible by <math>3</math>? (Recall that <math>\lfloor x \rfloor</math> is the greatest integer less than or equal to <math>x</math>.)<br />
<br />
<math>\textbf{(A) } 22 \qquad\textbf{(B) } 23 \qquad\textbf{(C) } 24 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 26</math><br />
<br />
== Solution ==<br />
Let <math>a = \lfloor \frac{998}n \rfloor</math>. If the expression is not divisible by <math>3</math>, then the three terms in the expression must be <math>(a, a + 1, a + 1)</math>, which would imply that <math>n</math> is divisible by <math>999</math> but not <math>1000</math>, or <math>(a, a, a + 1)</math>, which would imply that <math>n</math> is divisible by <math>1000</math> but not <math>999</math>. <math>999 = 3^3 \cdot 37</math> has <math>4 \cdot 2 = 8</math> factors, and <math>1000 = 2^3 \cdot 5^3</math> has <math>4 \cdot 4 = 16</math> factors. However, <math>n = 1</math> does not work because <math>1</math> is divisible by both <math>999</math> and <math>1000</math>, and since <math>1</math> is counted twice, the answer is <math>16 + 8 - 2 = \boxed{\textbf{(A) }22}</math>.<br />
<br />
==See Also==<br />
<br />
{{AMC10 box|year=2020|ab=A|num-b=21|num-a=23}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12B_Problems/Problem_24&diff=1151642009 AMC 12B Problems/Problem 242020-01-23T01:51:42Z<p>Rejas: /* Solution */</p>
<hr />
<div>== Problem ==<br />
For how many values of <math>x</math> in <math>[0,\pi]</math> is <math>\sin^{ - 1}(\sin 6x) = \cos^{ - 1}(\cos x)</math>?<br />
Note: The functions <math>\sin^{ - 1} = \arcsin</math> and <math>\cos^{ - 1} = \arccos</math> denote inverse trigonometric functions.<br />
<br />
<math>\textbf{(A)}\ 3\qquad \textbf{(B)}\ 4\qquad \textbf{(C)}\ 5\qquad \textbf{(D)}\ 6\qquad \textbf{(E)}\ 7</math><br />
<br />
== Solution ==<br />
<br />
First of all, we have to agree on the range of <math>\sin^{-1}</math> and <math>\cos^{-1}</math>. This should have been a part of the problem statement -- but as it is missing, we will assume the most common definition: <math>\forall x: -\pi/2 \leq \sin^{-1}(x) \leq \pi/2</math> and <math>\forall x: 0\leq \cos^{-1}(x) \leq \pi</math>.<br />
<br />
Hence we get that <math>\forall x\in[0,\pi]: \cos^{ - 1}(\cos x) = x</math>, thus our equation simplifies to <math>\sin^{ - 1}(\sin 6x) = x</math>.<br />
<br />
Consider the function <math>f(x) = \sin^{ - 1}(\sin 6x) - x</math>. We are looking for roots of <math>f</math> on <math>[0,\pi]</math>.<br />
<br />
By analyzing properties of <math>\sin</math> and <math>\sin^{-1}</math> (or by computing the derivative of <math>f</math>) one can discover the following properties of <math>f</math>:<br />
<br />
* <math>f(0)=0</math>.<br />
* <math>f</math> is increasing and then decreasing on <math>[0,\pi/6]</math>.<br />
* <math>f</math> is decreasing and then increasing on <math>[\pi/6,2\pi/6]</math>.<br />
* <math>f</math> is increasing and then decreasing on <math>[2\pi/6,3\pi/6]</math>.<br />
<br />
For <math>x=\pi/6</math> we have <math>f(x) = \sin^{-1} (\sin \pi) - \pi/6 = -\pi/6 < 0</math>. Hence <math>f</math> has exactly one root on <math>(0,\pi/6)</math>.<br />
<br />
For <math>x=2\pi/6</math> we have <math>f(x) = \sin^{-1} (\sin 2\pi) - 2\pi/6 = -2\pi/6 < 0</math>. Hence <math>f</math> is negative on the entire interval <math>[\pi/6,2\pi/6]</math>.<br />
<br />
Now note that <math>\forall t: \sin^{-1}(t) \leq \pi/2</math>. Hence for <math>x > 3\pi/6</math> we have <math>f(x) < 0</math>, and we can easily check that <math>f(3\pi/6)<0</math> as well.<br />
<br />
Thus the only unknown part of <math>f</math> is the interval <math>(2\pi/6,3\pi/6)</math>. On this interval, <math>f</math> is negative in both endpoints, and we know that it is first increasing and then decreasing. Hence there can be zero, one, or two roots on this interval.<br />
<br />
To prove that there are two roots, it is enough to find any <math>x</math> from this interval such that <math>f(x)>0</math>.<br />
<br />
A good guess is its midpoint, <math>x=5\pi/12</math>, where the function <math>\sin^{-1}(\sin 6x)</math> has its local maximum. We can evaluate:<br />
<math>f(x) = \sin^{-1}(\sin 5\pi/2) - 5\pi/12 = \pi/2 - 5\pi/12 = \pi/12 > 0</math>.<br />
<br />
Summary: The function <math>f</math> has <math>\boxed{\textbf{(B) }4}</math> roots on <math>[0,\pi]</math>: the first one is <math>0</math>, the second one is in <math>(0,\pi/6)</math>, and the last two are in <math>(2\pi/6,3\pi/6)</math>.<br />
<br />
Actual solutions are <math>x=0</math>, <math>x=\pi/7</math>, <math>x=2\pi/5</math>, and <math>x=3\pi/7</math>.<br />
<br />
==Solution 2==<br />
Since <math>0\leq \cos^{-1}(a) \leq \pi</math> for all <math>a</math>, the equation reduces to <math>\sin^{-1}(\sin(6x)) = x</math>. Since <math>-\pi/2 \leq \sin^{-1}(a) \leq \pi/2</math> for all <math>a</math>, <math>0 \leq x \leq \pi/2</math>. To make the problem easier, we will measure angles in degrees. We will consider each sixth of the interval <math>[0, 90]</math>.<br />
<br />
For <math>0 \leq x \leq 15</math>, <math>6x</math> is in the first quadrant. Thus, <math>\sin^{-1}(\sin(6x)) = 6x</math>. Setting this equal to <math>x</math> yields the solution <math>x = 0</math>.<br />
<br />
For <math>15 \leq x \leq 30</math>, <math>6x</math> is in the second quadrant. Thus, <math>\sin^{-1}(\sin(6x)) = 180 - 6x</math>. This yields the solution <math>x = \frac{180}7</math>.<br />
<br />
For <math>30 \leq x \leq 45</math>, <math>6x</math> is in the third quadrant. Thus, <math>\sin^{-1}(\sin(6x)) = 180 - 6x</math>. As <math>\frac{180}{7}</math> is not on the interval <math>30 \leq x \leq 45</math>, this yields no solution.<br />
<br />
For <math>45 \leq x \leq 60</math>, <math>6x</math> is in the fourth quadrant. Thus, <math>\sin^{-1}(\sin(6x)) = 6x - 360</math>. As <math>72</math> is not on the interval <math>45 \leq x \leq 60</math>, this yields no solution.<br />
<br />
For <math>60 \leq x \leq 75</math>, <math>6x</math> is in the first quadrant plus a full revolution. Thus, <math>\sin^{-1}(\sin(6x)) = 6x - 360</math>. This yields the solution <math>x = 72</math>.<br />
<br />
For <math>75 \leq x \leq 90</math>, <math>6x</math> is in the second quadrant plus a full revolution. Thus <math>\sin^{-1}(\sin(6x)) = 540 - 6x</math>. This yields the solution <math>x = \frac{540}7</math>.<br />
<br />
There are <math>\boxed{\textbf{(B) }4}</math> solutions, <math>x=0</math>, <math>x=\pi/7</math>, <math>x=2\pi/5</math>, and <math>x=3\pi/7</math>.<br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2009|ab=B|num-b=23|num-a=25}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2003_AMC_12A_Problems/Problem_18&diff=1089022003 AMC 12A Problems/Problem 182019-08-15T22:03:26Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>== Problem ==<br />
Let <math>n</math> be a <math>5</math>-digit number, and let <math>q</math> and <math>r</math> be the quotient and the remainder, respectively, when <math>n</math> is divided by <math>100</math>. For how many values of <math>n</math> is <math>q+r</math> divisible by <math>11</math>? <br />
<br />
<math> \mathrm{(A) \ } 8180\qquad \mathrm{(B) \ } 8181\qquad \mathrm{(C) \ } 8182\qquad \mathrm{(D) \ } 9000\qquad \mathrm{(E) \ } 9090 </math><br />
<br />
== Solution 1 ==<br />
<br />
When a <math>5</math>-digit number is divided by <math>100</math>, the first <math>3</math> digits become the quotient, <math>q</math>, and the last <math>2</math> digits become the remainder, <math>r</math>. <br />
<br />
Therefore, <math>q</math> can be any integer from <math>100</math> to <math>999</math> inclusive, and <math>r</math> can be any integer from <math>0</math> to <math>99</math> inclusive. <br />
<br />
For each of the <math>9\cdot10\cdot10=900</math> possible values of <math>q</math>, there are at least <math>\left\lfloor \frac{100}{11} \right\rfloor = 9</math> possible values of <math>r</math> such that <math>q+r \equiv 0\pmod{11}</math>. <br />
<br />
Since there is <math>1</math> "extra" possible value of <math>r</math> that is congruent to <math>0\pmod{11}</math>, each of the <math>\left\lfloor \frac{900}{11} \right\rfloor = 81</math> values of <math>q</math> that are congruent to <math>0\pmod{11}</math> have <math>1</math> more possible value of <math>r</math> such that <math>q+r \equiv 0\pmod{11}</math>. <br />
<br />
Therefore, the number of possible values of <math>n</math> such that <math>q+r \equiv 0\pmod{11}</math> is <math>900\cdot9+81\cdot1=8181 \Rightarrow\boxed{(B)} </math>.<br />
<br />
== Solution 2 ==<br />
<br />
Notice that <math>q+r\equiv0\pmod{11}\Rightarrow100q+r\equiv0\pmod{11}</math>. This means that any number whose quotient and remainder sum is divisible by 11 must also be divisible by 11. Therefore, there are <math>\frac{99990-10010}{11}+1=8181</math> possible values. The answer is <math>\boxed{\textbf{(B) }8181}</math>.<br />
<br />
== Solution 3 ==<br />
Let <math>abcde</math> be the five digits of <math>n</math>. Then <math>q = abc</math> and <math>r = de</math>. By the divisibility rules of <math>11</math>, <math>q = a + b + c \pmod{11}</math> and <math>r = -d + e \pmod{11}</math>, so <math>q + r = a - b + c - d + e = abcde = n \pmod{11}</math>. Thus, <math>n</math> must be divisble by <math>11</math>. There are <math>\frac{99990 - 10010}{11} + 1 = 8181</math> five-digit multiples of <math>11</math>, so the answer is <math>\boxed{\textbf{(B) }8181}</math>.<br />
<br />
==See Also==<br />
{{AMC10 box|year=2003|ab=A|num-b=24|after=Last Question}}<br />
{{AMC12 box|year=2003|ab=A|num-b=17|num-a=19}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2001_AMC_12_Problems/Problem_9&diff=1083372001 AMC 12 Problems/Problem 92019-08-06T22:29:55Z<p>Rejas: /* Solution */</p>
<hr />
<div>== Problem ==<br />
<!-- don't remove the following tag, for PoTW on the Wiki front page--><onlyinclude>Let <math>f</math> be a function satisfying <math>f(xy) = \frac{f(x)}y</math> for all positive real numbers <math>x</math> and <math>y</math>. If <math>f(500) =3</math>, what is the value of <math>f(600)</math>?<!-- don't remove the following tag, for PoTW on the Wiki front page--></onlyinclude><br />
<br />
<math>(\mathrm{A})\ 1 \qquad (\mathrm{B})\ 2 \qquad (\mathrm{C})\ \frac52 \qquad (\mathrm{D})\ 3 \qquad (\mathrm{E})\ \frac{18}5</math><br />
<br />
== Solution 1 ==<br />
Letting <math>x = 500</math> and <math>y = \dfrac65</math> in the given equation, we get <math>f(500\cdot\frac65) = \frac3{\frac65} = \frac52</math>, or <math>f(600) = \boxed{\textbf{C } \frac52}</math>.<br />
<br />
== Solution 2 ==<br />
The only function that satisfies the given condition is <math>y = \frac{k}{x}</math>, for some constant <math>k</math>. Thus, the answer is <math>\frac{500 \cdot 3}{600} = \frac52</math>.<br />
<br />
== See Also ==<br />
<br />
{{AMC12 box|year=2001|num-b=8|num-a=10}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12A_Problems/Problem_10&diff=1081402010 AMC 12A Problems/Problem 102019-08-01T21:12:47Z<p>Rejas: /* Solution */</p>
<hr />
<div>== Problem ==<br />
The first four terms of an arithmetic sequence are <math>p</math>, <math>9</math>, <math>3p-q</math>, and <math>3p+q</math>. What is the <math>2010^\text{th}</math> term of this sequence?<br />
<br />
<math>\textbf{(A)}\ 8041 \qquad \textbf{(B)}\ 8043 \qquad \textbf{(C)}\ 8045 \qquad \textbf{(D)}\ 8047 \qquad \textbf{(E)}\ 8049</math><br />
<br />
== Solution 1 ==<br />
<math>3p-q</math> and <math>3p+q</math> are consecutive terms, so the common difference is <math>(3p+q)-(3p-q) = 2q</math>.<br />
<br />
<cmath>\begin{align*}p+2q &= 9\\<br />
9+2q &= 3p-q\\<br />
q&=2\\<br />
p&=5\end{align*}</cmath><br />
<br />
The common difference is <math>4</math>. The first term is <math>5</math> and the <math>2010^\text{th}</math> term is<br />
<br />
<cmath>5+4(2009) = \boxed{\textbf{(A) }8041}</cmath><br />
<br />
== Solution 2 ==<br />
Since all the answer choices are around <math>2010 \cdot 4 = 8040</math>, the common difference must be <math>4</math>. The first term is therefore <math>9 - 4 = 5</math>, so the <math>2010^\text{th}</math> term is <math>5 + 4 \cdot 2009 = \boxed{\textbf{(A) }8041}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2010|num-b=9|num-a=11|ab=A}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_25&diff=1080612000 AMC 12 Problems/Problem 252019-07-31T00:07:04Z<p>Rejas: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
Eight congruent [[equilateral triangle]]s, each of a different color, are used to construct a regular [[octahedron]]. How many distinguishable ways are there to construct the octahedron? (Two colored octahedrons are distinguishable if neither can be rotated to look just like the other.) <br />
<br />
<math>\text {(A)}\ 210 \qquad \text {(B)}\ 560 \qquad \text {(C)}\ 840 \qquad \text {(D)}\ 1260 \qquad \text {(E)}\ 1680</math><br />
<br />
<center><asy><br />
import three;<br />
import math;<br />
unitsize(1.5cm);<br />
currentprojection=orthographic(2,0.2,1);<br />
<br />
triple A=(0,0,1);<br />
triple B=(sqrt(2)/2,sqrt(2)/2,0);<br />
triple C=(sqrt(2)/2,-sqrt(2)/2,0);<br />
triple D=(-sqrt(2)/2,-sqrt(2)/2,0);<br />
triple E=(-sqrt(2)/2,sqrt(2)/2,0);<br />
triple F=(0,0,-1);<br />
draw(A--B--E--cycle);<br />
draw(A--C--D--cycle);<br />
draw(F--C--B--cycle);<br />
draw(F--D--E--cycle,dotted+linewidth(0.7));<br />
</asy></center><br />
<br />
== Solution 1 ==<br />
Since the octahedron is indistinguishable by rotations, without loss of generality fix a face to be red.<br />
<center><asy><br />
size(8cm);<br />
defaultpen(0.5);<br />
import three;<br />
import math;<br />
currentprojection=orthographic(2,0.2,1);<br />
triple A=(0,0,1);<br />
triple B=(sqrt(2)/2,sqrt(2)/2,0);<br />
triple C=(sqrt(2)/2,-sqrt(2)/2,0);<br />
triple D=(-sqrt(2)/2,-sqrt(2)/2,0);<br />
triple E=(-sqrt(2)/2,sqrt(2)/2,0);<br />
triple F=(0,0,-1);<br />
draw(A--B--E--cycle);<br />
draw(A--C--D--cycle);<br />
draw(F--C--B--cycle);<br />
draw(F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(surface(A--B--C--cycle),rgb(1,.6,.6),nolight);</asy></center><br />
There are <math>7!</math> ways to arrange the remaining seven colors, but there still are three possible rotations about the fixed face, so the answer is <math>7!/3 = 1680</math>.<br />
<center><asy><br />
size(8cm);<br />
defaultpen(0.5);<br />
import three;<br />
import math;<br />
currentprojection=orthographic(2,0,1);<br />
triple A=(0,0,1);<br />
triple B=(sqrt(2)/2,sqrt(2)/2,0);<br />
triple C=(sqrt(2)/2,-sqrt(2)/2,0);<br />
triple D=(-sqrt(2)/2,-sqrt(2)/2,0);<br />
triple E=(-sqrt(2)/2,sqrt(2)/2,0);<br />
triple F=(0,0,-1);<br />
triple right=(0,1,0);<br />
picture p = new picture, r = new picture, s = new picture;<br />
draw(p,A--B--E--cycle);<br />
draw(p,A--C--D--cycle);<br />
draw(p,F--C--B--cycle);<br />
draw(p,F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(p,surface(A--B--C--cycle),rgb(1,.6,.6),nolight);<br />
draw(p,surface(A--B--E--cycle),rgb(1,1,.6),nolight);<br />
add(scale3(2.2)*p);<br />
draw(r,A--B--E--cycle);<br />
draw(r,A--C--D--cycle);<br />
draw(r,F--C--B--cycle);<br />
draw(r,F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(r,surface(A--B--C--cycle),rgb(1,.6,.6),nolight);<br />
draw(r,surface(A--C--D--cycle),rgb(1,1,.6),nolight);<br />
add(scale3(2.2)*shift(2*right)*r);<br />
draw(s,A--B--E--cycle);<br />
draw(s,A--C--D--cycle);<br />
draw(s,F--C--B--cycle);<br />
draw(s,F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(s,surface(A--B--C--cycle),rgb(1,.6,.6),nolight);<br />
draw(s,surface(B--C--F--cycle),rgb(1,1,.6),nolight);<br />
add(scale3(2.2)*shift(4*right)*s);<br />
</asy></center><br />
<br />
== Solution 2 ==<br />
We consider the dual of the octahedron, the [[cube (geometry)|cube]]; a cube can be inscribed in an octahedron with each of its [[vertex|vertices]] at a face of the octahedron. So the problem is equivalent to finding the number of ways to color the vertices of a cube.<br />
<br />
Select any vertex and call it <math>A</math>; there are <math>8</math> color choices for this vertex, but this vertex can be rotated to any of <math>8</math> locations. After fixing <math>A</math>, we pick another vertex <math>B</math> adjacent to <math>A</math>. There are seven color choices for <math>B</math>, but there are only three locations to which <math>B</math> can be rotated to (since there are three edges from <math>A</math>). The remaining six vertices can be colored in any way and their locations are now fixed. Thus the total number of ways is <math>\frac{8}{8} \cdot \frac{7}{3} \cdot 6! = 1680 \Rightarrow \mathrm{(E)}</math>.<br />
<br />
== Solution 3 ==<br />
There are 8! ways to place eight colors on a fixed octahedron. An octahedron has six vertices, of which one can face the top, and for any vertex that faces the top, there are four different triangles around that vertex that can be facing you. Thus there are 6*4 = 24 ways to orient an octahedron, and <math>8!/24 = 1680 \Rightarrow \mathrm{(E)}</math><br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=24|after=Last question}}<br />
<br />
[[Category:Intermediate Combinatorics Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_25&diff=1080602000 AMC 12 Problems/Problem 252019-07-31T00:06:45Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>== Problem ==<br />
Eight congruent [[equilateral triangle]]s, each of a different color, are used to construct a regular [[octahedron]]. How many distinguishable ways are there to construct the octahedron? (Two colored octahedrons are distinguishable if neither can be rotated to look just like the other.) <br />
<br />
<math>\text {(A)}\ 210 \qquad \text {(B)}\ 560 \qquad \text {(C)}\ 840 \qquad \text {(D)}\ 1260 \qquad \text {(E)}\ 1680</math><br />
<br />
<center><asy><br />
import three;<br />
import math;<br />
unitsize(1.5cm);<br />
currentprojection=orthographic(2,0.2,1);<br />
<br />
triple A=(0,0,1);<br />
triple B=(sqrt(2)/2,sqrt(2)/2,0);<br />
triple C=(sqrt(2)/2,-sqrt(2)/2,0);<br />
triple D=(-sqrt(2)/2,-sqrt(2)/2,0);<br />
triple E=(-sqrt(2)/2,sqrt(2)/2,0);<br />
triple F=(0,0,-1);<br />
draw(A--B--E--cycle);<br />
draw(A--C--D--cycle);<br />
draw(F--C--B--cycle);<br />
draw(F--D--E--cycle,dotted+linewidth(0.7));<br />
</asy></center><br />
<br />
== Solution 1 ==<br />
We consider the dual of the octahedron, the [[cube (geometry)|cube]]; a cube can be inscribed in an octahedron with each of its [[vertex|vertices]] at a face of the octahedron. So the problem is equivalent to finding the number of ways to color the vertices of a cube.<br />
<br />
Select any vertex and call it <math>A</math>; there are <math>8</math> color choices for this vertex, but this vertex can be rotated to any of <math>8</math> locations. After fixing <math>A</math>, we pick another vertex <math>B</math> adjacent to <math>A</math>. There are seven color choices for <math>B</math>, but there are only three locations to which <math>B</math> can be rotated to (since there are three edges from <math>A</math>). The remaining six vertices can be colored in any way and their locations are now fixed. Thus the total number of ways is <math>\frac{8}{8} \cdot \frac{7}{3} \cdot 6! = 1680 \Rightarrow \mathrm{(E)}</math>.<br />
<br />
== Solution 1 ==<br />
Since the octahedron is indistinguishable by rotations, without loss of generality fix a face to be red.<br />
<center><asy><br />
size(8cm);<br />
defaultpen(0.5);<br />
import three;<br />
import math;<br />
currentprojection=orthographic(2,0.2,1);<br />
triple A=(0,0,1);<br />
triple B=(sqrt(2)/2,sqrt(2)/2,0);<br />
triple C=(sqrt(2)/2,-sqrt(2)/2,0);<br />
triple D=(-sqrt(2)/2,-sqrt(2)/2,0);<br />
triple E=(-sqrt(2)/2,sqrt(2)/2,0);<br />
triple F=(0,0,-1);<br />
draw(A--B--E--cycle);<br />
draw(A--C--D--cycle);<br />
draw(F--C--B--cycle);<br />
draw(F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(surface(A--B--C--cycle),rgb(1,.6,.6),nolight);</asy></center><br />
There are <math>7!</math> ways to arrange the remaining seven colors, but there still are three possible rotations about the fixed face, so the answer is <math>7!/3 = 1680</math>.<br />
<center><asy><br />
size(8cm);<br />
defaultpen(0.5);<br />
import three;<br />
import math;<br />
currentprojection=orthographic(2,0,1);<br />
triple A=(0,0,1);<br />
triple B=(sqrt(2)/2,sqrt(2)/2,0);<br />
triple C=(sqrt(2)/2,-sqrt(2)/2,0);<br />
triple D=(-sqrt(2)/2,-sqrt(2)/2,0);<br />
triple E=(-sqrt(2)/2,sqrt(2)/2,0);<br />
triple F=(0,0,-1);<br />
triple right=(0,1,0);<br />
picture p = new picture, r = new picture, s = new picture;<br />
draw(p,A--B--E--cycle);<br />
draw(p,A--C--D--cycle);<br />
draw(p,F--C--B--cycle);<br />
draw(p,F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(p,surface(A--B--C--cycle),rgb(1,.6,.6),nolight);<br />
draw(p,surface(A--B--E--cycle),rgb(1,1,.6),nolight);<br />
add(scale3(2.2)*p);<br />
draw(r,A--B--E--cycle);<br />
draw(r,A--C--D--cycle);<br />
draw(r,F--C--B--cycle);<br />
draw(r,F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(r,surface(A--B--C--cycle),rgb(1,.6,.6),nolight);<br />
draw(r,surface(A--C--D--cycle),rgb(1,1,.6),nolight);<br />
add(scale3(2.2)*shift(2*right)*r);<br />
draw(s,A--B--E--cycle);<br />
draw(s,A--C--D--cycle);<br />
draw(s,F--C--B--cycle);<br />
draw(s,F--D--E--cycle,dotted+linewidth(0.7));<br />
draw(s,surface(A--B--C--cycle),rgb(1,.6,.6),nolight);<br />
draw(s,surface(B--C--F--cycle),rgb(1,1,.6),nolight);<br />
add(scale3(2.2)*shift(4*right)*s);<br />
</asy></center><br />
<br />
== Solution 2 ==<br />
We consider the dual of the octahedron, the [[cube (geometry)|cube]]; a cube can be inscribed in an octahedron with each of its [[vertex|vertices]] at a face of the octahedron. So the problem is equivalent to finding the number of ways to color the vertices of a cube.<br />
<br />
Select any vertex and call it <math>A</math>; there are <math>8</math> color choices for this vertex, but this vertex can be rotated to any of <math>8</math> locations. After fixing <math>A</math>, we pick another vertex <math>B</math> adjacent to <math>A</math>. There are seven color choices for <math>B</math>, but there are only three locations to which <math>B</math> can be rotated to (since there are three edges from <math>A</math>). The remaining six vertices can be colored in any way and their locations are now fixed. Thus the total number of ways is <math>\frac{8}{8} \cdot \frac{7}{3} \cdot 6! = 1680 \Rightarrow \mathrm{(E)}</math>.<br />
<br />
== Solution 3 ==<br />
There are 8! ways to place eight colors on a fixed octahedron. An octahedron has six vertices, of which one can face the top, and for any vertex that faces the top, there are four different triangles around that vertex that can be facing you. Thus there are 6*4 = 24 ways to orient an octahedron, and <math>8!/24 = 1680 \Rightarrow \mathrm{(E)}</math><br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=24|after=Last question}}<br />
<br />
[[Category:Intermediate Combinatorics Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_15&diff=1080582000 AMC 12 Problems/Problem 152019-07-30T21:55:24Z<p>Rejas: /* Solution 3 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #15]] and [[2000 AMC 10 Problems|2000 AMC 10 #24]]}}<br />
<br />
== Problem ==<br />
Let <math>f</math> be a [[function]] for which <math>f(x/3) = x^2 + x + 1</math>. Find the sum of all values of <math>z</math> for which <math>f(3z) = 7</math>.<br />
<br />
<math>\text {(A)}\ -1/3 \qquad \text {(B)}\ -1/9 \qquad \text {(C)}\ 0 \qquad \text {(D)}\ 5/9 \qquad \text {(E)}\ 5/3</math><br />
<br />
==Solution 1==<br />
Let <math>y = \frac{x}{3}</math>; then <math>f(y) = (3y)^2 + 3y + 1 = 9y^2 + 3y+1</math>. Thus <math>f(3z)-7=81z^2+9z-6=3(9z-2)(3z+1)=0</math>, and <math>z = -\frac{1}{3}, \frac{2}{9}</math>. These sum up to <math>\boxed{\textbf{(B) }-\frac19}</math>. (We can also use [[Vieta's formulas]] to find the sum more quickly.)<br />
<br />
==Solution 2==<br />
Set <math>f(\frac{x}{3}) = x^2+x+1=7</math> to get <math>x^2+x-6=0.</math> From either finding the roots or using Vieta's formulas, we find the sum of these roots to be <math>-1.</math> Each root of this equation is <math>9</math> times greater than a corresponding root of <math>f(3z) = 7</math> (because <math>\frac{x}{3} = 3z</math> gives <math>x = 9z</math>), thus the sum of the roots in the equation <math>f(3z)=7</math> is <math>-\frac{1}{9}</math> or <math>\boxed{\textbf{(B) }-\frac19}</math>.<br />
<br />
==Solution 3==<br />
Since we have <math>f(x/3)</math>, <math>f(3z)</math> occurs at <math>x=9z.</math> Thus, <math>f(9z/3) = f(3z) = (9z)^2 + 9z + 1</math>. We set this equal to 7:<br />
<br />
<math>81z^2 + 9z +1 = 7 \Longrightarrow 81z^2 + 9z - 6 = 0</math>. For any quadratic <math>ax^2 + bx +c = 0</math>, the sum of the roots is <math>-\frac{b}{a}</math>. Thus, the sum of the roots of this equation is <math>-\frac{9}{81} = \boxed{\textbf{(B) }-\frac19}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=14|num-a=16}}<br />
{{AMC10 box|year=2000|num-b=23|num-a=25}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_15&diff=1080572000 AMC 12 Problems/Problem 152019-07-30T21:55:07Z<p>Rejas: /* Solution 3 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #15]] and [[2000 AMC 10 Problems|2000 AMC 10 #24]]}}<br />
<br />
== Problem ==<br />
Let <math>f</math> be a [[function]] for which <math>f(x/3) = x^2 + x + 1</math>. Find the sum of all values of <math>z</math> for which <math>f(3z) = 7</math>.<br />
<br />
<math>\text {(A)}\ -1/3 \qquad \text {(B)}\ -1/9 \qquad \text {(C)}\ 0 \qquad \text {(D)}\ 5/9 \qquad \text {(E)}\ 5/3</math><br />
<br />
==Solution 1==<br />
Let <math>y = \frac{x}{3}</math>; then <math>f(y) = (3y)^2 + 3y + 1 = 9y^2 + 3y+1</math>. Thus <math>f(3z)-7=81z^2+9z-6=3(9z-2)(3z+1)=0</math>, and <math>z = -\frac{1}{3}, \frac{2}{9}</math>. These sum up to <math>\boxed{\textbf{(B) }-\frac19}</math>. (We can also use [[Vieta's formulas]] to find the sum more quickly.)<br />
<br />
==Solution 2==<br />
Set <math>f(\frac{x}{3}) = x^2+x+1=7</math> to get <math>x^2+x-6=0.</math> From either finding the roots or using Vieta's formulas, we find the sum of these roots to be <math>-1.</math> Each root of this equation is <math>9</math> times greater than a corresponding root of <math>f(3z) = 7</math> (because <math>\frac{x}{3} = 3z</math> gives <math>x = 9z</math>), thus the sum of the roots in the equation <math>f(3z)=7</math> is <math>-\frac{1}{9}</math> or <math>\boxed{\textbf{(B) }-\frac19}</math>.<br />
<br />
==Solution 3==<br />
Since we have <math>f(x/3)</math>, <math>f(3z)</math> occurs at <math>x=9z.</math> Thus, <math>f(9z/3) = f(3z) = (9z)^2 + 9z + 1</math>. We set this equal to 7:<br />
<br />
<math>81z^2 + 9z +1 = 7 \Longrightarrow 81z^2 + 9z - 6 = 0</math>. For any quadratic <math>ax^2 + bx +c = 0</math>, the sum of the roots is <math>-\frac{b}{a}</math>. Thus, the sum of the roots of this equation is <math>-\frac{9}{81} = \boxed{-\frac{1}{9}} \Longrightarrow \boxed{\textbf{(B) }-\frac19}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=14|num-a=16}}<br />
{{AMC10 box|year=2000|num-b=23|num-a=25}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_15&diff=1080562000 AMC 12 Problems/Problem 152019-07-30T21:54:41Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #15]] and [[2000 AMC 10 Problems|2000 AMC 10 #24]]}}<br />
<br />
== Problem ==<br />
Let <math>f</math> be a [[function]] for which <math>f(x/3) = x^2 + x + 1</math>. Find the sum of all values of <math>z</math> for which <math>f(3z) = 7</math>.<br />
<br />
<math>\text {(A)}\ -1/3 \qquad \text {(B)}\ -1/9 \qquad \text {(C)}\ 0 \qquad \text {(D)}\ 5/9 \qquad \text {(E)}\ 5/3</math><br />
<br />
==Solution 1==<br />
Let <math>y = \frac{x}{3}</math>; then <math>f(y) = (3y)^2 + 3y + 1 = 9y^2 + 3y+1</math>. Thus <math>f(3z)-7=81z^2+9z-6=3(9z-2)(3z+1)=0</math>, and <math>z = -\frac{1}{3}, \frac{2}{9}</math>. These sum up to <math>\boxed{\textbf{(B) }-\frac19}</math>. (We can also use [[Vieta's formulas]] to find the sum more quickly.)<br />
<br />
==Solution 2==<br />
Set <math>f(\frac{x}{3}) = x^2+x+1=7</math> to get <math>x^2+x-6=0.</math> From either finding the roots or using Vieta's formulas, we find the sum of these roots to be <math>-1.</math> Each root of this equation is <math>9</math> times greater than a corresponding root of <math>f(3z) = 7</math> (because <math>\frac{x}{3} = 3z</math> gives <math>x = 9z</math>), thus the sum of the roots in the equation <math>f(3z)=7</math> is <math>-\frac{1}{9}</math> or <math>\boxed{\textbf{(B) }-\frac19}</math>.<br />
<br />
==Solution 3==<br />
Since we have <math>f(x/3)</math>, <math>f(3z)</math> occurs at <math>x=9z.</math> Thus, <math>f(9z/3) = f(3z) = (9z)^2 + 9z + 1</math>. We set this equal to 7:<br />
<br />
<math>81z^2 + 9z +1 = 7 \Longrightarrow 81z^2 + 9z - 6 = 0</math>. For any quadratic <math>ax^2 + bx +c = 0</math>, the sum of the roots is <math>-\frac{b}{a}</math>. Thus, the sum of the roots of this equation is <math>-\frac{9}{81} = \boxed{-\frac{1}{9}} \Longrightarrow \boxed{\text{(B)}}</math><br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=14|num-a=16}}<br />
{{AMC10 box|year=2000|num-b=23|num-a=25}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_15&diff=1080552000 AMC 12 Problems/Problem 152019-07-30T21:54:22Z<p>Rejas: /* Solution 1 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #15]] and [[2000 AMC 10 Problems|2000 AMC 10 #24]]}}<br />
<br />
== Problem ==<br />
Let <math>f</math> be a [[function]] for which <math>f(x/3) = x^2 + x + 1</math>. Find the sum of all values of <math>z</math> for which <math>f(3z) = 7</math>.<br />
<br />
<math>\text {(A)}\ -1/3 \qquad \text {(B)}\ -1/9 \qquad \text {(C)}\ 0 \qquad \text {(D)}\ 5/9 \qquad \text {(E)}\ 5/3</math><br />
<br />
==Solution 1==<br />
Let <math>y = \frac{x}{3}</math>; then <math>f(y) = (3y)^2 + 3y + 1 = 9y^2 + 3y+1</math>. Thus <math>f(3z)-7=81z^2+9z-6=3(9z-2)(3z+1)=0</math>, and <math>z = -\frac{1}{3}, \frac{2}{9}</math>. These sum up to <math>\boxed{\textbf{(B) }-\frac19}</math>. (We can also use [[Vieta's formulas]] to find the sum more quickly.)<br />
<br />
==Solution 2==<br />
Set <math>f(\frac{x}{3}) = x^2+x+1=7</math> to get <math>x^2+x-6=0.</math> From either finding the roots or using Vieta's formulas, we find the sum of these roots to be <math>-1.</math> Each root of this equation is <math>9</math> times greater than a corresponding root of <math>f(3z) = 7</math> (because <math>\frac{x}{3} = 3z</math> gives <math>x = 9z</math>), thus the sum of the roots in the equation <math>f(3z)=7</math> is <math>-\frac{1}{9}</math> or <math>\boxed{\text{(B)}}</math><br />
<br />
==Solution 3==<br />
Since we have <math>f(x/3)</math>, <math>f(3z)</math> occurs at <math>x=9z.</math> Thus, <math>f(9z/3) = f(3z) = (9z)^2 + 9z + 1</math>. We set this equal to 7:<br />
<br />
<math>81z^2 + 9z +1 = 7 \Longrightarrow 81z^2 + 9z - 6 = 0</math>. For any quadratic <math>ax^2 + bx +c = 0</math>, the sum of the roots is <math>-\frac{b}{a}</math>. Thus, the sum of the roots of this equation is <math>-\frac{9}{81} = \boxed{-\frac{1}{9}} \Longrightarrow \boxed{\text{(B)}}</math><br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=14|num-a=16}}<br />
{{AMC10 box|year=2000|num-b=23|num-a=25}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_8&diff=1080542000 AMC 12 Problems/Problem 82019-07-30T21:43:25Z<p>Rejas: /* Solution 4 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #8]] and [[2000 AMC 10 Problems|2000 AMC 10 #12]]}}<br />
==Problem==<br />
<br />
Figures <math>0</math>, <math>1</math>, <math>2</math>, and <math>3</math> consist of <math>1</math>, <math>5</math>, <math>13</math>, and <math>25</math> nonoverlapping unit squares, respectively. If the pattern were continued, how many nonoverlapping unit squares would there be in figure 100?<br />
<br />
<asy><br />
unitsize(8);<br />
draw((0,0)--(1,0)--(1,1)--(0,1)--cycle);<br />
draw((9,0)--(10,0)--(10,3)--(9,3)--cycle);<br />
draw((8,1)--(11,1)--(11,2)--(8,2)--cycle);<br />
draw((19,0)--(20,0)--(20,5)--(19,5)--cycle);<br />
draw((18,1)--(21,1)--(21,4)--(18,4)--cycle);<br />
draw((17,2)--(22,2)--(22,3)--(17,3)--cycle);<br />
draw((32,0)--(33,0)--(33,7)--(32,7)--cycle);<br />
draw((29,3)--(36,3)--(36,4)--(29,4)--cycle);<br />
draw((31,1)--(34,1)--(34,6)--(31,6)--cycle);<br />
draw((30,2)--(35,2)--(35,5)--(30,5)--cycle);<br />
label("Figure",(0.5,-1),S);<br />
label("$0$",(0.5,-2.5),S);<br />
label("Figure",(9.5,-1),S);<br />
label("$1$",(9.5,-2.5),S);<br />
label("Figure",(19.5,-1),S);<br />
label("$2$",(19.5,-2.5),S);<br />
label("Figure",(32.5,-1),S);<br />
label("$3$",(32.5,-2.5),S);<br />
</asy><br />
<br />
<br />
<math>\mathrm{(A)}\ 10401 \qquad\mathrm{(B)}\ 19801 \qquad\mathrm{(C)}\ 20201 \qquad\mathrm{(D)}\ 39801 \qquad\mathrm{(E)}\ 40801</math><br />
<br />
==Solution==<br />
<br />
<br />
<br />
===Solution 2===<br />
<br />
We can divide up figure <math>n</math> to get the sum of the sum of the first <math>n+1</math> odd numbers and the sum of the first <math>n</math> odd numbers. If you do not see this, here is the example for <math>n=3</math>:<br />
<br />
<asy><br />
draw((3,0)--(4,0)--(4,7)--(3,7)--cycle);<br />
draw((0,3)--(7,3)--(7,4)--(0,4)--cycle);<br />
draw((2,1)--(5,1)--(5,6)--(2,6)--cycle);<br />
draw((1,2)--(6,2)--(6,5)--(1,5)--cycle);<br />
draw((3,0)--(3,7));<br />
</asy><br />
<br />
The sum of the first <math>n</math> odd numbers is <math>n^2</math>, so for figure <math>n</math>, there are <math>(n+1)^2+n^2</math> unit squares. We plug in <math>n=100</math> to get <math>\boxed{\textbf{(C) }20201}</math>.<br />
<br />
===Solution 3===<br />
<br />
Using the recursion from solution 1, we see that the first differences of <math>4, 8, 12, ...</math> form an arithmetic progression, and consequently that the second differences are constant and all equal to <math>4</math>. Thus, the original sequence can be generated from a quadratic function.<br />
<br />
If <math>f(n) = an^2 + bn + c</math>, and <math>f(0) = 1</math>, <math>f(1) = 5</math>, and <math>f(2) = 13</math>, we get a system of three equations in three variables:<br />
<br />
<math>f(0) = 1</math> gives <math>c = 1</math><br />
<br />
<math>f(1) = 5</math> gives <math>a + b + c = 5</math><br />
<br />
<math>f(2) = 13</math> gives <math>4a + 2b + c = 13</math><br />
<br />
Plugging in <math>c=1</math> into the last two equations gives <br />
<br />
<math>a + b = 4</math><br />
<br />
<math>4a + 2b = 12</math><br />
<br />
Dividing the second equation by 2 gives the system:<br />
<br />
<math>a + b = 4</math><br />
<br />
<math>2a + b = 6</math><br />
<br />
Subtracting the first equation from the second gives <math>a = 2</math>, and hence <math>b = 2</math>. Thus, our quadratic function is:<br />
<br />
<math>f(n) = 2n^2 + 2n + 1</math><br />
<br />
Calculating the answer to our problem, <math>f(100) = 20000 + 200 + 1 = 20201</math>, which is choice <math>\boxed{\textbf{(C) }20201}</math>.<br />
<br />
===Solution 4===<br />
We can see that each figure <math>n</math> has a central box and 4 columns of <math>n</math> boxes on each side of each square. Therefore, at figure 100, there is a central box with 100 boxes on the top, right, left, and bottom. Knowing that each quarter of each figure has a pyramid structure, we know that for each quarter there are <math>\sum_{n=1}^{100} n = 5050</math> squares. <math>4 \cdot 5050 = 20200</math>. Adding in the original center box we have <math> 20200 + 1 = \boxed{\textbf{(C) }20201}</math>.<br />
<br />
==Solution 5==<br />
Let <math>a_n</math> be the number of squares in figure <math>n</math>. We can easily see that <br />
<cmath>a_0=4\cdot 0+1</cmath><br />
<cmath>a_1=4\cdot 1+1</cmath><br />
<cmath>a_2=4\cdot 3+1</cmath><br />
<cmath>a_3=4\cdot 6+1.</cmath><br />
Note that in <math>a_n</math>, the number multiplied by the 4 is the <math>n</math>th triangular number. Hence, <math>a_{100}=4\cdot \frac{100\cdot 101}{2}+1=\boxed{\textbf{(C) }20201}</math>.<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2000|num-b=7|num-a=9}}<br />
{{AMC10 box|year=2000|num-b=11|num-a=13}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_8&diff=1080532000 AMC 12 Problems/Problem 82019-07-30T21:43:04Z<p>Rejas: /* Solution 5 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #8]] and [[2000 AMC 10 Problems|2000 AMC 10 #12]]}}<br />
==Problem==<br />
<br />
Figures <math>0</math>, <math>1</math>, <math>2</math>, and <math>3</math> consist of <math>1</math>, <math>5</math>, <math>13</math>, and <math>25</math> nonoverlapping unit squares, respectively. If the pattern were continued, how many nonoverlapping unit squares would there be in figure 100?<br />
<br />
<asy><br />
unitsize(8);<br />
draw((0,0)--(1,0)--(1,1)--(0,1)--cycle);<br />
draw((9,0)--(10,0)--(10,3)--(9,3)--cycle);<br />
draw((8,1)--(11,1)--(11,2)--(8,2)--cycle);<br />
draw((19,0)--(20,0)--(20,5)--(19,5)--cycle);<br />
draw((18,1)--(21,1)--(21,4)--(18,4)--cycle);<br />
draw((17,2)--(22,2)--(22,3)--(17,3)--cycle);<br />
draw((32,0)--(33,0)--(33,7)--(32,7)--cycle);<br />
draw((29,3)--(36,3)--(36,4)--(29,4)--cycle);<br />
draw((31,1)--(34,1)--(34,6)--(31,6)--cycle);<br />
draw((30,2)--(35,2)--(35,5)--(30,5)--cycle);<br />
label("Figure",(0.5,-1),S);<br />
label("$0$",(0.5,-2.5),S);<br />
label("Figure",(9.5,-1),S);<br />
label("$1$",(9.5,-2.5),S);<br />
label("Figure",(19.5,-1),S);<br />
label("$2$",(19.5,-2.5),S);<br />
label("Figure",(32.5,-1),S);<br />
label("$3$",(32.5,-2.5),S);<br />
</asy><br />
<br />
<br />
<math>\mathrm{(A)}\ 10401 \qquad\mathrm{(B)}\ 19801 \qquad\mathrm{(C)}\ 20201 \qquad\mathrm{(D)}\ 39801 \qquad\mathrm{(E)}\ 40801</math><br />
<br />
==Solution==<br />
<br />
<br />
<br />
===Solution 2===<br />
<br />
We can divide up figure <math>n</math> to get the sum of the sum of the first <math>n+1</math> odd numbers and the sum of the first <math>n</math> odd numbers. If you do not see this, here is the example for <math>n=3</math>:<br />
<br />
<asy><br />
draw((3,0)--(4,0)--(4,7)--(3,7)--cycle);<br />
draw((0,3)--(7,3)--(7,4)--(0,4)--cycle);<br />
draw((2,1)--(5,1)--(5,6)--(2,6)--cycle);<br />
draw((1,2)--(6,2)--(6,5)--(1,5)--cycle);<br />
draw((3,0)--(3,7));<br />
</asy><br />
<br />
The sum of the first <math>n</math> odd numbers is <math>n^2</math>, so for figure <math>n</math>, there are <math>(n+1)^2+n^2</math> unit squares. We plug in <math>n=100</math> to get <math>\boxed{\textbf{(C) }20201}</math>.<br />
<br />
===Solution 3===<br />
<br />
Using the recursion from solution 1, we see that the first differences of <math>4, 8, 12, ...</math> form an arithmetic progression, and consequently that the second differences are constant and all equal to <math>4</math>. Thus, the original sequence can be generated from a quadratic function.<br />
<br />
If <math>f(n) = an^2 + bn + c</math>, and <math>f(0) = 1</math>, <math>f(1) = 5</math>, and <math>f(2) = 13</math>, we get a system of three equations in three variables:<br />
<br />
<math>f(0) = 1</math> gives <math>c = 1</math><br />
<br />
<math>f(1) = 5</math> gives <math>a + b + c = 5</math><br />
<br />
<math>f(2) = 13</math> gives <math>4a + 2b + c = 13</math><br />
<br />
Plugging in <math>c=1</math> into the last two equations gives <br />
<br />
<math>a + b = 4</math><br />
<br />
<math>4a + 2b = 12</math><br />
<br />
Dividing the second equation by 2 gives the system:<br />
<br />
<math>a + b = 4</math><br />
<br />
<math>2a + b = 6</math><br />
<br />
Subtracting the first equation from the second gives <math>a = 2</math>, and hence <math>b = 2</math>. Thus, our quadratic function is:<br />
<br />
<math>f(n) = 2n^2 + 2n + 1</math><br />
<br />
Calculating the answer to our problem, <math>f(100) = 20000 + 200 + 1 = 20201</math>, which is choice <math>\boxed{\textbf{(C) }20201}</math>.<br />
<br />
===Solution 4===<br />
We can see that each figure <math>n</math> has a central box and 4 columns of <math>n</math> boxes on each side of each square. Therefore, at figure 100, there is a central box with 100 boxes on the top, right, left, and bottom. Knowing that each quarter of each figure has a pyramid structure, we know that for each quarter there are <math>\sum_{n=1}^{100} n = 5050</math> squares. <math>4 \cdot 5050 = 20200</math>. Adding in the original center box we have <math> 20200 + 1 = 20201</math> which is answer choice <math> \boxed{\text{C}}</math><br />
<br />
==Solution 5==<br />
Let <math>a_n</math> be the number of squares in figure <math>n</math>. We can easily see that <br />
<cmath>a_0=4\cdot 0+1</cmath><br />
<cmath>a_1=4\cdot 1+1</cmath><br />
<cmath>a_2=4\cdot 3+1</cmath><br />
<cmath>a_3=4\cdot 6+1.</cmath><br />
Note that in <math>a_n</math>, the number multiplied by the 4 is the <math>n</math>th triangular number. Hence, <math>a_{100}=4\cdot \frac{100\cdot 101}{2}+1=\boxed{\textbf{(C) }20201}</math>.<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2000|num-b=7|num-a=9}}<br />
{{AMC10 box|year=2000|num-b=11|num-a=13}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_8&diff=1080522000 AMC 12 Problems/Problem 82019-07-30T21:42:39Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #8]] and [[2000 AMC 10 Problems|2000 AMC 10 #12]]}}<br />
==Problem==<br />
<br />
Figures <math>0</math>, <math>1</math>, <math>2</math>, and <math>3</math> consist of <math>1</math>, <math>5</math>, <math>13</math>, and <math>25</math> nonoverlapping unit squares, respectively. If the pattern were continued, how many nonoverlapping unit squares would there be in figure 100?<br />
<br />
<asy><br />
unitsize(8);<br />
draw((0,0)--(1,0)--(1,1)--(0,1)--cycle);<br />
draw((9,0)--(10,0)--(10,3)--(9,3)--cycle);<br />
draw((8,1)--(11,1)--(11,2)--(8,2)--cycle);<br />
draw((19,0)--(20,0)--(20,5)--(19,5)--cycle);<br />
draw((18,1)--(21,1)--(21,4)--(18,4)--cycle);<br />
draw((17,2)--(22,2)--(22,3)--(17,3)--cycle);<br />
draw((32,0)--(33,0)--(33,7)--(32,7)--cycle);<br />
draw((29,3)--(36,3)--(36,4)--(29,4)--cycle);<br />
draw((31,1)--(34,1)--(34,6)--(31,6)--cycle);<br />
draw((30,2)--(35,2)--(35,5)--(30,5)--cycle);<br />
label("Figure",(0.5,-1),S);<br />
label("$0$",(0.5,-2.5),S);<br />
label("Figure",(9.5,-1),S);<br />
label("$1$",(9.5,-2.5),S);<br />
label("Figure",(19.5,-1),S);<br />
label("$2$",(19.5,-2.5),S);<br />
label("Figure",(32.5,-1),S);<br />
label("$3$",(32.5,-2.5),S);<br />
</asy><br />
<br />
<br />
<math>\mathrm{(A)}\ 10401 \qquad\mathrm{(B)}\ 19801 \qquad\mathrm{(C)}\ 20201 \qquad\mathrm{(D)}\ 39801 \qquad\mathrm{(E)}\ 40801</math><br />
<br />
==Solution==<br />
<br />
<br />
<br />
===Solution 2===<br />
<br />
We can divide up figure <math>n</math> to get the sum of the sum of the first <math>n+1</math> odd numbers and the sum of the first <math>n</math> odd numbers. If you do not see this, here is the example for <math>n=3</math>:<br />
<br />
<asy><br />
draw((3,0)--(4,0)--(4,7)--(3,7)--cycle);<br />
draw((0,3)--(7,3)--(7,4)--(0,4)--cycle);<br />
draw((2,1)--(5,1)--(5,6)--(2,6)--cycle);<br />
draw((1,2)--(6,2)--(6,5)--(1,5)--cycle);<br />
draw((3,0)--(3,7));<br />
</asy><br />
<br />
The sum of the first <math>n</math> odd numbers is <math>n^2</math>, so for figure <math>n</math>, there are <math>(n+1)^2+n^2</math> unit squares. We plug in <math>n=100</math> to get <math>\boxed{\textbf{(C) }20201}</math>.<br />
<br />
===Solution 3===<br />
<br />
Using the recursion from solution 1, we see that the first differences of <math>4, 8, 12, ...</math> form an arithmetic progression, and consequently that the second differences are constant and all equal to <math>4</math>. Thus, the original sequence can be generated from a quadratic function.<br />
<br />
If <math>f(n) = an^2 + bn + c</math>, and <math>f(0) = 1</math>, <math>f(1) = 5</math>, and <math>f(2) = 13</math>, we get a system of three equations in three variables:<br />
<br />
<math>f(0) = 1</math> gives <math>c = 1</math><br />
<br />
<math>f(1) = 5</math> gives <math>a + b + c = 5</math><br />
<br />
<math>f(2) = 13</math> gives <math>4a + 2b + c = 13</math><br />
<br />
Plugging in <math>c=1</math> into the last two equations gives <br />
<br />
<math>a + b = 4</math><br />
<br />
<math>4a + 2b = 12</math><br />
<br />
Dividing the second equation by 2 gives the system:<br />
<br />
<math>a + b = 4</math><br />
<br />
<math>2a + b = 6</math><br />
<br />
Subtracting the first equation from the second gives <math>a = 2</math>, and hence <math>b = 2</math>. Thus, our quadratic function is:<br />
<br />
<math>f(n) = 2n^2 + 2n + 1</math><br />
<br />
Calculating the answer to our problem, <math>f(100) = 20000 + 200 + 1 = 20201</math>, which is choice <math>\boxed{\textbf{(C) }20201}</math>.<br />
<br />
===Solution 4===<br />
We can see that each figure <math>n</math> has a central box and 4 columns of <math>n</math> boxes on each side of each square. Therefore, at figure 100, there is a central box with 100 boxes on the top, right, left, and bottom. Knowing that each quarter of each figure has a pyramid structure, we know that for each quarter there are <math>\sum_{n=1}^{100} n = 5050</math> squares. <math>4 \cdot 5050 = 20200</math>. Adding in the original center box we have <math> 20200 + 1 = 20201</math> which is answer choice <math> \boxed{\text{C}}</math><br />
<br />
==Solution 5==<br />
Let <math>a_n</math> be the number of squares in figure <math>n</math>. We can easily see that <br />
<cmath>a_0=4\cdot 0+1</cmath><br />
<cmath>a_1=4\cdot 1+1</cmath><br />
<cmath>a_2=4\cdot 3+1</cmath><br />
<cmath>a_3=4\cdot 6+1.</cmath><br />
Note that in <math>a_n</math>, the number multiplied by the 4 is the <math>n</math>th triangular number. Hence, <math>a_{100}=4\cdot \frac{100\cdot 101}{2}+1=20201,</math> which is <math>\boxed{\text{C}}</math>.<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2000|num-b=7|num-a=9}}<br />
{{AMC10 box|year=2000|num-b=11|num-a=13}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_8&diff=1080512000 AMC 12 Problems/Problem 82019-07-30T21:42:20Z<p>Rejas: /* Solution 3 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #8]] and [[2000 AMC 10 Problems|2000 AMC 10 #12]]}}<br />
==Problem==<br />
<br />
Figures <math>0</math>, <math>1</math>, <math>2</math>, and <math>3</math> consist of <math>1</math>, <math>5</math>, <math>13</math>, and <math>25</math> nonoverlapping unit squares, respectively. If the pattern were continued, how many nonoverlapping unit squares would there be in figure 100?<br />
<br />
<asy><br />
unitsize(8);<br />
draw((0,0)--(1,0)--(1,1)--(0,1)--cycle);<br />
draw((9,0)--(10,0)--(10,3)--(9,3)--cycle);<br />
draw((8,1)--(11,1)--(11,2)--(8,2)--cycle);<br />
draw((19,0)--(20,0)--(20,5)--(19,5)--cycle);<br />
draw((18,1)--(21,1)--(21,4)--(18,4)--cycle);<br />
draw((17,2)--(22,2)--(22,3)--(17,3)--cycle);<br />
draw((32,0)--(33,0)--(33,7)--(32,7)--cycle);<br />
draw((29,3)--(36,3)--(36,4)--(29,4)--cycle);<br />
draw((31,1)--(34,1)--(34,6)--(31,6)--cycle);<br />
draw((30,2)--(35,2)--(35,5)--(30,5)--cycle);<br />
label("Figure",(0.5,-1),S);<br />
label("$0$",(0.5,-2.5),S);<br />
label("Figure",(9.5,-1),S);<br />
label("$1$",(9.5,-2.5),S);<br />
label("Figure",(19.5,-1),S);<br />
label("$2$",(19.5,-2.5),S);<br />
label("Figure",(32.5,-1),S);<br />
label("$3$",(32.5,-2.5),S);<br />
</asy><br />
<br />
<br />
<math>\mathrm{(A)}\ 10401 \qquad\mathrm{(B)}\ 19801 \qquad\mathrm{(C)}\ 20201 \qquad\mathrm{(D)}\ 39801 \qquad\mathrm{(E)}\ 40801</math><br />
<br />
==Solution==<br />
<br />
<br />
<br />
===Solution 2===<br />
<br />
We can divide up figure <math>n</math> to get the sum of the sum of the first <math>n+1</math> odd numbers and the sum of the first <math>n</math> odd numbers. If you do not see this, here is the example for <math>n=3</math>:<br />
<br />
<asy><br />
draw((3,0)--(4,0)--(4,7)--(3,7)--cycle);<br />
draw((0,3)--(7,3)--(7,4)--(0,4)--cycle);<br />
draw((2,1)--(5,1)--(5,6)--(2,6)--cycle);<br />
draw((1,2)--(6,2)--(6,5)--(1,5)--cycle);<br />
draw((3,0)--(3,7));<br />
</asy><br />
<br />
The sum of the first <math>n</math> odd numbers is <math>n^2</math>, so for figure <math>n</math>, there are <math>(n+1)^2+n^2</math> unit squares. We plug in <math>n=100</math> to get <math>20201</math>, which is choice <math>\boxed{\text{C}}</math><br />
<br />
===Solution 3===<br />
<br />
Using the recursion from solution 1, we see that the first differences of <math>4, 8, 12, ...</math> form an arithmetic progression, and consequently that the second differences are constant and all equal to <math>4</math>. Thus, the original sequence can be generated from a quadratic function.<br />
<br />
If <math>f(n) = an^2 + bn + c</math>, and <math>f(0) = 1</math>, <math>f(1) = 5</math>, and <math>f(2) = 13</math>, we get a system of three equations in three variables:<br />
<br />
<math>f(0) = 1</math> gives <math>c = 1</math><br />
<br />
<math>f(1) = 5</math> gives <math>a + b + c = 5</math><br />
<br />
<math>f(2) = 13</math> gives <math>4a + 2b + c = 13</math><br />
<br />
Plugging in <math>c=1</math> into the last two equations gives <br />
<br />
<math>a + b = 4</math><br />
<br />
<math>4a + 2b = 12</math><br />
<br />
Dividing the second equation by 2 gives the system:<br />
<br />
<math>a + b = 4</math><br />
<br />
<math>2a + b = 6</math><br />
<br />
Subtracting the first equation from the second gives <math>a = 2</math>, and hence <math>b = 2</math>. Thus, our quadratic function is:<br />
<br />
<math>f(n) = 2n^2 + 2n + 1</math><br />
<br />
Calculating the answer to our problem, <math>f(100) = 20000 + 200 + 1 = 20201</math>, which is choice <math>\boxed{\textbf{(C) }20201}</math>.<br />
<br />
===Solution 4===<br />
We can see that each figure <math>n</math> has a central box and 4 columns of <math>n</math> boxes on each side of each square. Therefore, at figure 100, there is a central box with 100 boxes on the top, right, left, and bottom. Knowing that each quarter of each figure has a pyramid structure, we know that for each quarter there are <math>\sum_{n=1}^{100} n = 5050</math> squares. <math>4 \cdot 5050 = 20200</math>. Adding in the original center box we have <math> 20200 + 1 = 20201</math> which is answer choice <math> \boxed{\text{C}}</math><br />
<br />
==Solution 5==<br />
Let <math>a_n</math> be the number of squares in figure <math>n</math>. We can easily see that <br />
<cmath>a_0=4\cdot 0+1</cmath><br />
<cmath>a_1=4\cdot 1+1</cmath><br />
<cmath>a_2=4\cdot 3+1</cmath><br />
<cmath>a_3=4\cdot 6+1.</cmath><br />
Note that in <math>a_n</math>, the number multiplied by the 4 is the <math>n</math>th triangular number. Hence, <math>a_{100}=4\cdot \frac{100\cdot 101}{2}+1=20201,</math> which is <math>\boxed{\text{C}}</math>.<br />
<br />
==See Also==<br />
<br />
{{AMC12 box|year=2000|num-b=7|num-a=9}}<br />
{{AMC10 box|year=2000|num-b=11|num-a=13}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_6&diff=1080502000 AMC 12 Problems/Problem 62019-07-30T21:41:17Z<p>Rejas: /* Solution 1 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #6]] and [[2000 AMC 10 Problems|2000 AMC 10 #11]]}}<br />
<br />
== Problem ==<br />
Two different [[prime number]]s between <math>4</math> and <math>18</math> are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?<br />
<br />
<math> \mathrm{(A) \ 22 } \qquad \mathrm{(B) \ 60 } \qquad \mathrm{(C) \ 119 } \qquad \mathrm{(D) \ 194 } \qquad \mathrm{(E) \ 231 } </math><br />
<br />
==Solution 1==<br />
<br />
All prime numbers between 4 and 18 have an odd product and an even sum. Any odd number minus an even number is an odd number, so we can eliminate B, D, and A. Since the highest two prime numbers we can pick are 13 and 17, the highest number we can make is <math>(13)(17)-(13+17) = 221 - 30 = 191</math>. Thus, we can eliminate E. So, the answer must be <math>\boxed{\textbf{(C) }119}</math>.<br />
<br />
==Solution 2==<br />
<br />
Let the two primes be <math>p</math> and <math>q</math>. We wish to obtain the value of <math>pq-(p+q)</math>, or <math>pq-p-q</math>. Using [[Simon's Favorite Factoring Trick]], we can rewrite this expression as <math>(1-p)(1-q) -1</math> or <math>(p-1)(q-1) -1</math>. Noticing that <math>(13-1)(11-1) - 1 = 120-1 = 119</math>, we see that the answer is <math>\boxed{\textbf{(C) }119}</math>.<br />
<br />
==Solution 3==<br />
The answer must be in the form <math>pq - p - q</math> = <math>(p - 1)(q - 1) - 1</math>. Since <math>p - 1</math> and <math>q - 1</math> are both even, <math>(p - 1)(q - 1) - 1</math> is <math>3 \pmod 4</math>, and the only answer that is <math>3 \pmod 4</math> is <math>\boxed{\textbf{(C) }119}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=5|num-a=7}}<br />
{{AMC10 box|year=2000|num-b=10|num-a=12}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2000_AMC_12_Problems/Problem_6&diff=1080492000 AMC 12 Problems/Problem 62019-07-30T21:41:07Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>{{duplicate|[[2000 AMC 12 Problems|2000 AMC 12 #6]] and [[2000 AMC 10 Problems|2000 AMC 10 #11]]}}<br />
<br />
== Problem ==<br />
Two different [[prime number]]s between <math>4</math> and <math>18</math> are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?<br />
<br />
<math> \mathrm{(A) \ 22 } \qquad \mathrm{(B) \ 60 } \qquad \mathrm{(C) \ 119 } \qquad \mathrm{(D) \ 194 } \qquad \mathrm{(E) \ 231 } </math><br />
<br />
==Solution 1==<br />
<br />
All prime numbers between 4 and 18 have an odd product and an even sum. Any odd number minus an even number is an odd number, so we can eliminate B, D, and A. Since the highest two prime numbers we can pick are 13 and 17, the highest number we can make is <math>(13)(17)-(13+17) = 221 - 30 = 191</math>. Thus, we can eliminate E. So, the answer must be <math>\mathrm{(C)}</math>.<br />
<br />
==Solution 2==<br />
<br />
Let the two primes be <math>p</math> and <math>q</math>. We wish to obtain the value of <math>pq-(p+q)</math>, or <math>pq-p-q</math>. Using [[Simon's Favorite Factoring Trick]], we can rewrite this expression as <math>(1-p)(1-q) -1</math> or <math>(p-1)(q-1) -1</math>. Noticing that <math>(13-1)(11-1) - 1 = 120-1 = 119</math>, we see that the answer is <math>\boxed{\textbf{(C) }119}</math>.<br />
<br />
==Solution 3==<br />
The answer must be in the form <math>pq - p - q</math> = <math>(p - 1)(q - 1) - 1</math>. Since <math>p - 1</math> and <math>q - 1</math> are both even, <math>(p - 1)(q - 1) - 1</math> is <math>3 \pmod 4</math>, and the only answer that is <math>3 \pmod 4</math> is <math>\boxed{\textbf{(C) }119}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2000|num-b=5|num-a=7}}<br />
{{AMC10 box|year=2000|num-b=10|num-a=12}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2010_AIME_I_Problems/Problem_3&diff=1079262010 AIME I Problems/Problem 32019-07-25T21:01:57Z<p>Rejas: /* Solution 3 */</p>
<hr />
<div>== Problem ==<br />
Suppose that <math>y = \frac34x</math> and <math>x^y = y^x</math>. The quantity <math>x + y</math> can be expressed as a rational number <math>\frac {r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r + s</math>.<br />
<br />
== Solution 1 ==<br />
Substitute <math>y = \frac34x</math> into <math>x^y = y^x</math> and solve.<br />
<cmath>x^{\frac34x} = (\frac34x)^x</cmath><br />
<cmath>x^{\frac34x} = (\frac34)^x \cdot x^x</cmath><br />
<cmath>x^{-\frac14x} = (\frac34)^x</cmath><br />
<cmath>x^{-\frac14} = \frac34</cmath><br />
<cmath>x = \frac{256}{81}</cmath><br />
<cmath>y = \frac34x = \frac{192}{81}</cmath><br />
<cmath>x + y = \frac{448}{81}</cmath><br />
<cmath>448 + 81 = \boxed{529}</cmath><br />
<br />
== Solution 2 ==<br />
We solve in general using <math>c</math> instead of <math>3/4</math>. Substituting <math>y = cx</math>, we have:<br />
<br />
<center><cmath>x^{cx} = (cx)^x \Longrightarrow (x^x)^c = c^x\cdot x^x</cmath></center><br />
<br />
Dividing by <math>x^x</math>, we get <math>(x^x)^{c - 1} = c^x</math>.<br />
<br />
Taking the <math>x</math>th root, <math>x^{c - 1} = c</math>, or <math>x = c^{1/(c - 1)}</math>.<br />
<br />
In the case <math>c = \frac34</math>, <math>x = \Bigg(\frac34\Bigg)^{ - 4} = \Bigg(\frac43\Bigg)^4 = \frac {256}{81}</math>, <math>y = \frac {64}{27}</math>, <math>x + y = \frac {256 + 192}{81} = \frac {448}{81}</math>, yielding an answer of <math>448 + 81 = \boxed{529}</math>.<br />
<br />
== Solution 3 ==<br />
Taking the logarithm base <math>x</math> of both sides, we arrive with:<br />
<br />
<center><cmath> y = log_x y^x \Longrightarrow \frac{y}{x} = log_x y = log_x \frac{3}{4}x = \frac{3}{4}</cmath></center><br />
Where the last two simplifications were made since <math>y = \frac{3}{4}x</math>. Then,<br />
<center><cmath>x^{\frac{3}{4}} = \frac{3}{4}x \Longrightarrow x^{\frac{1}{4}} = \frac{4}{3} \Longrightarrow x = \left(\frac{4}{3}\right)^4</cmath></center><br />
Then, <math>y = \left(\frac{4}{3}\right)^3</math>, and thus:<br />
<center> <cmath>x+y = \left(\frac{4}{3}\right)^3 \left(\frac{4}{3} + 1 \right) = \frac{448}{81} \Longrightarrow 448 + 81 = \boxed{529}</cmath> </center><br />
<br />
== See Also ==<br />
{{AIME box|year=2010|num-b=2|num-a=4|n=I}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2010_AIME_I_Problems/Problem_3&diff=1079252010 AIME I Problems/Problem 32019-07-25T21:01:38Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>== Problem ==<br />
Suppose that <math>y = \frac34x</math> and <math>x^y = y^x</math>. The quantity <math>x + y</math> can be expressed as a rational number <math>\frac {r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r + s</math>.<br />
<br />
== Solution 1 ==<br />
Substitute <math>y = \frac34x</math> into <math>x^y = y^x</math> and solve.<br />
<cmath>x^{\frac34x} = (\frac34x)^x</cmath><br />
<cmath>x^{\frac34x} = (\frac34)^x \cdot x^x</cmath><br />
<cmath>x^{-\frac14x} = (\frac34)^x</cmath><br />
<cmath>x^{-\frac14} = \frac34</cmath><br />
<cmath>x = \frac{256}{81}</cmath><br />
<cmath>y = \frac34x = \frac{192}{81}</cmath><br />
<cmath>x + y = \frac{448}{81}</cmath><br />
<cmath>448 + 81 = \boxed{529}</cmath><br />
<br />
== Solution 2 ==<br />
We solve in general using <math>c</math> instead of <math>3/4</math>. Substituting <math>y = cx</math>, we have:<br />
<br />
<center><cmath>x^{cx} = (cx)^x \Longrightarrow (x^x)^c = c^x\cdot x^x</cmath></center><br />
<br />
Dividing by <math>x^x</math>, we get <math>(x^x)^{c - 1} = c^x</math>.<br />
<br />
Taking the <math>x</math>th root, <math>x^{c - 1} = c</math>, or <math>x = c^{1/(c - 1)}</math>.<br />
<br />
In the case <math>c = \frac34</math>, <math>x = \Bigg(\frac34\Bigg)^{ - 4} = \Bigg(\frac43\Bigg)^4 = \frac {256}{81}</math>, <math>y = \frac {64}{27}</math>, <math>x + y = \frac {256 + 192}{81} = \frac {448}{81}</math>, yielding an answer of <math>448 + 81 = \boxed{529}</math>.<br />
<br />
== Solution 3 ==<br />
Taking the logarithm base <math>x</math> of both sides, we arrive with:<br />
<br />
<center><cmath> y = log_x y^x \Longrightarrow \frac{y}{x} = log_x y = log_x \frac{3}{4}x = \frac{3}{4}</cmath></center><br />
Where the last two simplifications were made since <math>y = \frac{3}{4}x</math>. Then,<br />
<center><cmath>x^{\frac{3}{4}} = \frac{3}{4}x \Longrightarrow x^{\frac{1}{4}} = \frac{4}{3} \Longrightarrow x = \left(\frac{4}{3}\right)^4</cmath></center><br />
Then, <math>y = \left(\frac{4}{3}\right)^3</math>, and thus:<br />
<center> <cmath>x+y = \left(\frac{4}{3}\right)^3 \left(\frac{4}{3} + 1 \right) = \frac{448}{81} \Longrightarrow 448 + 81 = \boxed{529}</cmath> </center><br />
<br />
== Solution 3 ==<br />
<cmath>x^{\frac34x} = (\frac34x)^x</cmath><br />
<cmath>x^{\frac34x} = (\frac34)^x \cdot x^x</cmath><br />
<cmath>x^{-\frac14x} = (\frac34)^x</cmath><br />
<cmath>x^{-\frac14} = \frac34</cmath><br />
<cmath>x = \frac{256}{81}</cmath><br />
<cmath>y = \frac34x = \frac{192}{81}</cmath><br />
<cmath>x + y = \frac{448}{81}</cmath><br />
<cmath>448 + 81 = \boxed{529}</cmath><br />
<br />
== See Also ==<br />
{{AIME box|year=2010|num-b=2|num-a=4|n=I}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2010_AIME_I_Problems/Problem_3&diff=1079242010 AIME I Problems/Problem 32019-07-25T21:01:16Z<p>Rejas: /* Solution */</p>
<hr />
<div>== Problem ==<br />
Suppose that <math>y = \frac34x</math> and <math>x^y = y^x</math>. The quantity <math>x + y</math> can be expressed as a rational number <math>\frac {r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r + s</math>.<br />
<br />
== Solution 1 ==<br />
Substitute <math>y = \frac34x</math> into <math>x^y = y^x</math> and solve.<br />
<cmath>x^{\frac34x} = (\frac34x)^x</cmath><br />
<cmath>x^{\frac34x} = (\frac34)^x \cdot x^x</cmath><br />
<cmath>x^{-\frac14x} = (\frac34)^x</cmath><br />
<cmath>x^{-\frac14} = \frac34</cmath><br />
<cmath>x = \frac{256}{81}</cmath><br />
<cmath>y = \frac34x = \frac{192}{81}</cmath><br />
<cmath>x + y = \frac{448}{81}</cmath><br />
<cmath>448 + 81 = \boxed{529}</cmath><br />
<br />
== Solution 2 ==<br />
We solve in general using <math>c</math> instead of <math>3/4</math>. Substituting <math>y = cx</math>, we have:<br />
<br />
<center><cmath>x^{cx} = (cx)^x \Longrightarrow (x^x)^c = c^x\cdot x^x</cmath></center><br />
<br />
Dividing by <math>x^x</math>, we get <math>(x^x)^{c - 1} = c^x</math>.<br />
<br />
Taking the <math>x</math>th root, <math>x^{c - 1} = c</math>, or <math>x = c^{1/(c - 1)}</math>.<br />
<br />
In the case <math>c = \frac34</math>, <math>x = \Bigg(\frac34\Bigg)^{ - 4} = \Bigg(\frac43\Bigg)^4 = \frac {256}{81}</math>, <math>y = \frac {64}{27}</math>, <math>x + y = \frac {256 + 192}{81} = \frac {448}{81}</math>, yielding an answer of <math>448 + 81 = \boxed{529}</math>.<br />
<br />
== Solution 2 ==<br />
Taking the logarithm base <math>x</math> of both sides, we arrive with:<br />
<br />
<center><cmath> y = log_x y^x \Longrightarrow \frac{y}{x} = log_x y = log_x \frac{3}{4}x = \frac{3}{4}</cmath></center><br />
Where the last two simplifications were made since <math>y = \frac{3}{4}x</math>. Then,<br />
<center><cmath>x^{\frac{3}{4}} = \frac{3}{4}x \Longrightarrow x^{\frac{1}{4}} = \frac{4}{3} \Longrightarrow x = \left(\frac{4}{3}\right)^4</cmath></center><br />
Then, <math>y = \left(\frac{4}{3}\right)^3</math>, and thus:<br />
<center> <cmath>x+y = \left(\frac{4}{3}\right)^3 \left(\frac{4}{3} + 1 \right) = \frac{448}{81} \Longrightarrow 448 + 81 = \boxed{529}</cmath> </center><br />
== Solution 3 ==<br />
<cmath>x^{\frac34x} = (\frac34x)^x</cmath><br />
<cmath>x^{\frac34x} = (\frac34)^x \cdot x^x</cmath><br />
<cmath>x^{-\frac14x} = (\frac34)^x</cmath><br />
<cmath>x^{-\frac14} = \frac34</cmath><br />
<cmath>x = \frac{256}{81}</cmath><br />
<cmath>y = \frac34x = \frac{192}{81}</cmath><br />
<cmath>x + y = \frac{448}{81}</cmath><br />
<cmath>448 + 81 = \boxed{529}</cmath><br />
<br />
== See Also ==<br />
{{AIME box|year=2010|num-b=2|num-a=4|n=I}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2010_AIME_I_Problems/Problem_3&diff=1079232010 AIME I Problems/Problem 32019-07-25T20:58:58Z<p>Rejas: /* Solution 2 */</p>
<hr />
<div>== Problem ==<br />
Suppose that <math>y = \frac34x</math> and <math>x^y = y^x</math>. The quantity <math>x + y</math> can be expressed as a rational number <math>\frac {r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r + s</math>.<br />
<br />
== Solution ==<br />
We solve in general using <math>c</math> instead of <math>3/4</math>. Substituting <math>y = cx</math>, we have:<br />
<br />
<center><cmath>x^{cx} = (cx)^x \Longrightarrow (x^x)^c = c^x\cdot x^x</cmath></center><br />
<br />
Dividing by <math>x^x</math>, we get <math>(x^x)^{c - 1} = c^x</math>.<br />
<br />
Taking the <math>x</math>th root, <math>x^{c - 1} = c</math>, or <math>x = c^{1/(c - 1)}</math>.<br />
<br />
In the case <math>c = \frac34</math>, <math>x = \Bigg(\frac34\Bigg)^{ - 4} = \Bigg(\frac43\Bigg)^4 = \frac {256}{81}</math>, <math>y = \frac {64}{27}</math>, <math>x + y = \frac {256 + 192}{81} = \frac {448}{81}</math>, yielding an answer of <math>448 + 81 = \boxed{529}</math>.<br />
<br />
== Solution 2 ==<br />
Taking the logarithm base <math>x</math> of both sides, we arrive with:<br />
<br />
<center><cmath> y = log_x y^x \Longrightarrow \frac{y}{x} = log_x y = log_x \frac{3}{4}x = \frac{3}{4}</cmath></center><br />
Where the last two simplifications were made since <math>y = \frac{3}{4}x</math>. Then,<br />
<center><cmath>x^{\frac{3}{4}} = \frac{3}{4}x \Longrightarrow x^{\frac{1}{4}} = \frac{4}{3} \Longrightarrow x = \left(\frac{4}{3}\right)^4</cmath></center><br />
Then, <math>y = \left(\frac{4}{3}\right)^3</math>, and thus:<br />
<center> <cmath>x+y = \left(\frac{4}{3}\right)^3 \left(\frac{4}{3} + 1 \right) = \frac{448}{81} \Longrightarrow 448 + 81 = \boxed{529}</cmath> </center><br />
== Solution 3 ==<br />
<cmath>x^{\frac34x} = (\frac34x)^x</cmath><br />
<cmath>x^{\frac34x} = (\frac34)^x \cdot x^x</cmath><br />
<cmath>x^{-\frac14x} = (\frac34)^x</cmath><br />
<cmath>x^{-\frac14} = \frac34</cmath><br />
<cmath>x = \frac{256}{81}</cmath><br />
<cmath>y = \frac34x = \frac{192}{81}</cmath><br />
<cmath>x + y = \frac{448}{81}</cmath><br />
<cmath>448 + 81 = \boxed{529}</cmath><br />
<br />
== See Also ==<br />
{{AIME box|year=2010|num-b=2|num-a=4|n=I}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2014_AIME_I_Problems/Problem_11&diff=1078812014 AIME I Problems/Problem 112019-07-24T23:40:52Z<p>Rejas: /* Solution (Nice) */</p>
<hr />
<div>== Problem 11 ==<br />
<br />
A token starts at the point <math>(0,0)</math> of an <math>xy</math>-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of <math>|y|=|x|</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
== Solution 1 (Nice) ==<br />
Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. <br />
<br />
However, we overcount exactly one case: ending at <math>(0, 0)</math>. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply <math>\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}</math>. Using PIE, the total probability is <math>\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}</math>, giving an answer of <math>\boxed{391}</math>.<br />
<br />
~sampai7<br />
<br />
<br />
== Solution 2 (Casework) ==<br />
<br />
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is <math>4^6</math>, or <math>4096</math>. There are 4 possible cases that land along the line <math>y = x</math>: <math>x,y = \pm 1; x,y = \pm 2; x,y = \pm 3;</math> or <math>x = y = 0</math>. We will count the number of ways to end up at <math>(1,1), (2,2),</math> and <math>(3,3)</math>, multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at <math>(0,0)</math>.<br />
<br />
*Case 1: The token ends at <math>(3, 3)</math>. In order for the token to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence <math>RRRUUU</math>, which is <math>{6\choose 3} = 20.</math><br />
<br />
*Case 2: The token ends at <math>(2,2)</math>. In order for the token to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences <math>RRRLUU</math> and <math>UUUDRR</math>, both of which are <math>{6\choose 1}{5\choose 2} = 60</math>, for a total of <math>120</math> possibilities.<br />
<br />
*Case 3: The token ends at <math>(1,1)</math>. In order for the token to end up here, it could have had:<br />
**1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RUUUDD</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>URRRLL</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence <math>UUDRRL</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(1,1)</math> is <math>300</math>.<br />
<br />
*Case 4: The token ends at <math>(0,0)</math>. In order for the token to end up here, it could have had:<br />
**3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRRLLL</math> is <math>{6\choose 3} = 20.</math><br />
**3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>UUUDDD</math> is <math>{6\choose 3} = 20.</math><br />
**1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RLUUDD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
**1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRLLUD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(0,0)</math> is <math>400</math>.<br />
<br />
Adding these cases together, we get that the total number of ways to end up on <math>y = x</math> is <math>4(20 + 120 + 300) + 400 = 2160</math>. Thus, our probability is <math>\frac{2160}{4096}</math>. When this fraction is fully reduced, it is <math>\frac{135}{256}</math>, so our answer is <math>135 + 256 = \boxed{391}.</math><br />
<br />
==Solution 3 (Casework)==<br />
We split this into cases by making a chart. In each row, the entries <math>(\pm1)</math> before the dividing line represent the right or left steps (without regard to order), and the entries after the dividing line represent the up or down steps (again, without regard to order). This table only represents the cases where the ending position <math>(x,y)</math> satisfies <math>x=y</math>.<br />
<cmath><br />
\begin{array}{ccccccccccccl}<br />
\multicolumn{5}{c}{R (+)\qquad L (-)}& |&\multicolumn{5}{c}{U (+)\qquad D (-)}\\<br />
+1&& +1&& +1&| & +1&& +1&& +1\\<br />
+1&& +1&& -1& | & +1&& +1&& -1\\<br />
+1&& -1&& -1& | & +1&& -1&& -1\\<br />
-1 && -1&& -1& | & -1&& -1&& -1\\<br />
\\<br />
+1&& +1&& +1&& -1 &|& +1&& +1\\<br />
+1&& +1&& -1 && -1 &|& +1 && -1\\<br />
+1&& -1&& -1 && -1 &|& -1 && -1 &&(\times 2 \text{ for symmetry by swapping }R-L\text{ and }U-D)\\<br />
\\<br />
+1&& +1 &&+1 &&-1&& -1& |& +1\\<br />
+1&& +1 &&-1&& -1&& -1 &|& -1&& (\times 2\text{ symmetry})\\<br />
\\<br />
+1&& +1 &&+1&& -1&& -1 &&-1&| & (\times2 \text{ symmetry})\\<br />
\end{array}<br />
</cmath><br />
Note that to account for the cases when <math>x=-y</math>, we can simply multiply the <math>U-D</math> steps by <math>-1</math>, so for example, the first row would become <cmath>+1 \qquad+1\qquad +1 \ \ \ \ |\ \ \ -1\qquad -1\qquad -1.</cmath> Therefore, we must multiply the number of possibilities in each case by <math>2</math>, except for when <math>x=y=0</math>.<br />
<br />
Now, we compute the number of possibilities for each case. In particular, we must compute the number of <math>RLUD</math> words, where <math>R</math> represents <math>+1</math> to the left of <math>|</math>, <math>L</math> represents <math>-1</math> to the left of <math>|</math>, <math>U</math> represents <math>+1</math> to the right of <math>|</math>, and <math>D</math> represents <math>-1</math> to the right of <math>|</math>. Using multinomials, we compute the following numbers of possibilities for each case.<br />
<cmath>{6\choose 3}\cdot 2+ \frac{6!}{2!2!}\cdot 2 + \frac{6!}{2!2!} \cdot 2 + {6\choose 3} \cdot 2 = 2(20 + 180 + 180 + 20) = 800</cmath><br />
<cmath>\frac{6!}{3!2!}\cdot 2 + \frac{6!}{2!2!} + \frac{6!}{3!2!}\cdot 2 = 120 + 180 + 120 = 420\ (\times2\text{ for symmetry})</cmath><br />
<cmath>\frac{6!}{3!2!} \cdot 2 + \frac{6!}{3!2!} \cdot 2 = 120 + 120 = 240\ (\times2\text{ for symmetry})</cmath><br />
<cmath>{6\choose 3} = 20\ (\times 2\text{ for symmetry})</cmath><br />
<br />
Thus, there are <math>800 + 840 + 480 + 40 = 2160</math> possibilities where <math>|x|=|y|</math>. Because there are <math>4^6</math> total possibilities, the probability is <math>\frac{2160}{4^6} = \frac{135}{256}</math>, so the answer is <math>\boxed{391}.</math><br />
<br />
==Solution 4 (States)==<br />
Denote <math>(x, y)_n</math> the probability that starting from point <math>(x, y)</math>, the token reaches a point on the graph of <math>|y| = |x|</math> in exactly <math>n</math> moves. The problem asks us to find <math>(0, 0)_6</math>. We start by breaking this down:<br />
<cmath>(0, 0)_6 = \frac14 \cdot ((0, 1)_5 + (0, -1)_5 + (1, 0)_5 + (-1, 0)_5)</cmath><br />
Notice that by symmetry, <math>(0, 1)_5 = (0, -1)_5 = (1, 0)_5 = (-1, 0)_5</math>, so the equation simplifies to<br />
<cmath>(0, 0)_6 = (0, 1)_5</cmath><br />
We now expand <math>(0, 1)_5</math>.<br />
<cmath>(0, 1)_5 = \frac14 \cdot ((0, 0)_4 + (0, 2)_4 + 2(1, 1)_4)</cmath><br />
First, we find <math>(0, 0)_4</math>.<br />
<cmath>(0, 0)_4 = (0, 1)_3</cmath><br />
<cmath>(0, 1)_3 = \frac14 \cdot ((0, 0)_2 + (0, 2)_2 + 2(1, 1)_2)</cmath><br />
At this point, we can just count the possibilities to find <math>(0, 0)_2 = \frac34</math>, <math>(0, 2)_2 = \frac{7}{16}</math>, and <math>(1, 1)_2 = \frac58</math>. Therefore,<br />
<cmath>(0, 1)_3 = \frac14 \cdot (\frac34 + \frac{7}{16} + 2 \cdot \frac58)</cmath><br />
<cmath>(0, 1)_3 = \frac{39}{64}</cmath><br />
Next, we find <math>(0, 2)_4</math>.<br />
<cmath>(0, 2)_4 = \frac14 \cdot ((0, 1)_3 + (0, 3)_3 + 2(1, 2)_3)</cmath><br />
We already calculated <math>(0, 1)_3</math>, so we just need to find <math>(0, 3)_3</math> and <math>(1, 2)_3</math><br />
<cmath>(0, 3)_3 = \frac14 \cdot ((0, 2)_2 + (0, 4)_2 + 2(1, 3)_2)</cmath><br />
<cmath>(0, 3)_3 = \frac14 \cdot (\frac{7}{16} + 0 + 2 \cdot \frac{1}{4})</cmath><br />
<cmath>(0, 3)_3 = \frac{15}{64}</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot ((1, 3)_2 + (1, 1)_2 + (0, 2)_2 + (2, 2)_2)</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot (\frac14 + \frac58 + \frac{7}{16} + \frac12)</cmath><br />
<cmath>(1, 2)_3 = \frac{29}{64}</cmath><br />
Therefore,<br />
<cmath>(0, 2)_4 = \frac14 \cdot (\frac{39}{64} + \frac{15}{64} + 2 \cdot \frac{29}{64})</cmath><br />
<cmath>(0, 2)_4 = \frac{7}{16}</cmath><br />
Finally, we find <math>(1, 1)_4</math>.<br />
<cmath>(1, 1)_4 = \frac12 \cdot ((0, 1)_3 + (1, 2)_3)</cmath><br />
<cmath>(1, 1)_4 = \frac12 \cdot (\frac{39}{64} + \frac{29}{64})</cmath><br />
<cmath>(1, 1)_4 = \frac{17}{32}</cmath><br />
Putting it all together,<br />
<cmath>(0, 0)_6 = (0, 1)_5 =\frac14 \cdot (\frac{39}{64} + \frac{7}{16} + 2 \cdot \frac{17}{32})</cmath><br />
<cmath>(0, 0)_6 = \frac{135}{256}</cmath><br />
Thus, the answer is <math>135 + 256 = \boxed{391}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2014|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2014_AIME_I_Problems/Problem_11&diff=1078802014 AIME I Problems/Problem 112019-07-24T23:40:34Z<p>Rejas: /* Solution (casework 2) */</p>
<hr />
<div>== Problem 11 ==<br />
<br />
A token starts at the point <math>(0,0)</math> of an <math>xy</math>-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of <math>|y|=|x|</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
== Solution 1 (Nice) ==<br />
Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. <br />
<br />
However, we overcount exactly one case: ending at <math>(0, 0)</math>. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply <math>\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}</math>. Using PIE, the total probability is <math>\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}</math>, giving an answer of <math>\boxed{391}</math>.<br />
<br />
~sampai7<br />
<br />
<br />
== Solution 2 (Casework) ==<br />
<br />
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is <math>4^6</math>, or <math>4096</math>. There are 4 possible cases that land along the line <math>y = x</math>: <math>x,y = \pm 1; x,y = \pm 2; x,y = \pm 3;</math> or <math>x = y = 0</math>. We will count the number of ways to end up at <math>(1,1), (2,2),</math> and <math>(3,3)</math>, multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at <math>(0,0)</math>.<br />
<br />
*Case 1: The token ends at <math>(3, 3)</math>. In order for the token to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence <math>RRRUUU</math>, which is <math>{6\choose 3} = 20.</math><br />
<br />
*Case 2: The token ends at <math>(2,2)</math>. In order for the token to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences <math>RRRLUU</math> and <math>UUUDRR</math>, both of which are <math>{6\choose 1}{5\choose 2} = 60</math>, for a total of <math>120</math> possibilities.<br />
<br />
*Case 3: The token ends at <math>(1,1)</math>. In order for the token to end up here, it could have had:<br />
**1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RUUUDD</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>URRRLL</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence <math>UUDRRL</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(1,1)</math> is <math>300</math>.<br />
<br />
*Case 4: The token ends at <math>(0,0)</math>. In order for the token to end up here, it could have had:<br />
**3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRRLLL</math> is <math>{6\choose 3} = 20.</math><br />
**3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>UUUDDD</math> is <math>{6\choose 3} = 20.</math><br />
**1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RLUUDD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
**1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRLLUD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(0,0)</math> is <math>400</math>.<br />
<br />
Adding these cases together, we get that the total number of ways to end up on <math>y = x</math> is <math>4(20 + 120 + 300) + 400 = 2160</math>. Thus, our probability is <math>\frac{2160}{4096}</math>. When this fraction is fully reduced, it is <math>\frac{135}{256}</math>, so our answer is <math>135 + 256 = \boxed{391}.</math><br />
<br />
==Solution 3 (Casework)==<br />
We split this into cases by making a chart. In each row, the entries <math>(\pm1)</math> before the dividing line represent the right or left steps (without regard to order), and the entries after the dividing line represent the up or down steps (again, without regard to order). This table only represents the cases where the ending position <math>(x,y)</math> satisfies <math>x=y</math>.<br />
<cmath><br />
\begin{array}{ccccccccccccl}<br />
\multicolumn{5}{c}{R (+)\qquad L (-)}& |&\multicolumn{5}{c}{U (+)\qquad D (-)}\\<br />
+1&& +1&& +1&| & +1&& +1&& +1\\<br />
+1&& +1&& -1& | & +1&& +1&& -1\\<br />
+1&& -1&& -1& | & +1&& -1&& -1\\<br />
-1 && -1&& -1& | & -1&& -1&& -1\\<br />
\\<br />
+1&& +1&& +1&& -1 &|& +1&& +1\\<br />
+1&& +1&& -1 && -1 &|& +1 && -1\\<br />
+1&& -1&& -1 && -1 &|& -1 && -1 &&(\times 2 \text{ for symmetry by swapping }R-L\text{ and }U-D)\\<br />
\\<br />
+1&& +1 &&+1 &&-1&& -1& |& +1\\<br />
+1&& +1 &&-1&& -1&& -1 &|& -1&& (\times 2\text{ symmetry})\\<br />
\\<br />
+1&& +1 &&+1&& -1&& -1 &&-1&| & (\times2 \text{ symmetry})\\<br />
\end{array}<br />
</cmath><br />
Note that to account for the cases when <math>x=-y</math>, we can simply multiply the <math>U-D</math> steps by <math>-1</math>, so for example, the first row would become <cmath>+1 \qquad+1\qquad +1 \ \ \ \ |\ \ \ -1\qquad -1\qquad -1.</cmath> Therefore, we must multiply the number of possibilities in each case by <math>2</math>, except for when <math>x=y=0</math>.<br />
<br />
Now, we compute the number of possibilities for each case. In particular, we must compute the number of <math>RLUD</math> words, where <math>R</math> represents <math>+1</math> to the left of <math>|</math>, <math>L</math> represents <math>-1</math> to the left of <math>|</math>, <math>U</math> represents <math>+1</math> to the right of <math>|</math>, and <math>D</math> represents <math>-1</math> to the right of <math>|</math>. Using multinomials, we compute the following numbers of possibilities for each case.<br />
<cmath>{6\choose 3}\cdot 2+ \frac{6!}{2!2!}\cdot 2 + \frac{6!}{2!2!} \cdot 2 + {6\choose 3} \cdot 2 = 2(20 + 180 + 180 + 20) = 800</cmath><br />
<cmath>\frac{6!}{3!2!}\cdot 2 + \frac{6!}{2!2!} + \frac{6!}{3!2!}\cdot 2 = 120 + 180 + 120 = 420\ (\times2\text{ for symmetry})</cmath><br />
<cmath>\frac{6!}{3!2!} \cdot 2 + \frac{6!}{3!2!} \cdot 2 = 120 + 120 = 240\ (\times2\text{ for symmetry})</cmath><br />
<cmath>{6\choose 3} = 20\ (\times 2\text{ for symmetry})</cmath><br />
<br />
Thus, there are <math>800 + 840 + 480 + 40 = 2160</math> possibilities where <math>|x|=|y|</math>. Because there are <math>4^6</math> total possibilities, the probability is <math>\frac{2160}{4^6} = \frac{135}{256}</math>, so the answer is <math>\boxed{391}.</math><br />
<br />
==Solution (Nice)==<br />
Yall need to stop bashing<br />
<br />
Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. <br />
<br />
However, we overcount exactly one case: ending at <math>(0, 0)</math>. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply <math>\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}</math>. Using PIE, the total probability is <math>\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}</math>, giving an answer of <math>\boxed{391}</math>.<br />
<br />
Thank,<br />
<br />
~sampai7<br />
<br />
==Solution 4 (States)==<br />
Denote <math>(x, y)_n</math> the probability that starting from point <math>(x, y)</math>, the token reaches a point on the graph of <math>|y| = |x|</math> in exactly <math>n</math> moves. The problem asks us to find <math>(0, 0)_6</math>. We start by breaking this down:<br />
<cmath>(0, 0)_6 = \frac14 \cdot ((0, 1)_5 + (0, -1)_5 + (1, 0)_5 + (-1, 0)_5)</cmath><br />
Notice that by symmetry, <math>(0, 1)_5 = (0, -1)_5 = (1, 0)_5 = (-1, 0)_5</math>, so the equation simplifies to<br />
<cmath>(0, 0)_6 = (0, 1)_5</cmath><br />
We now expand <math>(0, 1)_5</math>.<br />
<cmath>(0, 1)_5 = \frac14 \cdot ((0, 0)_4 + (0, 2)_4 + 2(1, 1)_4)</cmath><br />
First, we find <math>(0, 0)_4</math>.<br />
<cmath>(0, 0)_4 = (0, 1)_3</cmath><br />
<cmath>(0, 1)_3 = \frac14 \cdot ((0, 0)_2 + (0, 2)_2 + 2(1, 1)_2)</cmath><br />
At this point, we can just count the possibilities to find <math>(0, 0)_2 = \frac34</math>, <math>(0, 2)_2 = \frac{7}{16}</math>, and <math>(1, 1)_2 = \frac58</math>. Therefore,<br />
<cmath>(0, 1)_3 = \frac14 \cdot (\frac34 + \frac{7}{16} + 2 \cdot \frac58)</cmath><br />
<cmath>(0, 1)_3 = \frac{39}{64}</cmath><br />
Next, we find <math>(0, 2)_4</math>.<br />
<cmath>(0, 2)_4 = \frac14 \cdot ((0, 1)_3 + (0, 3)_3 + 2(1, 2)_3)</cmath><br />
We already calculated <math>(0, 1)_3</math>, so we just need to find <math>(0, 3)_3</math> and <math>(1, 2)_3</math><br />
<cmath>(0, 3)_3 = \frac14 \cdot ((0, 2)_2 + (0, 4)_2 + 2(1, 3)_2)</cmath><br />
<cmath>(0, 3)_3 = \frac14 \cdot (\frac{7}{16} + 0 + 2 \cdot \frac{1}{4})</cmath><br />
<cmath>(0, 3)_3 = \frac{15}{64}</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot ((1, 3)_2 + (1, 1)_2 + (0, 2)_2 + (2, 2)_2)</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot (\frac14 + \frac58 + \frac{7}{16} + \frac12)</cmath><br />
<cmath>(1, 2)_3 = \frac{29}{64}</cmath><br />
Therefore,<br />
<cmath>(0, 2)_4 = \frac14 \cdot (\frac{39}{64} + \frac{15}{64} + 2 \cdot \frac{29}{64})</cmath><br />
<cmath>(0, 2)_4 = \frac{7}{16}</cmath><br />
Finally, we find <math>(1, 1)_4</math>.<br />
<cmath>(1, 1)_4 = \frac12 \cdot ((0, 1)_3 + (1, 2)_3)</cmath><br />
<cmath>(1, 1)_4 = \frac12 \cdot (\frac{39}{64} + \frac{29}{64})</cmath><br />
<cmath>(1, 1)_4 = \frac{17}{32}</cmath><br />
Putting it all together,<br />
<cmath>(0, 0)_6 = (0, 1)_5 =\frac14 \cdot (\frac{39}{64} + \frac{7}{16} + 2 \cdot \frac{17}{32})</cmath><br />
<cmath>(0, 0)_6 = \frac{135}{256}</cmath><br />
Thus, the answer is <math>135 + 256 = \boxed{391}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2014|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2014_AIME_I_Problems/Problem_11&diff=1078792014 AIME I Problems/Problem 112019-07-24T23:40:14Z<p>Rejas: /* Solution (casework) */</p>
<hr />
<div>== Problem 11 ==<br />
<br />
A token starts at the point <math>(0,0)</math> of an <math>xy</math>-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of <math>|y|=|x|</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
== Solution 1 (Nice) ==<br />
Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. <br />
<br />
However, we overcount exactly one case: ending at <math>(0, 0)</math>. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply <math>\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}</math>. Using PIE, the total probability is <math>\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}</math>, giving an answer of <math>\boxed{391}</math>.<br />
<br />
~sampai7<br />
<br />
<br />
== Solution 2 (Casework) ==<br />
<br />
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is <math>4^6</math>, or <math>4096</math>. There are 4 possible cases that land along the line <math>y = x</math>: <math>x,y = \pm 1; x,y = \pm 2; x,y = \pm 3;</math> or <math>x = y = 0</math>. We will count the number of ways to end up at <math>(1,1), (2,2),</math> and <math>(3,3)</math>, multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at <math>(0,0)</math>.<br />
<br />
*Case 1: The token ends at <math>(3, 3)</math>. In order for the token to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence <math>RRRUUU</math>, which is <math>{6\choose 3} = 20.</math><br />
<br />
*Case 2: The token ends at <math>(2,2)</math>. In order for the token to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences <math>RRRLUU</math> and <math>UUUDRR</math>, both of which are <math>{6\choose 1}{5\choose 2} = 60</math>, for a total of <math>120</math> possibilities.<br />
<br />
*Case 3: The token ends at <math>(1,1)</math>. In order for the token to end up here, it could have had:<br />
**1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RUUUDD</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>URRRLL</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence <math>UUDRRL</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(1,1)</math> is <math>300</math>.<br />
<br />
*Case 4: The token ends at <math>(0,0)</math>. In order for the token to end up here, it could have had:<br />
**3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRRLLL</math> is <math>{6\choose 3} = 20.</math><br />
**3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>UUUDDD</math> is <math>{6\choose 3} = 20.</math><br />
**1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RLUUDD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
**1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRLLUD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(0,0)</math> is <math>400</math>.<br />
<br />
Adding these cases together, we get that the total number of ways to end up on <math>y = x</math> is <math>4(20 + 120 + 300) + 400 = 2160</math>. Thus, our probability is <math>\frac{2160}{4096}</math>. When this fraction is fully reduced, it is <math>\frac{135}{256}</math>, so our answer is <math>135 + 256 = \boxed{391}.</math><br />
<br />
==Solution (casework 2)==<br />
We split this into cases by making a chart. In each row, the entries <math>(\pm1)</math> before the dividing line represent the right or left steps (without regard to order), and the entries after the dividing line represent the up or down steps (again, without regard to order). This table only represents the cases where the ending position <math>(x,y)</math> satisfies <math>x=y</math>.<br />
<cmath><br />
\begin{array}{ccccccccccccl}<br />
\multicolumn{5}{c}{R (+)\qquad L (-)}& |&\multicolumn{5}{c}{U (+)\qquad D (-)}\\<br />
+1&& +1&& +1&| & +1&& +1&& +1\\<br />
+1&& +1&& -1& | & +1&& +1&& -1\\<br />
+1&& -1&& -1& | & +1&& -1&& -1\\<br />
-1 && -1&& -1& | & -1&& -1&& -1\\<br />
\\<br />
+1&& +1&& +1&& -1 &|& +1&& +1\\<br />
+1&& +1&& -1 && -1 &|& +1 && -1\\<br />
+1&& -1&& -1 && -1 &|& -1 && -1 &&(\times 2 \text{ for symmetry by swapping }R-L\text{ and }U-D)\\<br />
\\<br />
+1&& +1 &&+1 &&-1&& -1& |& +1\\<br />
+1&& +1 &&-1&& -1&& -1 &|& -1&& (\times 2\text{ symmetry})\\<br />
\\<br />
+1&& +1 &&+1&& -1&& -1 &&-1&| & (\times2 \text{ symmetry})\\<br />
\end{array}<br />
</cmath><br />
Note that to account for the cases when <math>x=-y</math>, we can simply multiply the <math>U-D</math> steps by <math>-1</math>, so for example, the first row would become <cmath>+1 \qquad+1\qquad +1 \ \ \ \ |\ \ \ -1\qquad -1\qquad -1.</cmath> Therefore, we must multiply the number of possibilities in each case by <math>2</math>, except for when <math>x=y=0</math>.<br />
<br />
Now, we compute the number of possibilities for each case. In particular, we must compute the number of <math>RLUD</math> words, where <math>R</math> represents <math>+1</math> to the left of <math>|</math>, <math>L</math> represents <math>-1</math> to the left of <math>|</math>, <math>U</math> represents <math>+1</math> to the right of <math>|</math>, and <math>D</math> represents <math>-1</math> to the right of <math>|</math>. Using multinomials, we compute the following numbers of possibilities for each case.<br />
<cmath>{6\choose 3}\cdot 2+ \frac{6!}{2!2!}\cdot 2 + \frac{6!}{2!2!} \cdot 2 + {6\choose 3} \cdot 2 = 2(20 + 180 + 180 + 20) = 800</cmath><br />
<cmath>\frac{6!}{3!2!}\cdot 2 + \frac{6!}{2!2!} + \frac{6!}{3!2!}\cdot 2 = 120 + 180 + 120 = 420\ (\times2\text{ for symmetry})</cmath><br />
<cmath>\frac{6!}{3!2!} \cdot 2 + \frac{6!}{3!2!} \cdot 2 = 120 + 120 = 240\ (\times2\text{ for symmetry})</cmath><br />
<cmath>{6\choose 3} = 20\ (\times 2\text{ for symmetry})</cmath><br />
<br />
Thus, there are <math>800 + 840 + 480 + 40 = 2160</math> possibilities where <math>|x|=|y|</math>. Because there are <math>4^6</math> total possibilities, the probability is <math>\frac{2160}{4^6} = \frac{135}{256}</math>, so the answer is <math>\boxed{391}.</math><br />
<br />
==Solution (Nice)==<br />
Yall need to stop bashing<br />
<br />
Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. <br />
<br />
However, we overcount exactly one case: ending at <math>(0, 0)</math>. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply <math>\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}</math>. Using PIE, the total probability is <math>\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}</math>, giving an answer of <math>\boxed{391}</math>.<br />
<br />
Thank,<br />
<br />
~sampai7<br />
<br />
==Solution 4 (States)==<br />
Denote <math>(x, y)_n</math> the probability that starting from point <math>(x, y)</math>, the token reaches a point on the graph of <math>|y| = |x|</math> in exactly <math>n</math> moves. The problem asks us to find <math>(0, 0)_6</math>. We start by breaking this down:<br />
<cmath>(0, 0)_6 = \frac14 \cdot ((0, 1)_5 + (0, -1)_5 + (1, 0)_5 + (-1, 0)_5)</cmath><br />
Notice that by symmetry, <math>(0, 1)_5 = (0, -1)_5 = (1, 0)_5 = (-1, 0)_5</math>, so the equation simplifies to<br />
<cmath>(0, 0)_6 = (0, 1)_5</cmath><br />
We now expand <math>(0, 1)_5</math>.<br />
<cmath>(0, 1)_5 = \frac14 \cdot ((0, 0)_4 + (0, 2)_4 + 2(1, 1)_4)</cmath><br />
First, we find <math>(0, 0)_4</math>.<br />
<cmath>(0, 0)_4 = (0, 1)_3</cmath><br />
<cmath>(0, 1)_3 = \frac14 \cdot ((0, 0)_2 + (0, 2)_2 + 2(1, 1)_2)</cmath><br />
At this point, we can just count the possibilities to find <math>(0, 0)_2 = \frac34</math>, <math>(0, 2)_2 = \frac{7}{16}</math>, and <math>(1, 1)_2 = \frac58</math>. Therefore,<br />
<cmath>(0, 1)_3 = \frac14 \cdot (\frac34 + \frac{7}{16} + 2 \cdot \frac58)</cmath><br />
<cmath>(0, 1)_3 = \frac{39}{64}</cmath><br />
Next, we find <math>(0, 2)_4</math>.<br />
<cmath>(0, 2)_4 = \frac14 \cdot ((0, 1)_3 + (0, 3)_3 + 2(1, 2)_3)</cmath><br />
We already calculated <math>(0, 1)_3</math>, so we just need to find <math>(0, 3)_3</math> and <math>(1, 2)_3</math><br />
<cmath>(0, 3)_3 = \frac14 \cdot ((0, 2)_2 + (0, 4)_2 + 2(1, 3)_2)</cmath><br />
<cmath>(0, 3)_3 = \frac14 \cdot (\frac{7}{16} + 0 + 2 \cdot \frac{1}{4})</cmath><br />
<cmath>(0, 3)_3 = \frac{15}{64}</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot ((1, 3)_2 + (1, 1)_2 + (0, 2)_2 + (2, 2)_2)</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot (\frac14 + \frac58 + \frac{7}{16} + \frac12)</cmath><br />
<cmath>(1, 2)_3 = \frac{29}{64}</cmath><br />
Therefore,<br />
<cmath>(0, 2)_4 = \frac14 \cdot (\frac{39}{64} + \frac{15}{64} + 2 \cdot \frac{29}{64})</cmath><br />
<cmath>(0, 2)_4 = \frac{7}{16}</cmath><br />
Finally, we find <math>(1, 1)_4</math>.<br />
<cmath>(1, 1)_4 = \frac12 \cdot ((0, 1)_3 + (1, 2)_3)</cmath><br />
<cmath>(1, 1)_4 = \frac12 \cdot (\frac{39}{64} + \frac{29}{64})</cmath><br />
<cmath>(1, 1)_4 = \frac{17}{32}</cmath><br />
Putting it all together,<br />
<cmath>(0, 0)_6 = (0, 1)_5 =\frac14 \cdot (\frac{39}{64} + \frac{7}{16} + 2 \cdot \frac{17}{32})</cmath><br />
<cmath>(0, 0)_6 = \frac{135}{256}</cmath><br />
Thus, the answer is <math>135 + 256 = \boxed{391}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2014|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2014_AIME_I_Problems/Problem_11&diff=1078782014 AIME I Problems/Problem 112019-07-24T23:37:45Z<p>Rejas: /* Solution (Nice) */</p>
<hr />
<div>== Problem 11 ==<br />
<br />
A token starts at the point <math>(0,0)</math> of an <math>xy</math>-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of <math>|y|=|x|</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
== Solution (casework) ==<br />
<br />
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is <math>4^6</math>, or <math>4096</math>. There are 4 possible cases that land along the line <math>y = x</math>: <math>x,y = \pm 1; x,y = \pm 2; x,y = \pm 3;</math> or <math>x = y = 0</math>. We will count the number of ways to end up at <math>(1,1), (2,2),</math> and <math>(3,3)</math>, multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at <math>(0,0)</math>.<br />
<br />
*Case 1: The token ends at <math>(3, 3)</math>. In order for the token to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence <math>RRRUUU</math>, which is <math>{6\choose 3} = 20.</math><br />
<br />
*Case 2: The token ends at <math>(2,2)</math>. In order for the token to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences <math>RRRLUU</math> and <math>UUUDRR</math>, both of which are <math>{6\choose 1}{5\choose 2} = 60</math>, for a total of <math>120</math> possibilities.<br />
<br />
*Case 3: The token ends at <math>(1,1)</math>. In order for the token to end up here, it could have had:<br />
**1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RUUUDD</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>URRRLL</math> is <math>{6\choose 1}{5\choose 2} = 60.</math><br />
**2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence <math>UUDRRL</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(1,1)</math> is <math>300</math>.<br />
<br />
*Case 4: The token ends at <math>(0,0)</math>. In order for the token to end up here, it could have had:<br />
**3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRRLLL</math> is <math>{6\choose 3} = 20.</math><br />
**3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>UUUDDD</math> is <math>{6\choose 3} = 20.</math><br />
**1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RLUUDD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
**1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRLLUD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math><br />
Thus, the total number of ways to end up at <math>(0,0)</math> is <math>400</math>.<br />
<br />
Adding these cases together, we get that the total number of ways to end up on <math>y = x</math> is <math>4(20 + 120 + 300) + 400 = 2160</math>. Thus, our probability is <math>\frac{2160}{4096}</math>. When this fraction is fully reduced, it is <math>\frac{135}{256}</math>, so our answer is <math>135 + 256 = \boxed{391}.</math><br />
<br />
==Solution (casework 2)==<br />
We split this into cases by making a chart. In each row, the entries <math>(\pm1)</math> before the dividing line represent the right or left steps (without regard to order), and the entries after the dividing line represent the up or down steps (again, without regard to order). This table only represents the cases where the ending position <math>(x,y)</math> satisfies <math>x=y</math>.<br />
<cmath><br />
\begin{array}{ccccccccccccl}<br />
\multicolumn{5}{c}{R (+)\qquad L (-)}& |&\multicolumn{5}{c}{U (+)\qquad D (-)}\\<br />
+1&& +1&& +1&| & +1&& +1&& +1\\<br />
+1&& +1&& -1& | & +1&& +1&& -1\\<br />
+1&& -1&& -1& | & +1&& -1&& -1\\<br />
-1 && -1&& -1& | & -1&& -1&& -1\\<br />
\\<br />
+1&& +1&& +1&& -1 &|& +1&& +1\\<br />
+1&& +1&& -1 && -1 &|& +1 && -1\\<br />
+1&& -1&& -1 && -1 &|& -1 && -1 &&(\times 2 \text{ for symmetry by swapping }R-L\text{ and }U-D)\\<br />
\\<br />
+1&& +1 &&+1 &&-1&& -1& |& +1\\<br />
+1&& +1 &&-1&& -1&& -1 &|& -1&& (\times 2\text{ symmetry})\\<br />
\\<br />
+1&& +1 &&+1&& -1&& -1 &&-1&| & (\times2 \text{ symmetry})\\<br />
\end{array}<br />
</cmath><br />
Note that to account for the cases when <math>x=-y</math>, we can simply multiply the <math>U-D</math> steps by <math>-1</math>, so for example, the first row would become <cmath>+1 \qquad+1\qquad +1 \ \ \ \ |\ \ \ -1\qquad -1\qquad -1.</cmath> Therefore, we must multiply the number of possibilities in each case by <math>2</math>, except for when <math>x=y=0</math>.<br />
<br />
Now, we compute the number of possibilities for each case. In particular, we must compute the number of <math>RLUD</math> words, where <math>R</math> represents <math>+1</math> to the left of <math>|</math>, <math>L</math> represents <math>-1</math> to the left of <math>|</math>, <math>U</math> represents <math>+1</math> to the right of <math>|</math>, and <math>D</math> represents <math>-1</math> to the right of <math>|</math>. Using multinomials, we compute the following numbers of possibilities for each case.<br />
<cmath>{6\choose 3}\cdot 2+ \frac{6!}{2!2!}\cdot 2 + \frac{6!}{2!2!} \cdot 2 + {6\choose 3} \cdot 2 = 2(20 + 180 + 180 + 20) = 800</cmath><br />
<cmath>\frac{6!}{3!2!}\cdot 2 + \frac{6!}{2!2!} + \frac{6!}{3!2!}\cdot 2 = 120 + 180 + 120 = 420\ (\times2\text{ for symmetry})</cmath><br />
<cmath>\frac{6!}{3!2!} \cdot 2 + \frac{6!}{3!2!} \cdot 2 = 120 + 120 = 240\ (\times2\text{ for symmetry})</cmath><br />
<cmath>{6\choose 3} = 20\ (\times 2\text{ for symmetry})</cmath><br />
<br />
Thus, there are <math>800 + 840 + 480 + 40 = 2160</math> possibilities where <math>|x|=|y|</math>. Because there are <math>4^6</math> total possibilities, the probability is <math>\frac{2160}{4^6} = \frac{135}{256}</math>, so the answer is <math>\boxed{391}.</math><br />
<br />
==Solution (Nice)==<br />
Yall need to stop bashing<br />
<br />
Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. <br />
<br />
However, we overcount exactly one case: ending at <math>(0, 0)</math>. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply <math>\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}</math>. Using PIE, the total probability is <math>\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}</math>, giving an answer of <math>\boxed{391}</math>.<br />
<br />
Thank,<br />
<br />
~sampai7<br />
<br />
==Solution 4 (States)==<br />
Denote <math>(x, y)_n</math> the probability that starting from point <math>(x, y)</math>, the token reaches a point on the graph of <math>|y| = |x|</math> in exactly <math>n</math> moves. The problem asks us to find <math>(0, 0)_6</math>. We start by breaking this down:<br />
<cmath>(0, 0)_6 = \frac14 \cdot ((0, 1)_5 + (0, -1)_5 + (1, 0)_5 + (-1, 0)_5)</cmath><br />
Notice that by symmetry, <math>(0, 1)_5 = (0, -1)_5 = (1, 0)_5 = (-1, 0)_5</math>, so the equation simplifies to<br />
<cmath>(0, 0)_6 = (0, 1)_5</cmath><br />
We now expand <math>(0, 1)_5</math>.<br />
<cmath>(0, 1)_5 = \frac14 \cdot ((0, 0)_4 + (0, 2)_4 + 2(1, 1)_4)</cmath><br />
First, we find <math>(0, 0)_4</math>.<br />
<cmath>(0, 0)_4 = (0, 1)_3</cmath><br />
<cmath>(0, 1)_3 = \frac14 \cdot ((0, 0)_2 + (0, 2)_2 + 2(1, 1)_2)</cmath><br />
At this point, we can just count the possibilities to find <math>(0, 0)_2 = \frac34</math>, <math>(0, 2)_2 = \frac{7}{16}</math>, and <math>(1, 1)_2 = \frac58</math>. Therefore,<br />
<cmath>(0, 1)_3 = \frac14 \cdot (\frac34 + \frac{7}{16} + 2 \cdot \frac58)</cmath><br />
<cmath>(0, 1)_3 = \frac{39}{64}</cmath><br />
Next, we find <math>(0, 2)_4</math>.<br />
<cmath>(0, 2)_4 = \frac14 \cdot ((0, 1)_3 + (0, 3)_3 + 2(1, 2)_3)</cmath><br />
We already calculated <math>(0, 1)_3</math>, so we just need to find <math>(0, 3)_3</math> and <math>(1, 2)_3</math><br />
<cmath>(0, 3)_3 = \frac14 \cdot ((0, 2)_2 + (0, 4)_2 + 2(1, 3)_2)</cmath><br />
<cmath>(0, 3)_3 = \frac14 \cdot (\frac{7}{16} + 0 + 2 \cdot \frac{1}{4})</cmath><br />
<cmath>(0, 3)_3 = \frac{15}{64}</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot ((1, 3)_2 + (1, 1)_2 + (0, 2)_2 + (2, 2)_2)</cmath><br />
<cmath>(1, 2)_3 = \frac14 \cdot (\frac14 + \frac58 + \frac{7}{16} + \frac12)</cmath><br />
<cmath>(1, 2)_3 = \frac{29}{64}</cmath><br />
Therefore,<br />
<cmath>(0, 2)_4 = \frac14 \cdot (\frac{39}{64} + \frac{15}{64} + 2 \cdot \frac{29}{64})</cmath><br />
<cmath>(0, 2)_4 = \frac{7}{16}</cmath><br />
Finally, we find <math>(1, 1)_4</math>.<br />
<cmath>(1, 1)_4 = \frac12 \cdot ((0, 1)_3 + (1, 2)_3)</cmath><br />
<cmath>(1, 1)_4 = \frac12 \cdot (\frac{39}{64} + \frac{29}{64})</cmath><br />
<cmath>(1, 1)_4 = \frac{17}{32}</cmath><br />
Putting it all together,<br />
<cmath>(0, 0)_6 = (0, 1)_5 =\frac14 \cdot (\frac{39}{64} + \frac{7}{16} + 2 \cdot \frac{17}{32})</cmath><br />
<cmath>(0, 0)_6 = \frac{135}{256}</cmath><br />
Thus, the answer is <math>135 + 256 = \boxed{391}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2014|n=I|num-b=10|num-a=12}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10A_Problems/Problem_7&diff=1050562019 AMC 10A Problems/Problem 72019-03-31T01:45:41Z<p>Rejas: /* Solution 10 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10A Problems|2019 AMC 10A #7]] and [[2019 AMC 12A Problems|2019 AMC 12A #5]]}}<br />
<br />
==Problem==<br />
<br />
Two lines with slopes <math>\dfrac{1}{2}</math> and <math>2</math> intersect at <math>(2,2)</math>. What is the area of the triangle enclosed by these two lines and the line <math>x+y=10 ?</math><br />
<br />
<math>\textbf{(A) } 4 \qquad\textbf{(B) } 4\sqrt{2} \qquad\textbf{(C) } 6 \qquad\textbf{(D) } 8 \qquad\textbf{(E) } 6\sqrt{2}</math><br />
<br />
==Solution 1==<br />
Let's first work out the slope-intercept form of all three lines:<br />
<math>(x,y)=(2,2)</math> and <math>y=\frac{x}{2} + b</math> implies <math>2=\frac{2}{2} +b=1+b</math> so <math>b=1</math>, while <math>y=2x + c</math> implies <math>2= 2 \cdot 2+c=4+c</math> so <math>c=-2</math>. Also, <math>x+y=10</math> implies <math>y=-x+10</math>. Thus the lines are <math>y=\frac{x}{2} +1, y=2x-2,</math> and <math>y=-x+10</math>. <br />
Now we find the intersection points between each of the lines with <math>y=-x+10</math>, which are <math>(6,4)</math> and <math>(4,6)</math>. Using the distance formula and then the Pythagorean Theorem, we see that we have an isosceles triangle with base <math>2\sqrt{2}</math> and height <math>3\sqrt{2}</math>, whose area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 2==<br />
Like in Solution 1, we determine the coordinates of the three vertices of the triangle. Now, using the [[Shoelace Theorem]], we can directly find that the area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 3==<br />
Like in the other solutions, solve the systems of equations to see that the triangle's two other vertices are at <math>(4, 6)</math> and <math>(6, 4)</math>. Then apply Heron's Formula: the semi-perimeter will be <math>s = \sqrt{2} + \sqrt{20}</math>, so the area reduces nicely to a difference of squares, making it <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 4==<br />
Like in the other solutions, we find, either using algebra or simply by drawing the lines on squared paper, that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. We can now draw the bounding square with vertices <math>(2, 2)</math>, <math>(2, 6)</math>, <math>(6, 6)</math> and <math>(6, 2)</math>, and deduce that the triangle's area is <math>16-4-2-4=\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 5==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. Using graph paper, we can see that this triangle has <math>6</math> boundary lattice points and <math>4</math> interior lattice points. By Pick's Theorem, the area is <math>\frac62 + 4 - 1 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 6==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. By the Pythagorean Theorem, <math>AB = AC = 2\sqrt5</math> and <math>BC = 2\sqrt2</math>. By the Law of Cosines,<br />
<cmath>\cos A = \frac{(2\sqrt5)^2 + (2\sqrt5)^2 - (2\sqrt2)^2}{2 \cdot 2\sqrt5 \cdot 2\sqrt5} = \frac{20 + 20 - 8}{40} = \frac{32}{40} = \frac45</cmath><br />
Therefore, <math>\sin A = \sqrt{1 - \cos^2 A} = \frac35</math>, so the area is <math>\frac12 bc \sin A = \frac12 \cdot 2\sqrt5 \cdot 2\sqrt5 \cdot \frac35 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 7==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. The area of the triangle is half the absolute value of the determinant of the matrix determined by these points.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
2&2&1\\<br />
4&6&1\\<br />
6&4&1\\<br />
\end{Vmatrix} = \frac12|-12| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
<br />
==Solution 8==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. Then vectors <math>\overrightarrow{AB} = \langle 2, 4 \rangle</math> and <math>\overrightarrow{AC} = \langle 4, 2 \rangle</math>. The area of the triangle is half the magnitude of the cross product of these two vectors.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
i&j&k\\<br />
2&4&0\\<br />
4&2&0\\<br />
\end{Vmatrix} = \frac12|-12k| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==Solution 9==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. By the Pythagorean theorem, this is an isosceles triangle with base <math>2\sqrt2</math> and equal length <math>2\sqrt5</math>. The area of an isosceles triangle with base <math>b</math> and equal length <math>l</math> is <math>\frac{b\sqrt{4l^2-b^2}}{4}</math>. Plugging in <math>b = 2\sqrt2</math> and <math>l = 2\sqrt5</math>,<br />
<cmath>\frac{2\sqrt2 \cdot \sqrt{80-8}}{4} = \frac{\sqrt{576}}{4} = \frac{24}{4} = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==Solution 10==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. By the Pythagorean Theorem, <math>AB = AC = 2\sqrt5</math> and <math>BC = 2\sqrt2</math>. By the Law of Cosines,<br />
<cmath>\cos A = \frac{(2\sqrt5)^2 + (2\sqrt5)^2 - (2\sqrt2)^2}{2 \cdot 2\sqrt5 \cdot 2\sqrt5} = \frac{20 + 20 - 8}{40} = \frac{32}{40} = \frac45</cmath><br />
Therefore, <math>\sin A = \sqrt{1 - \cos^2 A} = \frac35</math>. By the extended Law of Sines,<br />
<cmath>2R = \frac{a}{\sin A} = \frac{2\sqrt2}{\frac35} = \frac{10\sqrt2}{3}</cmath><br />
<cmath>R = \frac{5\sqrt2}{3}</cmath><br />
Then the area is <math>\frac{abc}{4R} = \frac{2\sqrt2 \cdot 2\sqrt5^2}{4 \cdot \frac{5\sqrt2}{3}} = \boxed{\textbf{(C) }6}</math>.<br />
==Solution 11==<br />
The area of a triangle formed by three lines,<br />
<cmath>a_1x + a_2y + a_3 = 0</cmath><br />
<cmath>b_1x + b_2y + b_3 = 0</cmath><br />
<cmath>c_1x + c_2y + c_3 = 0</cmath><br />
is the absolute value of<br />
<cmath>\frac12 \cdot \frac{1}{(b_1c_2-b_2c_1)(a_1c_2-a_2c_1)(a_1b_2-a_2b_1)} \cdot \begin{vmatrix}<br />
a_1&a_2&a_3\\<br />
b_1&b_2&b_3\\<br />
c_1&c_2&c_3\\<br />
\end{vmatrix}^2</cmath><br />
Plugging in the three lines,<br />
<cmath>-x + 2y - 2 = 0</cmath><br />
<cmath>-2x + y + 2 = 0</cmath><br />
<cmath>x + y - 10 = 0</cmath><br />
the area is the absolute value of<br />
<cmath>\frac12 \cdot \frac{1}{(-2-1)(-1-2)(-1+4)} \cdot \begin{vmatrix}<br />
-1&2&-2\\<br />
-2&1&2\\<br />
1&1&-10\\<br />
\end{vmatrix}^2 = \frac12 \cdot \frac{1}{27} \cdot 18^2 = \boxed{\textbf{(C) }6}</cmath><br />
Source: Orrick, Michael L. “THE AREA OF A TRIANGLE FORMED BY THREE LINES.” Pi Mu Epsilon Journal, vol. 7, no. 5, 1981, pp. 294–298. JSTOR, www.jstor.org/stable/24336991.<br />
<br />
==See Also==<br />
<br />
{{AMC10 box|year=2019|ab=A|num-b=6|num-a=8}}<br />
{{AMC12 box|year=2019|ab=A|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10A_Problems/Problem_7&diff=1050262019 AMC 10A Problems/Problem 72019-03-30T03:58:19Z<p>Rejas: /* Solution 10 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10A Problems|2019 AMC 10A #7]] and [[2019 AMC 12A Problems|2019 AMC 12A #5]]}}<br />
<br />
==Problem==<br />
<br />
Two lines with slopes <math>\dfrac{1}{2}</math> and <math>2</math> intersect at <math>(2,2)</math>. What is the area of the triangle enclosed by these two lines and the line <math>x+y=10 ?</math><br />
<br />
<math>\textbf{(A) } 4 \qquad\textbf{(B) } 4\sqrt{2} \qquad\textbf{(C) } 6 \qquad\textbf{(D) } 8 \qquad\textbf{(E) } 6\sqrt{2}</math><br />
<br />
==Solution 1==<br />
Let's first work out the slope-intercept form of all three lines:<br />
<math>(x,y)=(2,2)</math> and <math>y=\frac{x}{2} + b</math> implies <math>2=\frac{2}{2} +b=1+b</math> so <math>b=1</math>, while <math>y=2x + c</math> implies <math>2= 2 \cdot 2+c=4+c</math> so <math>c=-2</math>. Also, <math>x+y=10</math> implies <math>y=-x+10</math>. Thus the lines are <math>y=\frac{x}{2} +1, y=2x-2,</math> and <math>y=-x+10</math>. <br />
Now we find the intersection points between each of the lines with <math>y=-x+10</math>, which are <math>(6,4)</math> and <math>(4,6)</math>. Using the distance formula and then the Pythagorean Theorem, we see that we have an isosceles triangle with base <math>2\sqrt{2}</math> and height <math>3\sqrt{2}</math>, whose area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 2==<br />
Like in Solution 1, we determine the coordinates of the three vertices of the triangle. Now, using the [[Shoelace Theorem]], we can directly find that the area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 3==<br />
Like in the other solutions, solve the systems of equations to see that the triangle's two other vertices are at <math>(4, 6)</math> and <math>(6, 4)</math>. Then apply Heron's Formula: the semi-perimeter will be <math>s = \sqrt{2} + \sqrt{20}</math>, so the area reduces nicely to a difference of squares, making it <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 4==<br />
Like in the other solutions, we find, either using algebra or simply by drawing the lines on squared paper, that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. We can now draw the bounding square with vertices <math>(2, 2)</math>, <math>(2, 6)</math>, <math>(6, 6)</math> and <math>(6, 2)</math>, and deduce that the triangle's area is <math>16-4-2-4=\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 5==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. Using graph paper, we can see that this triangle has <math>6</math> boundary lattice points and <math>4</math> interior lattice points. By Pick's Theorem, the area is <math>\frac62 + 4 - 1 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 6==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. By the Pythagorean Theorem, <math>AB = AC = 2\sqrt5</math> and <math>BC = 2\sqrt2</math>. By the Law of Cosines,<br />
<cmath>\cos A = \frac{(2\sqrt5)^2 + (2\sqrt5)^2 - (2\sqrt2)^2}{2 \cdot 2\sqrt5 \cdot 2\sqrt5} = \frac{20 + 20 - 8}{40} = \frac{32}{40} = \frac45</cmath><br />
Therefore, <math>\sin A = \sqrt{1 - \cos^2 A} = \frac35</math>, so the area is <math>\frac12 bc \sin A = \frac12 \cdot 2\sqrt5 \cdot 2\sqrt5 \cdot \frac35 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 7==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. The area of the triangle is half the absolute value of the determinant of the matrix determined by these points.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
2&2&1\\<br />
4&6&1\\<br />
6&4&1\\<br />
\end{Vmatrix} = \frac12|-12| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
<br />
==Solution 8==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. Then vectors <math>\overrightarrow{AB} = \langle 2, 4 \rangle</math> and <math>\overrightarrow{AC} = \langle 4, 2 \rangle</math>. The area of the triangle is half the magnitude of the cross product of these two vectors.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
i&j&k\\<br />
2&4&0\\<br />
4&2&0\\<br />
\end{Vmatrix} = \frac12|-12k| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==Solution 9==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. By the Pythagorean theorem, this is an isosceles triangle with base <math>2\sqrt2</math> and equal length <math>2\sqrt5</math>. The area of an isosceles triangle with base <math>b</math> and equal length <math>l</math> is <math>\frac{b\sqrt{4l^2-b^2}}{4}</math>. Plugging in <math>b = 2\sqrt2</math> and <math>l = 2\sqrt5</math>,<br />
<cmath>\frac{2\sqrt2 \cdot \sqrt{80-8}}{4} = \frac{\sqrt{576}}{4} = \frac{24}{4} = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==Solution 10==<br />
The area of a triangle formed by three lines,<br />
<cmath>a_1x + a_2y + a_3 = 0</cmath><br />
<cmath>b_1x + b_2y + b_3 = 0</cmath><br />
<cmath>c_1x + c_2y + c_3 = 0</cmath><br />
is the absolute value of<br />
<cmath>\frac12 \cdot \frac{1}{(b_1c_2-b_2c_1)(a_1c_2-a_2c_1)(a_1b_2-a_2b_1)} \cdot \begin{vmatrix}<br />
a_1&a_2&a_3\\<br />
b_1&b_2&b_3\\<br />
c_1&c_2&c_3\\<br />
\end{vmatrix}^2</cmath><br />
Plugging in the three lines,<br />
<cmath>-x + 2y - 2 = 0</cmath><br />
<cmath>-2x + y + 2 = 0</cmath><br />
<cmath>x + y - 10 = 0</cmath><br />
the area is the absolute value of<br />
<cmath>\frac12 \cdot \frac{1}{(-2-1)(-1-2)(-1+4)} \cdot \begin{vmatrix}<br />
-1&2&-2\\<br />
-2&1&2\\<br />
1&1&-10\\<br />
\end{vmatrix}^2 = \frac12 \cdot \frac{1}{27} \cdot 18^2 = \boxed{\textbf{(C) }6}</cmath><br />
Source: Orrick, Michael L. “THE AREA OF A TRIANGLE FORMED BY THREE LINES.” Pi Mu Epsilon Journal, vol. 7, no. 5, 1981, pp. 294–298. JSTOR, www.jstor.org/stable/24336991.<br />
<br />
==See Also==<br />
<br />
{{AMC10 box|year=2019|ab=A|num-b=6|num-a=8}}<br />
{{AMC12 box|year=2019|ab=A|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10A_Problems/Problem_7&diff=1050252019 AMC 10A Problems/Problem 72019-03-30T03:53:31Z<p>Rejas: /* Solution 9 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10A Problems|2019 AMC 10A #7]] and [[2019 AMC 12A Problems|2019 AMC 12A #5]]}}<br />
<br />
==Problem==<br />
<br />
Two lines with slopes <math>\dfrac{1}{2}</math> and <math>2</math> intersect at <math>(2,2)</math>. What is the area of the triangle enclosed by these two lines and the line <math>x+y=10 ?</math><br />
<br />
<math>\textbf{(A) } 4 \qquad\textbf{(B) } 4\sqrt{2} \qquad\textbf{(C) } 6 \qquad\textbf{(D) } 8 \qquad\textbf{(E) } 6\sqrt{2}</math><br />
<br />
==Solution 1==<br />
Let's first work out the slope-intercept form of all three lines:<br />
<math>(x,y)=(2,2)</math> and <math>y=\frac{x}{2} + b</math> implies <math>2=\frac{2}{2} +b=1+b</math> so <math>b=1</math>, while <math>y=2x + c</math> implies <math>2= 2 \cdot 2+c=4+c</math> so <math>c=-2</math>. Also, <math>x+y=10</math> implies <math>y=-x+10</math>. Thus the lines are <math>y=\frac{x}{2} +1, y=2x-2,</math> and <math>y=-x+10</math>. <br />
Now we find the intersection points between each of the lines with <math>y=-x+10</math>, which are <math>(6,4)</math> and <math>(4,6)</math>. Using the distance formula and then the Pythagorean Theorem, we see that we have an isosceles triangle with base <math>2\sqrt{2}</math> and height <math>3\sqrt{2}</math>, whose area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 2==<br />
Like in Solution 1, we determine the coordinates of the three vertices of the triangle. Now, using the [[Shoelace Theorem]], we can directly find that the area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 3==<br />
Like in the other solutions, solve the systems of equations to see that the triangle's two other vertices are at <math>(4, 6)</math> and <math>(6, 4)</math>. Then apply Heron's Formula: the semi-perimeter will be <math>s = \sqrt{2} + \sqrt{20}</math>, so the area reduces nicely to a difference of squares, making it <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 4==<br />
Like in the other solutions, we find, either using algebra or simply by drawing the lines on squared paper, that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. We can now draw the bounding square with vertices <math>(2, 2)</math>, <math>(2, 6)</math>, <math>(6, 6)</math> and <math>(6, 2)</math>, and deduce that the triangle's area is <math>16-4-2-4=\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 5==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. Using graph paper, we can see that this triangle has <math>6</math> boundary lattice points and <math>4</math> interior lattice points. By Pick's Theorem, the area is <math>\frac62 + 4 - 1 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 6==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. By the Pythagorean Theorem, <math>AB = AC = 2\sqrt5</math> and <math>BC = 2\sqrt2</math>. By the Law of Cosines,<br />
<cmath>\cos A = \frac{(2\sqrt5)^2 + (2\sqrt5)^2 - (2\sqrt2)^2}{2 \cdot 2\sqrt5 \cdot 2\sqrt5} = \frac{20 + 20 - 8}{40} = \frac{32}{40} = \frac45</cmath><br />
Therefore, <math>\sin A = \sqrt{1 - \cos^2 A} = \frac35</math>, so the area is <math>\frac12 bc \sin A = \frac12 \cdot 2\sqrt5 \cdot 2\sqrt5 \cdot \frac35 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 7==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. The area of the triangle is half the absolute value of the determinant of the matrix determined by these points.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
2&2&1\\<br />
4&6&1\\<br />
6&4&1\\<br />
\end{Vmatrix} = \frac12|-12| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
<br />
==Solution 8==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. Then vectors <math>\overrightarrow{AB} = \langle 2, 4 \rangle</math> and <math>\overrightarrow{AC} = \langle 4, 2 \rangle</math>. The area of the triangle is half the magnitude of the cross product of these two vectors.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
i&j&k\\<br />
2&4&0\\<br />
4&2&0\\<br />
\end{Vmatrix} = \frac12|-12k| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==Solution 9==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. By the Pythagorean theorem, this is an isosceles triangle with base <math>2\sqrt2</math> and equal length <math>2\sqrt5</math>. The area of an isosceles triangle with base <math>b</math> and equal length <math>l</math> is <math>\frac{b\sqrt{4l^2-b^2}}{4}</math>. Plugging in <math>b = 2\sqrt2</math> and <math>l = 2\sqrt5</math>,<br />
<cmath>\frac{2\sqrt2 \cdot \sqrt{80-8}}{4} = \frac{\sqrt{576}}{4} = \frac{24}{4} = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==Solution 10==<br />
The area of a triangle formed by three lines,<br />
<cmath>a_1x + a_2y + a_3 = 0</cmath><br />
<cmath>b_1x + b_2y + b_3 = 0</cmath><br />
<cmath>c_1x + c_2y + c_3 = 0</cmath><br />
is the absolute value of<br />
<cmath>\frac12 \cdot \frac{1}{(b_1c_2-b_2c_1)(a_1c_2-a_2c_1)(a_1b_2-a_2b_1)} \cdot \begin{vmatrix}<br />
a_1&a_2&a_3\\<br />
b_1&b_2&b_3\\<br />
c_1&c_2&c_3\\<br />
\end{vmatrix}^2</cmath><br />
Plugging in the three lines,<br />
<cmath>-x + 2y - 2 = 0</cmath><br />
<cmath>-2x + y + 2 = 0</cmath><br />
<cmath>x + y - 10 = 0</cmath><br />
the area is the absolute value of<br />
<cmath>\frac12 \cdot \frac{1}{(-2-1)(-1-2)(-1+4)} \cdot \begin{vmatrix}<br />
-1&2&-2\\<br />
-2&1&2\\<br />
1&1&-10\\<br />
\end{vmatrix}^2 = \frac12 \cdot \frac{1}{27} \cdot 324 = \boxed{\textbf{(C) }6}</cmath><br />
Source: Orrick, Michael L. “THE AREA OF A TRIANGLE FORMED BY THREE LINES.” Pi Mu Epsilon Journal, vol. 7, no. 5, 1981, pp. 294–298. JSTOR, www.jstor.org/stable/24336991.<br />
<br />
==See Also==<br />
<br />
{{AMC10 box|year=2019|ab=A|num-b=6|num-a=8}}<br />
{{AMC12 box|year=2019|ab=A|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10A_Problems/Problem_7&diff=1050242019 AMC 10A Problems/Problem 72019-03-30T03:18:07Z<p>Rejas: /* Solution 8 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10A Problems|2019 AMC 10A #7]] and [[2019 AMC 12A Problems|2019 AMC 12A #5]]}}<br />
<br />
==Problem==<br />
<br />
Two lines with slopes <math>\dfrac{1}{2}</math> and <math>2</math> intersect at <math>(2,2)</math>. What is the area of the triangle enclosed by these two lines and the line <math>x+y=10 ?</math><br />
<br />
<math>\textbf{(A) } 4 \qquad\textbf{(B) } 4\sqrt{2} \qquad\textbf{(C) } 6 \qquad\textbf{(D) } 8 \qquad\textbf{(E) } 6\sqrt{2}</math><br />
<br />
==Solution 1==<br />
Let's first work out the slope-intercept form of all three lines:<br />
<math>(x,y)=(2,2)</math> and <math>y=\frac{x}{2} + b</math> implies <math>2=\frac{2}{2} +b=1+b</math> so <math>b=1</math>, while <math>y=2x + c</math> implies <math>2= 2 \cdot 2+c=4+c</math> so <math>c=-2</math>. Also, <math>x+y=10</math> implies <math>y=-x+10</math>. Thus the lines are <math>y=\frac{x}{2} +1, y=2x-2,</math> and <math>y=-x+10</math>. <br />
Now we find the intersection points between each of the lines with <math>y=-x+10</math>, which are <math>(6,4)</math> and <math>(4,6)</math>. Using the distance formula and then the Pythagorean Theorem, we see that we have an isosceles triangle with base <math>2\sqrt{2}</math> and height <math>3\sqrt{2}</math>, whose area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 2==<br />
Like in Solution 1, we determine the coordinates of the three vertices of the triangle. Now, using the [[Shoelace Theorem]], we can directly find that the area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 3==<br />
Like in the other solutions, solve the systems of equations to see that the triangle's two other vertices are at <math>(4, 6)</math> and <math>(6, 4)</math>. Then apply Heron's Formula: the semi-perimeter will be <math>s = \sqrt{2} + \sqrt{20}</math>, so the area reduces nicely to a difference of squares, making it <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 4==<br />
Like in the other solutions, we find, either using algebra or simply by drawing the lines on squared paper, that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. We can now draw the bounding square with vertices <math>(2, 2)</math>, <math>(2, 6)</math>, <math>(6, 6)</math> and <math>(6, 2)</math>, and deduce that the triangle's area is <math>16-4-2-4=\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 5==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. Using graph paper, we can see that this triangle has <math>6</math> boundary lattice points and <math>4</math> interior lattice points. By Pick's Theorem, the area is <math>\frac62 + 4 - 1 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 6==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. By the Pythagorean Theorem, <math>AB = AC = 2\sqrt5</math> and <math>BC = 2\sqrt2</math>. By the Law of Cosines,<br />
<cmath>\cos A = \frac{(2\sqrt5)^2 + (2\sqrt5)^2 - (2\sqrt2)^2}{2 \cdot 2\sqrt5 \cdot 2\sqrt5} = \frac{20 + 20 - 8}{40} = \frac{32}{40} = \frac45</cmath><br />
Therefore, <math>\sin A = \sqrt{1 - \cos^2 A} = \frac35</math>, so the area is <math>\frac12 bc \sin A = \frac12 \cdot 2\sqrt5 \cdot 2\sqrt5 \cdot \frac35 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 7==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. The area of the triangle is half the absolute value of the determinant of the matrix determined by these points.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
2&2&1\\<br />
4&6&1\\<br />
6&4&1\\<br />
\end{Vmatrix} = \frac12|-12| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
<br />
==Solution 8==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. Then vectors <math>\overrightarrow{AB} = \langle 2, 4 \rangle</math> and <math>\overrightarrow{AC} = \langle 4, 2 \rangle</math>. The area of the triangle is half the magnitude of the cross product of these two vectors.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
i&j&k\\<br />
2&4&0\\<br />
4&2&0\\<br />
\end{Vmatrix} = \frac12|-12k| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==Solution 9==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. By the Pythagorean theorem, this is an isosceles triangle with base <math>2\sqrt2</math> and equal length <math>2\sqrt5</math>. The area of an isosceles triangle with base <math>b</math> and equal length <math>l</math> is <math>\frac{b\sqrt{4l^2-b^2}}{4}</math>. Plugging in <math>b = 2\sqrt2</math> and <math>l = 2\sqrt5</math>,<br />
<cmath>\frac{2\sqrt2 \cdot \sqrt{80-8}}{4} = \frac{\sqrt{576}}{4} = \frac{24}{4} = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==See Also==<br />
<br />
{{AMC10 box|year=2019|ab=A|num-b=6|num-a=8}}<br />
{{AMC12 box|year=2019|ab=A|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10A_Problems/Problem_7&diff=1050232019 AMC 10A Problems/Problem 72019-03-30T03:04:57Z<p>Rejas: /* Solution 4 */</p>
<hr />
<div>{{duplicate|[[2019 AMC 10A Problems|2019 AMC 10A #7]] and [[2019 AMC 12A Problems|2019 AMC 12A #5]]}}<br />
<br />
==Problem==<br />
<br />
Two lines with slopes <math>\dfrac{1}{2}</math> and <math>2</math> intersect at <math>(2,2)</math>. What is the area of the triangle enclosed by these two lines and the line <math>x+y=10 ?</math><br />
<br />
<math>\textbf{(A) } 4 \qquad\textbf{(B) } 4\sqrt{2} \qquad\textbf{(C) } 6 \qquad\textbf{(D) } 8 \qquad\textbf{(E) } 6\sqrt{2}</math><br />
<br />
==Solution 1==<br />
Let's first work out the slope-intercept form of all three lines:<br />
<math>(x,y)=(2,2)</math> and <math>y=\frac{x}{2} + b</math> implies <math>2=\frac{2}{2} +b=1+b</math> so <math>b=1</math>, while <math>y=2x + c</math> implies <math>2= 2 \cdot 2+c=4+c</math> so <math>c=-2</math>. Also, <math>x+y=10</math> implies <math>y=-x+10</math>. Thus the lines are <math>y=\frac{x}{2} +1, y=2x-2,</math> and <math>y=-x+10</math>. <br />
Now we find the intersection points between each of the lines with <math>y=-x+10</math>, which are <math>(6,4)</math> and <math>(4,6)</math>. Using the distance formula and then the Pythagorean Theorem, we see that we have an isosceles triangle with base <math>2\sqrt{2}</math> and height <math>3\sqrt{2}</math>, whose area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 2==<br />
Like in Solution 1, we determine the coordinates of the three vertices of the triangle. Now, using the [[Shoelace Theorem]], we can directly find that the area is <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 3==<br />
Like in the other solutions, solve the systems of equations to see that the triangle's two other vertices are at <math>(4, 6)</math> and <math>(6, 4)</math>. Then apply Heron's Formula: the semi-perimeter will be <math>s = \sqrt{2} + \sqrt{20}</math>, so the area reduces nicely to a difference of squares, making it <math>\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 4==<br />
Like in the other solutions, we find, either using algebra or simply by drawing the lines on squared paper, that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. We can now draw the bounding square with vertices <math>(2, 2)</math>, <math>(2, 6)</math>, <math>(6, 6)</math> and <math>(6, 2)</math>, and deduce that the triangle's area is <math>16-4-2-4=\boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 5==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. Using graph paper, we can see that this triangle has <math>6</math> boundary lattice points and <math>4</math> interior lattice points. By Pick's Theorem, the area is <math>\frac62 + 4 - 1 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 6==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. By the Pythagorean Theorem, <math>AB = AC = 2\sqrt5</math> and <math>BC = 2\sqrt2</math>. By the Law of Cosines,<br />
<cmath>\cos A = \frac{(2\sqrt5)^2 + (2\sqrt5)^2 - (2\sqrt2)^2}{2 \cdot 2\sqrt5 \cdot 2\sqrt5} = \frac{20 + 20 - 8}{40} = \frac{32}{40} = \frac45</cmath><br />
Therefore, <math>\sin A = \sqrt{1 - \cos^2 A} = \frac35</math>, so the area is <math>\frac12 bc \sin A = \frac12 \cdot 2\sqrt5 \cdot 2\sqrt5 \cdot \frac35 = \boxed{\textbf{(C) }6}</math>.<br />
<br />
==Solution 7==<br />
Like in other solutions, we find that the three points of intersection are <math>(2, 2)</math>, <math>(4, 6)</math>, and <math>(6, 4)</math>. The area of the triangle is half the absolute value of the determinant of the matrix determined by these points.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
2&2&1\\<br />
4&6&1\\<br />
6&4&1\\<br />
\end{Vmatrix} = \frac12|-12| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
<br />
==Solution 8==<br />
Like in other solutions, we find the three points of intersection. Label these <math>A (2, 2)</math>, <math>B (4, 6)</math>, and <math>C (6, 4)</math>. Then vectors <math>\overrightarrow{AB} = \langle 2, 4 \rangle</math> and <math>\overrightarrow{AC} = \langle 4, 2 \rangle</math>. The area of the triangle is half the magnitude of the cross product of these two vectors.<br />
<cmath><br />
\frac12\begin{Vmatrix}<br />
i&j&k\\<br />
2&4&0\\<br />
4&2&0\\<br />
\end{Vmatrix} = \frac12|-12k| = \frac12 \cdot 12 = \boxed{\textbf{(C) }6}</cmath><br />
<br />
==See Also==<br />
<br />
{{AMC10 box|year=2019|ab=A|num-b=6|num-a=8}}<br />
{{AMC12 box|year=2019|ab=A|num-b=4|num-a=6}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_14&diff=1048062019 AIME II Problems/Problem 142019-03-22T23:31:05Z<p>Rejas: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the sum of all positive integers <math>n</math> such that, given an unlimited supply of stamps of denominations <math>5,n,</math> and <math>n+1</math> cents, <math>91</math> cents is the greatest postage that cannot be formed.<br />
<br />
==Solution==<br />
By the Chicken McNugget theorem, the least possible value of <math>n</math> such that <math>91</math> cents cannot be formed satisfies <math>5n - 5 - n = 91</math>, so <math>n = 24</math>. For values of <math>n</math> greater than <math>24</math>, notice that if <math>91</math> cents cannot be formed, then any number <math>1 \bmod 5</math> less than <math>91</math> also cannot be formed. The proof of this is that if any number <math>1 \bmod 5</math> less than <math>91</math> can be formed, then we could keep adding <math>5</math> cent stamps until we reach <math>91</math> cents. However, since <math>91</math> cents is the greatest postage that cannot be formed, <math>96</math> cents is the first number that is <math>1 \bmod 5</math> that can be formed, so it must be formed without any <math>5</math> cent stamps. There are few <math>(n, n + 1)</math> pairs, where <math>n \geq 24</math>, that can make <math>96</math> cents. These are cases where one of <math>n</math> and <math>n + 1</math> is a factor of <math>96</math>, which are <math>(24, 25), (31, 32), (32, 33), (47, 48), (48, 49), (95, 96)</math>, and <math>(96, 97)</math>. The last two obviously do not work since <math>92</math> through <math>94</math> cents also cannot be formed, and by a little testing, only <math>(24, 25)</math> and <math>(47, 48)</math> satisfy the condition that <math>91</math> cents is the greatest postage that cannot be formed, so <math>n = 24, 47</math>. <math>24 + 47 = \boxed{071}</math>.<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=13|num-a=15}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_14&diff=1048052019 AIME II Problems/Problem 142019-03-22T23:28:58Z<p>Rejas: /* Solution */</p>
<hr />
<div>==Problem==<br />
Find the sum of all positive integers <math>n</math> such that, given an unlimited supply of stamps of denominations <math>5,n,</math> and <math>n+1</math> cents, <math>91</math> cents is the greatest postage that cannot be formed.<br />
<br />
==Solution==<br />
By the Chicken McNugget theorem, the least possible value of <math>n</math> such that <math>91</math> cents cannot be formed satisfies <math>5n - 5 - n = 91</math>, so <math>n = 24</math>. For values of <math>n</math> greater than <math>24</math>, notice that if <math>91</math> cents cannot be formed, then any number <math>1 \mod 5</math> less than <math>91</math> also cannot be formed. The proof of this is that if any number <math>1 \mod 5</math> less than <math>91</math> can be formed, then we could keep adding <math>5</math> cent stamps until we reach <math>91</math> cents. However, since <math>91</math> cents is the greatest postage that cannot be formed, <math>96</math> cents is the first number that is <math>1 \mod 5</math> that can be formed, so it must be formed without any <math>5</math> cent stamps. There are few <math>(n, n + 1)</math> pairs, where <math>n \geq 24</math>, that can make <math>96</math> cents. These are cases where one of <math>n</math> and <math>n + 1</math> is a factor of <math>96</math>, which are <math>(24, 25), (31, 32), (32, 33), (47, 48), (48, 49), (95, 96)</math>, and <math>(96, 97)</math>. The last two obviously do not work since <math>92</math> through <math>94</math> cents also cannot be formed, and by a little testing, only <math>(24, 25)</math> and <math>(47, 48)</math> satisfy the condition that <math>91</math> cents is the greatest postage that cannot be formed, so <math>n = 24, 47</math>. <math>24 + 47 = \boxed{071}</math>.<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=13|num-a=15}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_8&diff=1048042019 AIME II Problems/Problem 82019-03-22T23:01:40Z<p>Rejas: /* Solution */</p>
<hr />
<div>==Problem 8==<br />
The polynomial <math>f(z)=az^{2018}+bz^{2017}+cz^{2016}</math> has real coefficients not exceeding <math>2019</math>, and <math>f\left(\tfrac{1+\sqrt{3}i}{2}\right)=2015+2019\sqrt{3}i</math>. Find the remainder when <math>f(1)</math> is divided by <math>1000</math>.<br />
<br />
==Solution==<br />
We have <math>\frac{1+\sqrt{3}i}{2} = \omega</math> where <math>\omega = e^{\frac{i\pi}{3}}</math> is a primitive 6th root of unity. Then we have<br />
<br />
<cmath>\begin{align*}<br />
f(\omega) &= a\omega^{2018} + b\omega^{2017} + c\omega^{2016}\\<br />
&= a\omega^2 + b\omega + c<br />
\end{align*}</cmath><br />
<br />
We wish to find <math>f(1) = a+b+c</math>. We first look at the real parts. As <math>\text{Re}(\omega^2) = -\frac{1}{2}</math> and <math>\text{Re}(\omega) = \frac{1}{2}</math>, we have <math>-\frac{1}{2}a + \frac{1}{2}b + c = 2015 \implies -a+b + 2c = 4030</math>. Looking at imaginary parts, we have <math>\text{Im}(\omega^2) = \text{Im}(\omega) = \frac{\sqrt{3}}{2}</math>, so <math>\frac{\sqrt{3}}{2}(a+b) = 2019\sqrt{3} \implies a+b = 4038</math>. As <math>a</math> and <math>b</math> do not exceed 2019, we must have <math>a = 2019</math> and <math>b = 2019</math>. Then <math>c = \frac{4030}{2} = 2015</math>, so <math>f(1) = 4038 + 2015 = 6053 \implies f(1) \pmod{1000} = \boxed{053}</math>.<br />
<br />
-scrabbler94<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=7|num-a=9}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_8&diff=1048032019 AIME II Problems/Problem 82019-03-22T23:00:37Z<p>Rejas: /* Solution */</p>
<hr />
<div>==Problem 8==<br />
The polynomial <math>f(z)=az^{2018}+bz^{2017}+cz^{2016}</math> has real coefficients not exceeding <math>2019</math>, and <math>f\left(\tfrac{1+\sqrt{3}i}{2}\right)=2015+2019\sqrt{3}i</math>. Find the remainder when <math>f(1)</math> is divided by <math>1000</math>.<br />
<br />
==Solution==<br />
We have <math>\frac{1+\sqrt{3}i}{2} = \omega</math> where <math>\omega = e^{\frac{i\pi}{3}}</math> is a primitive 6th root of unity. Then we have<br />
<br />
<cmath>\begin{align*}<br />
f(\omega) &= a\omega^{2018} + b\omega^{2017} + c\omega^{2016}\\<br />
&= a\omega^2 + b\omega + c<br />
\end{align*}</cmath><br />
<br />
We wish to find <math>f(1) = a+b+c</math>. We first look at the real parts. As <math>\text{Re}(\omega^2) = -\frac{1}{2}</math> and <math>\text{Re}(\omega) = \frac{1}{2}</math>, we have <math>-\frac{1}{2}a + \frac{1}{2}b + c = 2015 \implies -a+b + 2c = 4030</math>. Looking at imaginary parts, we have <math>\text{Im}(\omega^2) = \text{Im}(\omega) = \frac{\sqrt{3}}{2}</math>, so <math>\frac{\sqrt{3}}{2}(a+b) = 2019\sqrt{3} \implies a+b = 4038</math>. As <math>a</math> and <math>b</math> do not exceed 2019, we must have <math>a+b = 2019</math>. Then <math>c = \frac{4030}{2} = 2015</math>, so <math>f(1) = 4038 + 2015 = 6053 \implies f(1) \pmod{1000} = \boxed{053}</math>.<br />
<br />
-scrabbler94<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=7|num-a=9}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_2&diff=1048022019 AIME II Problems/Problem 22019-03-22T22:50:52Z<p>Rejas: /* Solution */</p>
<hr />
<div>==Problem 2==<br />
<br />
Lily pads <math>1,2,3,\ldots</math> lie in a row on a pond. A frog makes a sequence of jumps starting on pad <math>1</math>. From any pad <math>k</math> the frog jumps to either pad <math>k+1</math> or pad <math>k+2</math> chosen randomly with probability <math>\tfrac{1}{2}</math> and independently of other jumps. The probability that the frog visits pad <math>7</math> is <math>\tfrac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
==Solution==<br />
Let <math>P_n</math> be the probability the frog visits pad <math>7</math> starting from pad <math>n</math>. Then <math>P_7 = 1</math>, <math>P_6 = \frac12</math>, and <math>P_n = \frac12(P_{n + 1} + P_{n + 2})</math> for all integers <math>1 \leq n \leq 5</math>. Working our way down, we find<br />
<cmath>P_5 = \frac{3}{4}</cmath><br />
<cmath>P_4 = \frac{5}{8}</cmath><br />
<cmath>P_3 = \frac{11}{16}</cmath><br />
<cmath>P_2 = \frac{21}{32}</cmath><br />
<cmath>P_1 = \frac{43}{64}</cmath><br />
<math>43 + 64 = \boxed{107}</math>.<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=1|num-a=3}}<br />
{{MAA Notice}}</div>Rejashttps://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_10&diff=1048012019 AIME II Problems/Problem 102019-03-22T22:41:15Z<p>Rejas: /* Solution */</p>
<hr />
<div>==Problem 10==<br />
There is a unique angle <math>\theta</math> between <math>0^{\circ}</math> and <math>90^{\circ}</math> such that for nonnegative integers <math>n</math>, the value of <math>\tan{\left(2^{n}\theta\right)}</math> is positive when <math>n</math> is a multiple of <math>3</math>, and negative otherwise. The degree measure of <math>\theta</math> is <math>\tfrac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime integers. Find <math>p+q</math>.<br />
<br />
==Solution==<br />
Note that if <math>\tan \theta</math> is positive, then <math>\theta</math> is in the first or third quadrant, so <math>0^{\circ} < \theta < 90^{\circ} \pmod{180^{\circ}}</math>. Also notice that the only way <math>\tan{\left(2^{n}\theta\right)}</math> can be positive for all <math>n</math> that are multiples of <math>3</math> is when <math>2^0\theta, 2^3\theta, 2^6\theta</math>, etc. are all the same value <math>\pmod{180^{\circ}}</math>. This happens if <math>8\theta = \theta \pmod{180^{\circ}}</math>, so <math>7\theta = 0^{\circ} \pmod{180^{\circ}}</math>. Therefore, the only possible values of theta between <math>0^{\circ}</math> and <math>90^{\circ}</math> are <math>\frac{180}{7}^{\circ}</math>, <math>\frac{360}{7}^{\circ}</math>, and <math>\frac{540}{7}^{\circ}</math>. However <math>\frac{180}{7}^{\circ}</math> does not work since <math>\tan{2 \cdot \frac{180}{7}^{\circ}}</math> is positive, and <math>\frac{360}{7}^{\circ}</math> does not work because <math>\tan{4 \cdot \frac{360}{7}^{\circ}}</math> is positive. Thus, <math>\theta = \frac{540}{7}^{\circ}</math>. <math>540 + 7 = \boxed{547}</math>.<br />
<br />
==See Also==<br />
{{AIME box|year=2019|n=II|num-b=9|num-a=11}}<br />
{{MAA Notice}}</div>Rejas