https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Bobafett101&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T12:49:31ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2014_USAMO_Problems/Problem_1&diff=852492014 USAMO Problems/Problem 12017-04-16T20:06:02Z<p>Bobafett101: /* Solution */</p>
<hr />
<div>==Problem==<br />
Let <math>a,b,c,d</math> be real numbers such that <math>b-d \ge 5</math> and all zeros <math>x_1, x_2, x_3,</math> and <math>x_4</math> of the polynomial <math>P(x)=x^4+ax^3+bx^2+cx+d</math> are real. Find the smallest value the product <math>(x_1^2+1)(x_2^2+1)(x_3^2+1)(x_4^2+1)</math> can take.<br />
<br />
==Hint==<br />
Factor <math>x^2 + 1</math> as the product of two linear binomials.<br />
<br />
==Solution==<br />
Using the hint we turn the equation into <math>\prod_{k=1} ^4 (x_k-i)(x_k+i) \implies P(i)P(-i) \implies ((b-d-1)-i(a-c))^2 \implies \boxed{16}</math>. This minimum is achieved when all the <math>x_i</math> are equal to <math>1</math>.</div>Bobafett101https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_1&diff=801901975 USAMO Problems/Problem 12016-09-03T22:07:27Z<p>Bobafett101: /* Proof of Key Lemma */</p>
<hr />
<div>==Problem==<br />
(a) Prove that<br />
<center><math>[5x]+[5y]\ge [3x+y]+[3y+x]</math>,</center><br />
where <math>x,y\ge 0</math> and <math>[u]</math> denotes the greatest integer <math>\le u</math> (e.g., <math>[\sqrt{2}]=1</math>).<br />
<br />
(b) Using (a) or otherwise, prove that<br />
<center><math>\frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}</math></center><br />
is integral for all positive integral <math>m</math> and <math>n</math>.<br />
<br />
<br />
==Background Knowledge==<br />
''Note: A complete proof for this problem may require these results, and preferably also their proofs.''<br />
<br />
If <math>[x] = a</math>, then <math>a \le x < a + 1</math>. This is the alternate definition of <math>[x]</math>.<br />
<br />
If <math>a < b</math>, then <math>[a] \le [b]</math>. This is easily proved by contradiction or consideration of the contrapositive.<br />
<br />
If <math>a</math> is an integer, then <math>[x + a] = [x] + a</math>. This is proved from considering that <math>[x] + a \le x + a < [x] + a + 1</math>.<br />
<br />
This is a known fact: the exponent of a prime <math>p</math> in the prime factorization of <math>n!</math> is <math>\sum_{k=1}^\infty \left[ \frac{n}{p^k} \right]</math>.<br />
<br />
==Key Lemma==<br />
''Lemma:'' For any pair of non-negative real numbers <math>x</math> and <math>y</math>, the following holds: <cmath>[5x] + [5y] \ge [x] + [y] + [3x + y] + [3y + x].</cmath><br />
<br />
<br />
==Proof of Key Lemma==<br />
We shall first prove the lemma statement for <math>0 \le x, y < 1</math>. Then <math>[x] = [y] = 0</math>, and so we have to prove that <cmath>[5x] + [5y] \ge [3x + y] + [3y + x].</cmath><br />
<br />
Let <math>[5x] = a, [5y] = b</math>, for integers <math>a</math> and <math>b</math>. Then <math>5x < a + 1 \text{ and } 5y < b + 1</math>, and so <math>x < \frac{a+1}{5}</math> and <math>y < \frac{b+1}{5}</math>.<br />
<br />
Define a new function, the ceiling function of x, to be the least integer greater than or equal to x. Also, define the ''trun-ceil function'', <math>[[x]],</math> to be the value of the ceiling function minus one. Thus, <math>[[a]] = a - 1</math> if <math>a</math> is an integer, and <math>[[a]] = [a]</math> otherwise. It is not difficult to verify that if <math>a</math> and <math>b</math> are real numbers with <math>a < b</math>, then <math>[[a]] \le [a] \le [[b]]</math>. (The only new thing we have to consider here is the case where <math>b</math> is integral, which is trivial.)<br />
<br />
Therefore,<br />
<cmath>[3x + y] + [3y + x] \le [[\frac{3a+b+4}{5}]] + [[\frac{3b+a+4}{5}]] = S.</cmath><br />
<br />
We shall prove that <math>S \le a + b = T</math>; to do so, we list cases. Without loss of generality, let <math>a \le b</math>. Because <math>x</math> and <math>y</math> are less than one, we have <math>a \le b \le 4.</math> Then, we find, for all 15 cases:<br />
<br />
<math>a = 0, b = 0 \rightarrow S = 0, T = 0.</math><br />
<br />
<math>a = 0, b = 1 \rightarrow S = 1, T = 1.</math><br />
<br />
<math>a = 0, b = 2 \rightarrow S = 2, T = 2.</math><br />
<br />
<math>a = 0, b = 3 \rightarrow S = 3, T = 3.</math><br />
<br />
<math>a = 0, b = 4 \rightarrow S = 4, T = 4.</math><br />
<br />
<math>a = 1, b = 1 \rightarrow S = 2, T = 2.</math><br />
<br />
<math>a = 1, b = 2 \rightarrow S = 3, T = 3.</math><br />
<br />
<math>a = 1, b = 3 \rightarrow S = 3, T = 4.</math><br />
<br />
<math>a = 1, b = 4 \rightarrow S = 5, T = 5.</math><br />
<br />
<math>a = 2, b = 2 \rightarrow S = 4, T = 4.</math><br />
<br />
<math>a = 2, b = 3 \rightarrow S = 4, T = 5.</math><br />
<br />
<math>a = 2, b = 4 \rightarrow S = 5, T = 6.</math><br />
<br />
<math>a = 3, b = 3 \rightarrow S = 6, T = 6.</math><br />
<br />
<math>a = 3, b = 4 \rightarrow S = 6, T = 7.</math><br />
<br />
<math>a = 4, b = 4 \rightarrow S = 6, T = 8.</math><br />
<br />
Thus, we have proved for all x and y in the range <math>[0, 1)</math>, <cmath>[5x] + [5y] = T \ge S \ge [3x + y] + [3y + x].</cmath><br />
<br />
Now, we prove the lemma statement without restrictions on x and y. Let <math>x = [x] + \{x\}</math>, and <math>y = [y] + \{y\}</math>, where <math>\{x\}</math>, the fractional part of x, is defined to be <math>x - [x]</math>. Note that <math>\{x\} < 1</math> as a result. Substituting gives the equivalent inequality<br />
<br />
<cmath>[5[x] + 5\{x\}] + [5[y] + 5\{y\}] \ge [x] + [y] + [3[x] + 3\{x\} + [y] + \{y\}] + [3[y] + 3\{y\} + [x] + \{x\}].</cmath><br />
<br />
But, because <math>[x] + a = [x + a]</math> for any integer <math>a</math>, this is obtained from simplifications following the adding of <math>5[x] + 5[y]</math> to both sides of<br />
<br />
<cmath>[5\{x\}] + [5\{y\}] \ge [3\{x\} + \{y\}] + [3\{y\} + \{x\}],</cmath><br />
<br />
which we have already proved (as <math>0 \le \{x\}, \{y\} < 1</math>). Thus, the lemma is proved.<br />
<br />
==How the Key Lemma Solves the Problem==<br />
Part (a) is a direct corollary of the lemma.<br />
<br />
For part (b), consider an arbitrary prime <math>p</math>. We have to prove the exponent of <math>p</math> in<br />
<center><math>I = \frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}</math></center><br />
is non-negative, or equivalently that <cmath>\sum_{k=1}^{\infty} \left( \left[ \frac{5m}{p^k} \right] + \left[ \frac{5n}{p^k} \right] \right) \ge \sum_{k=1}^{\infty} \left( \left[ \frac{m}{p^k} \right] + \left[ \frac{n}{p^k} \right] + \left[ \frac{3m+n}{p^k} \right] + \left[ \frac{3n+m}{p^k} \right] \right).</cmath><br />
<br />
But, the right-hand side minus the left-hand side of this inequality is <cmath>\sum_{k=1}^{\infty} \left( \left[ \frac{5m}{p^k} \right] + \left[ \frac{5n}{p^k} \right] - \left[ \frac{m}{p^k} \right] - \left[ \frac{n}{p^k} \right] - \left[ \frac{3m+n}{p^k} \right] - \left[ \frac{3n+m}{p^k} \right] \right),</cmath> which is the sum of non-negative terms by the Lemma. Thus, the inequality is proved, and so, by considering all primes <math>p</math>, we deduce that the exponents of all primes in <math>I</math> are non-negative. This proves the integrality of <math>I</math> (i.e. <math>I</math> is an integer). <math>\blacksquare</math><br />
<br />
==See Also==<br />
<br />
{{USAMO box|year=1975|before=First Question|num-a=2}}<br />
{{MAA Notice}}<br />
<br />
[[Category:Olympiad Number Theory Problems]]</div>Bobafett101https://artofproblemsolving.com/wiki/index.php?title=Proofs_of_AM-GM&diff=80053Proofs of AM-GM2016-08-21T17:30:45Z<p>Bobafett101: /* Proof by Cauchy Induction */</p>
<hr />
<div>This pages lists some proofs of the weighted [[AM-GM]] Inequality. The inequality's statement is as follows: for all nonnegative reals <math>a_1, \dotsc, a_n</math> and nonnegative reals <math>\lambda_1, \dotsc, \lambda_n</math> such that <math>\sum_{i=1}^n \lambda_i = 1</math>, then<br />
<cmath> \sum_{i=1}^n \lambda_i a_i \ge \prod_{i=1}^n a_i^{\lambda_i}, </cmath><br />
with equality if and only if <math>a_i = a_j</math> for all <math>i,j</math> such that <math>\lambda_i, \lambda_j \neq 0</math>.<br />
<br />
We first note that we may disregard any <math>a_i</math> for which <math>\lambda_i= 0</math>, as they contribute to neither side of the desired inequality. We also note that if <math>a_i= 0</math> and <math>\lambda_i \neq 0</math>, for some <math>i</math>, then the right-hand side of the inequality is zero and the left hand of the inequality is greater or equal to zero, with equality if and only if <math>a_j = 0 = a_i</math> whenever <math>\lambda_j\neq 0</math>. Thus we may henceforth assume that all <math>a_i</math> and <math>\lambda_i</math> are ''strictly positive.''<br />
<br />
== Complete Proofs ==<br />
<br />
=== Proof by Convexity ===<br />
<br />
We note that the [[function]] <math>x \mapsto \ln x</math> is strictly [[concave]]. Then by [[Jensen's Inequality]],<br />
<cmath> \ln \sum_i \lambda_i a_i \ge \sum_i \lambda_i \ln a_i = \ln \prod_i a_i^{\lambda_i} , </cmath><br />
with equality if and only if all the <math>a_i</math> are equal.<br />
Since <math>x \mapsto \ln x</math> is a strictly increasing function, it then follows that<br />
<cmath> \sum_i \lambda_i a_i \ge \prod_i a_i^{\lambda_i}, </cmath><br />
with equality if and only if all the <math>a_i</math> are equal, as desired. <math>\blacksquare</math><br />
<br />
=== Alternate Proof by Convexity ===<br />
<br />
''This proof is due to [[G. PĆ³lya]].''<br />
<br />
Note that the function <math>f:x \mapsto e^x</math> is strictly convex. Let <math>g(x)</math> be the line tangent to <math>f</math> at <math>(0,1)</math>; then <math>g(x) = x+1</math>. Since <math>f</math> is also a [[continuous]], [[differentiable]] function, it follows that <math>f(x) \ge g(x)</math> for all <math>x</math>, with equality exactly when <math>x=0</math>, i.e.,<br />
<cmath> 1+x \le e^x, </cmath><br />
with equality exactly when <math>x=0</math>.<br />
<br />
Now, set<br />
<cmath> r_i = a_i/\biggl( \sum_{j=1}^n \lambda_j a_j \biggr) - 1, </cmath><br />
for all integers <math>1\le i \le n</math>. Our earlier bound tells us that<br />
<cmath> r_i +1 \le \exp(r_i), </cmath><br />
so<br />
<cmath> (r_i +1)^{\lambda_i} \le \exp(\lambda_i r_i) .</cmath><br />
Multiplying <math>n</math> such inequalities gives us<br />
<br />
<cmath>\prod_{i=1}^n (r_i + 1)^{\lambda_{i}} \le \prod_{i=1}^n \exp \lambda_i r_i </cmath><br />
<br />
Evaluating the left hand side:<br />
<br />
<cmath>\prod_{i=1}^n (r_i + 1)^{\lambda_{i}} = \frac{\prod_{i=1}^n a_i^{\lambda_i} }{ (\sum_{j=1}^n \lambda_j a_j)^{\sum_{j=1}^n \lambda_i} } = \frac{\prod_{i=1}^n a_i^{\lambda_i} }{ \sum_{j=1}^n \lambda_j a_j } ,</cmath><br />
<br />
for <br />
<br />
<cmath> \sum_{j=1}^n \lambda_i = 1 .</cmath><br />
<br />
Evaluating the right hand side:<br />
<br />
<cmath> \prod_{i=1}^n \exp \lambda_i r_i = \prod_{i=1}^n \exp (\frac{a_i \lambda_i}{ \sum_{i=1}^n \lambda_j a_j} - \lambda_i) = \exp (\frac{\sum_{i=1}^n a_i \lambda_i}{ \sum_{i=1}^n \lambda_j a_j} - \sum_{i=1}^n \lambda_i) = \exp 0 = 1 .</cmath><br />
<br />
Substituting the results for the left and right sides:<br />
<br />
<cmath> \frac{\prod_{i=1}^n a_i^{\lambda_i} }{ \sum_{j=1}^n \lambda_j a_j } \le 1 </cmath><br />
<br />
<cmath> \prod_{i=1}^n a_i^{\lambda_i} \le \sum_{j=1}^n \lambda_j a_j = \sum_{i=1}^n \lambda_i a_i , </cmath><br />
<br />
as desired. <math>\blacksquare</math><br />
<br />
== Proofs of Unweighted AM-GM ==<br />
<br />
These proofs use the assumption that <math>\lambda_i = 1/n</math>, for all integers <math>1 \le i \le n</math>.<br />
<br />
=== Proof by Rearrangement ===<br />
<br />
Define the <math>n</math> sequence <math>\{ r_{ij}\}_{i=1}^{n}</math> as <math>r_{ij} = \sqrt[n]{a_i}</math>, for all integers <math>1 \le i,j \le n</math>. Evidently these sequences are similarly sorted. Then by the [[Rearrangement Inequality]],<br />
<cmath> \sum_i a_i = \sum_i \prod_j r_{ij} \ge \sum_i \prod_j r_{i,i+j} = n \prod_i \sqrt[n]{a_i} , </cmath><br />
where we take our indices modulo <math>n</math>, with equality exactly when all the <math>r_{ij}</math>, and therefore all the <math>a_i</math>, are equal. Dividing both sides by <math>n</math> gives the desired inequality. <math>\blacksquare</math><br />
<br />
=== Proof by [[Cauchy Induction]] ===<br />
<br />
We first prove that the inequality holds for two variables. Note that <math>(\sqrt{a}, \sqrt{b}), (\sqrt{a}, \sqrt{b})</math> are similarly sorted sequences. Then by the Rearrangement Inequality,<br />
<cmath> \sqrt{ab} = \frac{ \sqrt{a} \sqrt{b} + \sqrt{b} \sqrt{a}}{2} \le \frac{ \sqrt{a} \sqrt{a} + \sqrt{b} \sqrt{b}}{2} = \frac{a+b}{2} , </cmath><br />
with equality exactly when <math>a=b</math>.<br />
<br />
We next prove that if the inequality holds for <math>n</math> variables (with equality when all are equal to zero), than it holds for <math>2n</math> variables (with equality when all are equal to zero). Indeed, suppose the inequality holds for <math>n</math> variables. Let <math>A_n, A'_n, A_{2n}</math> denote the arithmetic means of <math>(a_1, \dotsc, a_n)</math>, <math>(a_{n+1}, \dotsc, a_{2n})</math>, <math>(a_1, \dotsc, a_{2n})</math>, respectively; let <math>G_n, G'_n, G_{2n}</math> denote their respective geometric means. Then<br />
<cmath> G_{2n} = \sqrt{G_n G'_n} \le \frac{G_n + G'_n}{2} \le \frac{A_n + A'_n}{2} = A_{2n}, </cmath><br />
with equality when all the numbers <math>a_1, \dotsc, a_{2n}</math> are equal, as desired.<br />
<br />
These two results show by induction that the theorem holds for <math>n=2^k</math>, for all integers <math>k</math>. In particular, for every integer <math>n</math>, there is an integer <math>N >n</math> such that the theorem holds for <math>N</math> variables.<br />
<br />
Finally, we show that if <math>N>n</math> and the theorem holds for <math>N</math> variables, then it holds for <math>n</math> variables <math>a_1, \dotsc, a_n</math> with arithmetic mean <math>A_n</math> and geometric mean <math>G_n</math>. Indeed, set <math>b_k = a_k</math> for <math>1\le k \le n</math>, and let <math>b_k = A_k</math> for <math>n < k \le N</math>. Then<br />
<cmath> G_n^{n/N} \cdot A_n^{(N-n)/N} = \prod_{i=1}^N b_i^{1/N} \le \sum_{i=1}^N b_i/N = A_n . </cmath><br />
It follows that <math>G_k^{n/N} \le A_k^{n/N}</math>, or <math>G_n \le A_n</math>, with equality exactly when all the <math>a_i</math> are equal to <math>A_k</math>.<br />
<br />
The last two results show that for all positive integers <math>n</math>, the theorem holds for <math>n</math> variables. Therefore the theorem is true. <math>\blacksquare</math><br />
<br />
[[Category:Inequality]]</div>Bobafett101https://artofproblemsolving.com/wiki/index.php?title=1972_USAMO_Problems/Problem_2&diff=791871972 USAMO Problems/Problem 22016-07-05T23:37:39Z<p>Bobafett101: /* Solution 2 */</p>
<hr />
<div>==Problem==<br />
A given tetrahedron <math>ABCD</math> is isosceles, that is, <math>AB=CD, AC=BD, AD=BC</math>. Show that the faces of the tetrahedron are acute-angled triangles.<br />
<br />
==Solutions==<br />
<br />
===Solution 1===<br />
<br />
Suppose <math>\triangle ABD</math> is fixed.<br />
By the equality conditions, it follows that the maximal possible value of <math>BC</math> occurs when the four vertices are coplanar, with <math>C</math> on the opposite side of <math>\overline{AD}</math> as <math>B</math>.<br />
In this case, the tetrahedron is not actually a tetrahedron, so this maximum isn't actually attainable.<br />
<br />
For the sake of contradiction, suppose <math>\angle ABD</math> is non-acute.<br />
Then, <math>(AD)^2\geq (AB)^2+(BD)^2</math>.<br />
In our optimal case noted above, <math>ACDB</math> is a parallelogram, so<br />
<cmath>\begin{align*}<br />
2(BD)^2 + 2(AB)^2 &= (AD)^2 + (CB)^2 \\<br />
&= 2(AD)^2 \\<br />
&\geq 2(BD)^2+2(AB)^2. <br />
\end{align*}</cmath><br />
However, as stated, equality cannot be attained, so we get our desired contradiction.<br />
<br />
===Solution 2===<br />
<br />
It's not hard to see that the four faces are congruent from SSS Congruence. Without loss of generality, assume that <math>AB\leq BC \leq CA</math>. Now assume, for the sake of contradiction, that each face is non-acute; that is, right or obtuse. Consider triangles <math>\triangle ABC</math> and <math>\triangle ABD</math>. They share side <math>AB</math>. Let <math>k</math> and <math>l</math> be the planes passing through <math>A</math> and <math>B</math>, respectively, that are perpendicular to side <math>AB</math>. We have that triangles <math>ABC</math> and <math>ABD</math> are non-acute, so <math>C</math> and <math>D</math> are not strictly between planes <math>k</math> and <math>l</math>. Therefore the length of <math>CD</math> is at least the distance between the planes, which is <math>AB</math>. However, if <math>CD=AB</math>, then the four points <math>A</math>, <math>B</math>, <math>C</math>, and <math>D</math> are coplanar, and the volume of <math>ABCD</math> would be zero. Therefore <math>CD>AB</math>. However, we were given that <math>CD=AB</math> in the problem, which leads to a contradiction. Therefore the faces of the tetrahedron must all be acute.<br />
<br />
===Solution 3===<br />
<br />
Let <math>\vec{a} = \overrightarrow{DA}</math>, <math>\vec{b} = \overrightarrow{DB}</math>, and <math>\vec{c} = \overrightarrow{DC}</math>. The conditions given translate to<br />
<cmath>\begin{align*}<br />
\vec{a}\cdot\vec{a} &= \vec{b}\cdot\vec{b} + \vec{c}\cdot\vec{c} - 2(\vec{b}\cdot\vec{c}) \\<br />
\vec{b}\cdot\vec{b} &= \vec{c}\cdot\vec{c} + \vec{a}\cdot\vec{a} - 2(\vec{c}\cdot\vec{a}) \\<br />
\vec{c}\cdot\vec{c} &= \vec{a}\cdot\vec{a} + \vec{b}\cdot\vec{b} - 2(\vec{a}\cdot\vec{b})<br />
\end{align*}</cmath><br />
We wish to show that <math>\vec{a}\cdot\vec{b}</math>, <math>\vec{b}\cdot\vec{c}</math>, and <math>\vec{c}\cdot\vec{a}</math> are all positive. WLOG, <math>\vec{a}\cdot\vec{a}\geq \vec{b}\cdot\vec{b}, \vec{c}\cdot\vec{c} > 0</math>, so it immediately follows that <math>\vec{a}\cdot\vec{b}</math> and <math>\vec{a}\cdot\vec{c}</math> are positive. Adding all three equations,<br />
<cmath>\vec{a}\cdot\vec{a} + \vec{b}\cdot\vec{b} + \vec{c}\cdot\vec{c} = 2(\vec{a}\cdot\vec{b} + \vec{a}\cdot\vec{c} + \vec{b}\cdot\vec{c})</cmath><br />
In addition,<br />
<cmath>\begin{align*}<br />
(\vec{a} - \vec{b} - \vec{c})\cdot(\vec{a} - \vec{b} - \vec{c})&\geq 0 \\<br />
\vec{a}\cdot\vec{a} + \vec{b}\cdot\vec{b} + \vec{c}\cdot\vec{c}&\geq 2(\vec{a}\cdot\vec{b} + \vec{a}\cdot\vec{c} - \vec{b}\cdot\vec{c}) \\<br />
2(\vec{a}\cdot\vec{b} + \vec{a}\cdot\vec{c} + \vec{b}\cdot\vec{c})&\geq 2(\vec{a}\cdot\vec{b} + \vec{a}\cdot\vec{c} - \vec{b}\cdot\vec{c}) \\<br />
\vec{b}\cdot\vec{c}&\geq 0<br />
\end{align*}</cmath><br />
Equality could only occur if <math>\vec{a} = \vec{b} + \vec{c}</math>, which requires the vectors to be coplanar and the original tetrahedron to be degenerate.<br />
<br />
==Solution 4==<br />
<br />
Suppose for the sake of contradiction that <math>\angle BAC</math> is not acute. Since all three sides of triangles <math>BAC</math> and <math>CDB</math> are congruent, those two triangles are congruent, meaning <math>\angle BDC=\angle BAC>90^{\circ}</math>. Construct a sphere with diameter <math>BC</math>. Since angles <math>BAC</math> and <math>BDC</math> are both not acute, <math>A</math> and <math>D</math> both lie on or inside the sphere. We seek to make <math>AD=BC</math> to satisfy the conditions of the problem. This can only occur when <math>AD</math> is a diameter of the sphere, since both points lie on or inside the sphere. However, for <math>AD</math> to be a diameter, all four points must be coplanar, as all diameters intersect at the center of the sphere. This would make tetrahedron <math>ABCD</math> degenerate, creating a contradiction. Thus, all angles on a face of an isosceles tetrahedron are acute.<br />
<br />
{{alternate solutions}}<br />
<br />
==See Also==<br />
<br />
{{USAMO box|year=1972|num-b=1|num-a=3}}<br />
{{MAA Notice}}<br />
<br />
[[Category:Olympiad Geometry Problems]]</div>Bobafett101https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_12B_Problems/Problem_20&diff=770132016 AMC 12B Problems/Problem 202016-02-24T06:08:38Z<p>Bobafett101: /* Solution */</p>
<hr />
<div>==Problem==<br />
<br />
A set of teams held a round-robin tournament in which every team played every other team exactly once. Every team won <math>10</math> games and lost <math>10</math> games; there were no ties. How many sets of three teams <math>\{A, B, C\}</math> were there in which <math>A</math> beat <math>B</math>, <math>B</math> beat <math>C</math>, and <math>C</math> beat <math>A?</math><br />
<br />
<math>\textbf{(A)}\ 385 \qquad<br />
\textbf{(B)}\ 665 \qquad<br />
\textbf{(C)}\ 945 \qquad<br />
\textbf{(D)}\ 1140 \qquad<br />
\textbf{(E)}\ 1330</math><br />
<br />
==Solution==<br />
<br />
We use complementary counting. Firstly, because each team played <math>20</math> other teams, there are <math>21</math> teams total. All sets that do not have <math>A</math> beat <math>B</math>, <math>B</math> beat <math>C</math>, and <math>C</math> beat <math>A</math> have one team that beats both the other teams. Thus we must count the number of sets of three teams such that one team beats the two other teams and subtract that number from the total number of ways to choose three teams.<br />
<br />
There are <math>21</math> ways to choose the team that beat the two other teams, and <math>\binom{10}{2} = 45</math> to choose two teams that the first team both beat. This is <math>21 * 45 = 945</math> sets. There are <math>\binom{21}{3} = 1330</math> sets of three teams total. Subtracting, we obtain <math>1330 - 945 = \boxed{ A) 385}</math> as our answer.<br />
<br />
==See Also==<br />
{{AMC12 box|year=2016|ab=B|num-b=19|num-a=21}}<br />
{{MAA Notice}}</div>Bobafett101https://artofproblemsolving.com/wiki/index.php?title=2008_AMC_12A_Problems/Problem_19&diff=741202008 AMC 12A Problems/Problem 192015-12-31T03:54:32Z<p>Bobafett101: Added new solution</p>
<hr />
<div>==Problem==<br />
In the expansion of<br />
<cmath>\left(1 + x + x^2 + \cdots + x^{27}\right)\left(1 + x + x^2 + \cdots + x^{14}\right)^2,</cmath><br />
what is the [[coefficient]] of <math>x^{28}</math>?<br />
<br />
<math>\mathrm{(A)}\ 195\qquad\mathrm{(B)}\ 196\qquad\mathrm{(C)}\ 224\qquad\mathrm{(D)}\ 378\qquad\mathrm{(E)}\ 405</math><br />
<br />
==Solution 1== <br />
Let <math>A = \left(1 + x + x^2 + \cdots + x^{14}\right)</math> and <math>B = \left(1 + x + x^2 + \cdots + x^{27}\right)</math>. We are expanding <math>A \cdot A \cdot B</math>. <br />
<br />
Since there are <math>15</math> terms in <math>A</math>, there are <math>15^2 = 225</math> ways to choose one term from each <math>A</math>. The product of the selected terms is <math>x^n</math> for some integer <math>n</math> between <math>0</math> and <math>28</math> inclusive. For each <math>n \neq 0</math>, there is one and only one <math>x^{28 - n}</math> in <math>B</math>. For example, if I choose <math>x^2</math> from <math>A</math> , then there is exactly one power of <math>x</math> in <math>B</math> that I can choose; in this case, it would be <math>x^{24}</math>. Since there is only one way to choose one term from each <math>A</math> to get a product of <math>x^0</math>, there are <math>225 - 1 = 224</math> ways to choose one term from each <math>A</math> and one term from <math>B</math> to get a product of <math>x^{28}</math>. Thus the coefficient of the <math>x^{28}</math> term is <math>224 \Rightarrow C</math>.<br />
<br />
== Solution 2 ==<br />
Let <math>P(x) = \left(1 + x + x^2 + \cdots + x^{14}\right)^2 = a_0 + a_1x + a_2x^2 + \cdots + a_{28}x^{28}</math>. Then the <math>x^{28}</math> term from the product in question <math>\left(1 + x + x^2 + \cdots + x^{27}\right)(a_0 + a_1x + a_2x^2 + \cdots + a_{28}x^{28})</math> is<br />
<br />
<math>1a_{28}x^{28} + xa_{27}x^{27} + x^2a_{26}x^{26} + \cdots + x^{27}a_1x = \left(a_1 + a_2 + \cdots a_{28}\right)x^{28}</math><br />
<br />
So we are trying to find the sum of the coefficients of <math>P(x)</math> minus <math>a_0</math>. Since the constant term <math>a_0</math> in <math>P(x)</math> (when expanded) is <math>1</math>, and the sum of the coefficients of <math>P(x)</math> is <math>P(1)</math>, we find the answer to be<br />
<math>P(1) - a_0<br />
= \left(1 + 1 + 1^2 + \cdots 1^{14}\right)^2 - 1<br />
= 15^2 - 1<br />
= 224 \rightarrow C</math><br />
<br />
==Solution 3==<br />
We expand <math>(1 + x + x^2 + x^3 + \cdots + x^{14})^2</math> to <math>(1 + x + x^2 + x^3 + \cdots + x^{14}) * (1 + x + x^2 + x^3 + \cdots + x^{14})</math> and use FOIL to multiply. It expands out to:<br />
<br />
<math>1 + x + x^2 + x^3 + x^4 + \cdots + x^{14} + </math> <br />
<br />
<math>\qquad x + x^2 + x^3 + x^4 + \cdots + x^{14} + x^{15} + </math> <br />
<br />
<math>\qquad \qquad x^2 + x^3 + x^4 + \cdots + x^{14} + x^{15} + x^{16} + \cdots</math><br />
<br />
It becomes apparent that <br />
<br />
<math>(1 + x + x^2 + x^3 + \cdots + x^{14})^2 = 1 + 2x + 3x^2 + 4x^3 + \cdots + 15x^{14} + 14x^{15} + 13x^{16} + \cdots + x^{28}</math>.<br />
<br />
Now we have to find the coefficient of <math>x^{28}</math> in the product: <br />
<br />
<math>(1 + 2x + 3x^2 + 4x^3 + \cdots + 15x^{14} + 14x^{15} + 13x^{16} + \cdots + x^{28}) * (1 + x + x^2 + x^3 + \cdots + x^{27})</math>.<br />
<br />
We quickly see that the we get <math>x^{28}</math> terms from <math>x^{27} * 2x</math>, <math>x^{26} * 3x^2</math>, <math>x^{25} * 4x^3</math>, ... <math>15x^{14} * x^{14}</math>, ... <math>x^{28} * 1</math>. The coefficient of <math>x^{28}</math> is just the sum of the coefficients of all these terms. <math>1 + 2 + 3 + 4 + \cdots + 15 + 14 + 13 + \cdots + 4 + 3 + 2 = 224</math>, so the answer is <math>\boxed{C}</math>.<br />
<br />
==Solution 4==<br />
Rewrite the product as <math>\frac{(x^{28} - 1)(x^{15} - 1)(x^{15} - 1)}{(x - 1)^3}</math>. It is known that <br />
<br />
<cmath>\frac{1}{(1 - x)^n} = \binom{n - 1}{n - 1} + \binom{n}{n - 1}x + \binom{n + 1}{n - 1}x^2 + \binom{n + 2}{n - 1}x^3 + \cdots + \binom{n - 1 + k}{n - 1}x^k + \cdots .</cmath><br />
<br />
Thus, our product becomes<br />
<br />
<cmath>-\left( x^{28} - 1 \right) \left( x^{15} - 1 \right) \left( x^{15} - 1 \right) \left( \binom{2}{2} + \binom{3}{2}x + \binom{4}{2}x^2 + \cdots \right).</cmath><br />
<br />
<cmath>= -\left( x^{28} - 1 \right) \left( x^{15} - 1 \right) \left( x^{15} - 1 \right) \left( 1 + 3x + 6x^2 + \cdots \right). </cmath><br />
<br />
We determine the <math>x^{28}</math> coefficient by doing casework on the first three terms in our product. We can obtain an <math>x^{28}</math> term by choosing <math>x^{28}</math> in the first term, <math>-1</math> in the second and third terms, and <math>1</math> in the fourth term. We can get two <math>x^{28}</math> terms by choosing <math>x^{15}</math> in either the second or third term, <math>-1</math> in the first term, <math>-1</math> in the second or third term from which <math>x^{15}</math> has not been chosen, and the <math>\binom{15}{2}x^{13}</math> in the fourth term. We get <math>\binom{15}{2} * 2 = 210</math> <math>x^{28}</math> terms this way. (We multiply by <math>2</math> because the <math>x^{15}</math> term could have been chosen from the second term or the third term). Lastly, we can get an <math>x^{28}</math> term by choosing <math>-1</math> in the first three terms and a <math>\binom{30}{2}x^{28}</math> from the fourth term. We have a total of <math>1 + 210 - 435 = -224</math> for the <math>x^{28}</math> coefficient, but we recall that we have a negative sign in front of our product, so we obtain an answer of <math>224</math> <math>\boxed{C)}</math>.<br />
<br />
==See Also==<br />
{{AMC12 box|year=2008|ab=A|num-b=18|num-a=20}}<br />
<br />
[[Category:Introductory Algebra Problems]]<br />
{{MAA Notice}}</div>Bobafett101