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

m
m (Solution 4)
Line 69: Line 69:
 
==Solution 4==
 
==Solution 4==
 
We can write the points in polar form <math>(r, \theta)</math> as
 
We can write the points in polar form <math>(r, \theta)</math> as
<cmath>V = \{ (\sqrt{2}, \frac{\pi}{2}), (\sqrt{2}, \frac{3\pi}{2}), (\frac{1}{2}, \frac{\pi}{4}), (\frac{1}{2}, \frac{3\pi}{4}), (\frac{1}{2}, \frac{5\pi}{4}), (\frac{1}{2}, \frac{7\pi}{4}).</cmath>Note that when multiplying complex numbers, the <math>r</math>s multiply and the <math>\theta</math>s add, and since <math>-1 = (1, \pi),</math> we need <math>8</math> complex numbers with <math>r = \sqrt{2} = 2^{0.5}</math> and <math>4</math> with <math>r = \frac{1}{2} = 2^{-1}.</math> By binomial distribution, the probability of this occurring is <math>\dbinom{12}{4} (\frac{1}{3})^8 (\frac{2}{3})^4.</math> For the <math>\theta</math> part, note that <math>\frac{4\theta}{\pi}</math> must be congruent to <math>4 \mod 8, </math> and by using simple symmetry, the probability of the aforementioned occurring is <math>\frac{1}{4}. </math> This is since <math>2a + 6b</math> is even for all <math>a + b =8, </math> and the number of ordered quadruples <math>(a_1, a_2, a_3, a_4)</math> such that <math>a_i \in \{1, 3, 5, 7\}</math> for all <math>1 \leq i \leq 4</math> and <math>a_1 + a_2 + a_3 + a_4 \equiv 2k \mod 8</math> is the same for all <math>1 \leq k \leq 4,</math> again by using symmetry. Thus, our probability is <cmath>(\frac{1}{4}) (\frac{1}{3})^8 (\frac{2}{3})^4 \dbinom{12}{4} = \frac{2^2}{3^{12}} \dbinom{12}{4} = \boxed{\frac{2^2 \cdot 11 \cdot 5}{3^{10}}}.</cmath>
+
<cmath>V = \{ (\sqrt{2}, \frac{\pi}{2}), (\sqrt{2}, \frac{3\pi}{2}), (\frac{1}{2}, \frac{\pi}{4}), (\frac{1}{2}, \frac{3\pi}{4}), (\frac{1}{2}, \frac{5\pi}{4}), (\frac{1}{2}, \frac{7\pi}{4}).</cmath>Note that when multiplying complex numbers, the <math>r</math>'s multiply and the <math>\theta</math>'s add, and since <math>-1 = (1, \pi),</math> we need <math>8</math> complex numbers with <math>r = \sqrt{2} = 2^{0.5}</math> and <math>4</math> with <math>r = \frac{1}{2} = 2^{-1}.</math> By binomial distribution, the probability of this occurring is <math>\dbinom{12}{4} (\frac{1}{3})^8 (\frac{2}{3})^4.</math> For the <math>\theta</math> part, note that <math>\frac{4\theta}{\pi}</math> must be congruent to <math>4 \mod 8, </math> and by using simple symmetry, the probability of the aforementioned occurring is <math>\frac{1}{4}. </math> This is since <math>2a + 6b</math> is even for all <math>a + b =8, </math> and the number of ordered quadruples <math>(a_1, a_2, a_3, a_4)</math> such that <math>a_i \in \{1, 3, 5, 7\}</math> for all <math>1 \leq i \leq 4</math> and <math>a_1 + a_2 + a_3 + a_4 \equiv 2k \mod 8</math> is the same for all <math>1 \leq k \leq 4,</math> again by using symmetry. Thus, our probability is <cmath>(\frac{1}{4}) (\frac{1}{3})^8 (\frac{2}{3})^4 \dbinom{12}{4} = \frac{2^2}{3^{12}} \dbinom{12}{4} = \boxed{\frac{2^2 \cdot 11 \cdot 5}{3^{10}}}.</cmath>
  
 
-fidgetboss_4000
 
-fidgetboss_4000

Revision as of 14:37, 11 July 2020

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 1

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}}}.\]

Solution 2

By changing $z_1$ to $-z_1$, we can give a bijection between cases where $P=-1$ and cases where $P=1$, so we'll just find the probability that $P=\pm 1$ and divide by $2$ in the end. Multiplying the hexagon's vertices by $i$ doesn't change $P$, and switching any $z_j$ with $-z_j$ doesn't change the property $P=\pm 1$, so the probability that $P=\pm1$ remains the same if we only select our $z_j$'s at random from \[\left\{a= \sqrt 2,\quad b=\frac1{\sqrt{8}}(1+i),\quad c=\frac1{\sqrt{8}}(1-i)\right\}.\] Since $|a|=\sqrt2$ and $|b|=|c|=\frac12$, we must choose $a$ exactly $8$ times to make $|P|=1$. To ensure $P$ is real, we must either choose $b$ $4$ times, $c$ $4$ times, or both $b$ and $c$ $2$ times. This gives us a total of \[2\binom{12}{4}+\binom{12}{2}\binom{10}{2}=(12\cdot 11\cdot 10\cdot 9)\left(\frac1{12}+\frac14\right)=(2^3\cdot 3^3\cdot 5\cdot 11)\frac13\] good sequences $z_1,\dots,z_{12}$, and hence the final result is \[\frac12\cdot \frac{2^3\cdot 3^2\cdot 5\cdot 11}{3^{12}}=\boxed{(E)}.\]

Solution 3

We use generating functions and a roots of unity filter. Notice that all values in $V$ are eighth roots of unity multiplied by a constant. Let $x$ be a primitive eighth root of unity ($e^{\frac{i\pi}{4}}$). The numbers in $V$ are then $\left \{ \frac{x}{2},x^2\sqrt2,\frac{x^3}{2},\frac{x^5}{2},x^6\sqrt2,\frac{x^7}{2} \right\}$. To have $P=-1$, we must have that $|P|=1$, so eight of the $(z_i)$ must belong to \[\left \{ x^2\sqrt2,x^6\sqrt2 \right\}\] and the other four must belong to \[\left \{ \frac{x}{2},\frac{x^3}{2},\frac{x^5}{2},\frac{x^7}{2} \right\}\] So, we write the generating function \[\left (x^2 +x^6 \right )^8 \left (x+x^3+x^5+x^7 \right )^4\] to describe the product. Note that this assumes that the $(z_i)$ that belong to $\left \{ x^2\sqrt2,x^6\sqrt2 \right\}$ come first, so we will need to multiply by $\binom{12}{4}$ at the end. We now apply a roots of unity filter to find the sum of the coefficients of the exponents that are $4\pmod{8}$, or equivalently the coefficients of the powers that are multiples of $8$ of the following function: \[P(x)=\left (x^2 +x^6 \right )^8 \left (x+x^3+x^5+x^7 \right )^4x^4\] Let $\zeta=e^{\frac{i\pi}{4}}$. We are looking for $\frac{P(1)+P(\zeta)+P(\zeta^2)+P(\zeta^3)+P(\zeta^4)+P(\zeta^5)+P(\zeta^6)+P(\zeta^7)}{8}$. $P(1)=P(-1)=2^{16}$, and all of the rest are equal to $0$. So, we get an answer of $\frac{2^{16}+2^{16}}{8\cdot 6^{12}}=\frac{2^{14}}{6^{12}}=\frac{2^2}{3^{10}}$. But wait! We need to multiply by ${12}\choose {4}$=$\frac{12\cdot11\cdot10\cdot9}{4\cdot3\cdot3\cdot1}=5\cdot9\cdot11$. So, the answer is $\boxed{\text{\textbf{(E) }} \frac{2^2\cdot5\cdot11}{3^{10}} }$

Solution 4

We can write the points in polar form $(r, \theta)$ as \[V = \{ (\sqrt{2}, \frac{\pi}{2}), (\sqrt{2}, \frac{3\pi}{2}), (\frac{1}{2}, \frac{\pi}{4}), (\frac{1}{2}, \frac{3\pi}{4}), (\frac{1}{2}, \frac{5\pi}{4}), (\frac{1}{2}, \frac{7\pi}{4}).\]Note that when multiplying complex numbers, the $r$'s multiply and the $\theta$'s add, and since $-1 = (1, \pi),$ we need $8$ complex numbers with $r = \sqrt{2} = 2^{0.5}$ and $4$ with $r = \frac{1}{2} = 2^{-1}.$ By binomial distribution, the probability of this occurring is $\dbinom{12}{4} (\frac{1}{3})^8 (\frac{2}{3})^4.$ For the $\theta$ part, note that $\frac{4\theta}{\pi}$ must be congruent to $4 \mod 8,$ and by using simple symmetry, the probability of the aforementioned occurring is $\frac{1}{4}.$ This is since $2a + 6b$ is even for all $a + b =8,$ and the number of ordered quadruples $(a_1, a_2, a_3, a_4)$ such that $a_i \in \{1, 3, 5, 7\}$ for all $1 \leq i \leq 4$ and $a_1 + a_2 + a_3 + a_4 \equiv 2k \mod 8$ is the same for all $1 \leq k \leq 4,$ again by using symmetry. Thus, our probability is \[(\frac{1}{4}) (\frac{1}{3})^8 (\frac{2}{3})^4 \dbinom{12}{4} = \frac{2^2}{3^{12}} \dbinom{12}{4} = \boxed{\frac{2^2 \cdot 11 \cdot 5}{3^{10}}}.\]

-fidgetboss_4000

See Also

2017 AMC 12A (ProblemsAnswer KeyResources)
Preceded by
Problem 24
Followed by
Last 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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png