Difference between revisions of "2017 AMC 12A Problems/Problem 25"

Revision as of 18:03, 8 February 2017

Problem

The vertices $V$ of a centrally symmetric hexagon in the complex plane are given by $V=\left\{ \sqrt{2}i,-\sqrt{2}i, \frac{1}{\sqrt{8}}(1+i),\frac{1}{\sqrt{8}}(-1+i),\frac{1}{\sqrt{8}}(1-i),\frac{1}{\sqrt{8}}(-1-i) \right\}.$ For each $j$ , $1\leq j\leq 12$ , an element $z_j$ is chosen from $V$ at random, independently of the other choices. Let $P={\prod}_{j=1}^{12}z_j$ be the product of the $12$ numbers selected. What is the probability that $P=-1$ ?

$\textbf{(A) } \dfrac{5\cdot11}{3^{10}} \qquad \textbf{(B) } \dfrac{5^2\cdot11}{2\cdot3^{10}} \qquad \textbf{(C) } \dfrac{5\cdot11}{3^{9}} \qquad \textbf{(D) } \dfrac{5\cdot7\cdot11}{2\cdot3^{10}} \qquad \textbf{(E) } \dfrac{2^2\cdot5\cdot11}{3^{10}}$

Solution

It is possible to solve this problem using elementary counting methods. This solution proceeds by a cleaner generating function.

We note that $\pm \sqrt{2}i$ both lie on the imaginary axis and each of the $\frac{1}{\sqrt{8}}(\pm 1\pm i)$ have length $\frac{1}{2}$ and angle of odd multiples of $\pi/4$ , i.e. $\pi/4,3\pi/4,5\pi,4,7\pi/4$ . When we draw these 6 complex numbers out on the complex plane, we get a crystal-looking thing. Note that the total number of ways to choose 12 complex numbers is $6^{12}$ . Now we count the number of good combinations.

We first consider the lengths. When we multiply 12 complex numbers together, their magnitudes multiply. Suppose we have $n$ of the numbers $\pm \sqrt{2}i$ ; then we must have $\left(\sqrt{2}\right)^n\cdot\left(\frac{1}{2}\right)^{12-n}=1 \Longrightarrow n=8$ . Having $n=8$ will take care of the length of the product; now we need to deal with the angle.

We require $\sum\theta\equiv\pi \mod 2\pi$ . Letting $z$ be $e^{i\pi/4}$ , we see that the angles we have available are $\{z^1,z^2,z^3,z^5,z^6,z^7\}$ , where we must choose exactly 8 angles from the set $\{z^2,z^6\}$ and exactly 4 from the set $\{z^1,z^3,z^5,z^7\}$ . If we found a good combination where we had $a_i$ of each angle $z^i$ , then the amount this would contribute to our count would be $\binom{12}{4,8}\cdot\binom{8}{a_2,a_6}\cdot\binom{4}{a_1,a_3,a_5,a_7}$ . We want to add these all up. We proceed by generating functions.

Consider $(t_2x^2+t_6x^6)^8(t_1x^1+t_3x^3+t_5x^5+t_7x^7)^4.$ The expansion will be of the form $\sum_i\left(\sum_{\sum a=i} \binom{8}{a_2,a_6}\binom{4}{a_1,a_3,a_5,a_7}{t_1}^{a_1}{t_2}^{a_2}{t_3}^{a_3}{t_5}^{a_5}{t_6}^{a_6}{t_7}^{a_7}x^i \right)$ . Note that if we reduced the powers of $x$ mod $8$ and fished out the coefficient of $x^4$ and plugged in $t_i=1\ \forall\,i$ (and then multiplied by $\binom{12}{4,8}$ ) then we would be done. Since plugging in $t_i=1$ doesn't affect the $x$ 's, we do that right away. The expression then becomes $x^{20}(1+x^4)^8(1+x^2+x^4+x^6)^4=x^{20}(1+x^4)^{12}(1+x^2)^4=x^4(1+x^4)^{12}(1+x^2)^4,$ where the last equality is true because we are taking the powers of $x$ mod $8$ . Let $[x^n]f(x)$ denote the coefficient of $x^n$ in $f(x)$ . Note $[x^4] x^4(1+x^4)^{12}(1+x^2)^4=[x^0](1+x^4)^{12}(1+x^2)^4$ . We use the roots of unity filter, which states $\text{terms of }f(x)\text{ that have exponent congruent to }k\text{ mod }n=\frac{1}{n}\sum_{m=1}^n \frac{f(z^mx)}{z^{mk}},$ where $z=e^{i\pi/n}$ . In our case $k=0$ , so we only need to find the average of the $f(z^mx)$ 's. \begin{align*} z^0 &\Longrightarrow (1+x^4)^{12}(1+x^2)^4,\\ z^1 &\Longrightarrow (1-x^4)^{12}(1+ix^2)^4,\\ z^2 &\Longrightarrow (1+x^4)^{12}(1-x^2)^4,\\ z^3 &\Longrightarrow (1-x^4)^{12}(1-ix^2)^4,\\ z^4 &\Longrightarrow (1+x^4)^{12}(1+x^2)^4,\\ z^5 &\Longrightarrow (1-x^4)^{12}(1+ix^2)^4,\\ z^6 &\Longrightarrow (1+x^4)^{12}(1-x^2)^4,\\ z^7 &\Longrightarrow (1-x^4)^{12}(1-ix^2)^4. \end{align*} We plug in $x=1$ and take the average to find the sum of all coefficients of $x^{\text{multiple of 8}}$ . Plugging in $x=1$ makes all of the above zero except for $z^0$ and $z^4$ . Averaging, we get $2^{14}$ . Now the answer is simply $\frac{\binom{12}{4,8}}{6^{12}}\cdot 2^{14}=\boxed{\frac{2^2\cdot 5\cdot 11}{3^{10}}}.$

2017 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Problem ??
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2017 AMC 12A Problems/Problem 25"

Revision as of 18:03, 8 February 2017

Problem

Solution

See Also

@@ Line 7: / Line 7: @@
 <math>\textbf{(A) } \dfrac{5\cdot11}{3^{10}} \qquad \textbf{(B) } \dfrac{5^2\cdot11}{2\cdot3^{10}} \qquad \textbf{(C) } \dfrac{5\cdot11}{3^{9}} \qquad \textbf{(D) } \dfrac{5\cdot7\cdot11}{2\cdot3^{10}} \qquad \textbf{(E) } \dfrac{2^2\cdot5\cdot11}{3^{10}}</math>
+==Solution==
+It is possible to solve this problem using elementary counting methods. This solution proceeds by a cleaner generating function.
+We note that <math>\pm \sqrt{2}i</math> both lie on the imaginary axis and each of the <math>\frac{1}{\sqrt{8}}(\pm 1\pm i)</math> have length <math>\frac{1}{2}</math> and angle of odd multiples of <math>\pi/4</math>, i.e. <math>\pi/4,3\pi/4,5\pi,4,7\pi/4</math>. When we draw these 6 complex numbers out on the complex plane, we get a crystal-looking thing. Note that the total number of ways to choose 12 complex numbers is <math>6^{12}</math>. Now we count the number of good combinations.
+We first consider the lengths. When we multiply 12 complex numbers together, their magnitudes multiply. Suppose we have <math>n</math> of the numbers <math>\pm \sqrt{2}i</math>; then we must have <math>\left(\sqrt{2}\right)^n\cdot\left(\frac{1}{2}\right)^{12-n}=1 \Longrightarrow n=8</math>. Having <math>n=8</math> will take care of the length of the product; now we need to deal with the angle.
+We require <math>\sum\theta\equiv\pi \mod 2\pi</math>. Letting <math>z</math> be <math>e^{i\pi/4}</math>, we see that the angles we have available are <math>\{z^1,z^2,z^3,z^5,z^6,z^7\}</math>, where we must choose exactly 8 angles from the set <math>\{z^2,z^6\}</math> and exactly 4 from the set <math>\{z^1,z^3,z^5,z^7\}</math>. If we found a good combination where we had <math>a_i</math> of each angle <math>z^i</math>, then the amount this would contribute to our count would be <math>\binom{12}{4,8}\cdot\binom{8}{a_2,a_6}\cdot\binom{4}{a_1,a_3,a_5,a_7}</math>. We want to add these all up. We proceed by generating functions.
+Consider <cmath>(t_2x^2+t_6x^6)^8(t_1x^1+t_3x^3+t_5x^5+t_7x^7)^4.</cmath> The expansion will be of the form <math>\sum_i\left(\sum_{\sum a=i} \binom{8}{a_2,a_6}\binom{4}{a_1,a_3,a_5,a_7}{t_1}^{a_1}{t_2}^{a_2}{t_3}^{a_3}{t_5}^{a_5}{t_6}^{a_6}{t_7}^{a_7}x^i \right)</math>. Note that if we reduced the powers of <math>x</math> mod <math>8</math> and fished out the coefficient of <math>x^4</math> and plugged in <math>t_i=1\ \forall\,i</math> (and then multiplied by <math>\binom{12}{4,8}</math>) then we would be done. Since plugging in <math>t_i=1</math> doesn't affect the <math>x</math>'s, we do that right away. The expression then becomes <cmath>x^{20}(1+x^4)^8(1+x^2+x^4+x^6)^4=x^{20}(1+x^4)^{12}(1+x^2)^4=x^4(1+x^4)^{12}(1+x^2)^4,</cmath> where the last equality is true because we are taking the powers of <math>x</math> mod <math>8</math>. Let <math>[x^n]f(x)</math> denote the coefficient of <math>x^n</math> in <math>f(x)</math>. Note <math>[x^4] x^4(1+x^4)^{12}(1+x^2)^4=[x^0](1+x^4)^{12}(1+x^2)^4</math>. We use the roots of unity filter, which states <cmath>\text{terms of }f(x)\text{ that have exponent congruent to }k\text{ mod }n=\frac{1}{n}\sum_{m=1}^n \frac{f(z^mx)}{z^{mk}},</cmath> where <math>z=e^{i\pi/n}</math>. In our case <math>k=0</math>, so we only need to find the average of the <math>f(z^mx)</math>'s.
+\begin{align*}
+z^0 &\Longrightarrow (1+x^4)^{12}(1+x^2)^4,\\
+z^1 &\Longrightarrow (1-x^4)^{12}(1+ix^2)^4,\\
+z^2 &\Longrightarrow (1+x^4)^{12}(1-x^2)^4,\\
+z^3 &\Longrightarrow (1-x^4)^{12}(1-ix^2)^4,\\
+z^4 &\Longrightarrow (1+x^4)^{12}(1+x^2)^4,\\
+z^5 &\Longrightarrow (1-x^4)^{12}(1+ix^2)^4,\\
+z^6 &\Longrightarrow (1+x^4)^{12}(1-x^2)^4,\\
+z^7 &\Longrightarrow (1-x^4)^{12}(1-ix^2)^4.
+\end{align*}
+We plug in <math>x=1</math> and take the average to find the sum of all coefficients of <math>x^{\text{multiple of 8}}</math>. Plugging in <math>x=1</math> makes all of the above zero except for <math>z^0</math> and <math>z^4</math>. Averaging, we get <math>2^{14}</math>. Now the answer is simply <cmath>\frac{\binom{12}{4,8}}{6^{12}}\cdot 2^{14}=\boxed{\frac{2^2\cdot 5\cdot 11}{3^{10}}}.</cmath>
 ==See Also==
 {{AMC12 box|year=2017|ab=A|num-b=24|num-a=??}}
 {{MAA Notice}}