https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Jtanman&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T14:04:55ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_I_Problems/Problem_12&diff=309322007 AIME I Problems/Problem 122009-03-22T21:13:14Z<p>Jtanman: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
In [[isosceles triangle]] <math>\triangle ABC</math>, <math>A</math> is located at the [[origin]] and <math>B</math> is located at <math>(20,0)</math>. Point <math>C</math> is in the [[first quadrant]] with <math>AC = BC</math> and angle <math>BAC = 75^{\circ}</math>. If triangle <math>ABC</math> is rotated counterclockwise about point <math>A</math> until the image of <math>C</math> lies on the positive <math>y</math>-axis, the area of the region common to the original and the rotated triangle is in the form <math>p\sqrt{2} + q\sqrt{3} + r\sqrt{6} + s</math>, where <math>p,q,r,s</math> are integers. Find <math>\frac{p-q+r-s}2</math>.<br />
<br />
{|<br />
|-<br />
| __TOC__<br />
| [[Image:AIME I 2007-12.png]]<br />
|}<br />
== Solution ==<br />
=== Solution 1 ===<br />
Let the new triangle be <math>\triangle AB'C'</math> (<math>A</math>, the origin, is a vertex of both triangles). Let <math>\overline{B'C'}</math> intersect with <math>\overline{AC}</math> at point <math>D</math>, <math>\overline{BC}</math> intersect with <math>\overline{B'C'}</math> at <math>E</math>, and <math>\overline{BC}</math> intersect with <math>\overline{AB'}</math> at <math>F</math>. The region common to both triangles is the [[quadrilateral]] <math>ADEF</math>. Notice that <math>[ADEF] = [\triangle ADB'] - [\triangle EFB']</math>, where we let <math>[\ldots]</math> denote area. <br />
<br />
<center>To find <math>[\triangle ADB']</math>:</center><br />
<br />
Since <math>\angle B'AC'</math> and <math>\angle BAC</math> both have measures <math>75^{\circ}</math>, both of their [[complement]]s are <math>15^{\circ}</math>, and <math>\angle DAB' = 90 - 2(15) = 60^{\circ}</math>. We know that <math>\angle DB'A = 75^{\circ}</math>, so <math>\angle ADB' = 180 - 60 - 75 = 45^{\circ}</math>.<br />
<br />
Thus <math>\triangle ADB'</math> is a <math>45 - 60 - 75 \triangle</math>. It can be solved by drawing an [[altitude]] splitting the <math>75^{\circ}</math> angle into <math>30^{\circ}</math> and <math>45^{\circ}</math> angles, forming a <math>30-60-90</math> [[right triangle]] and a <math>45-45-90</math> isosceles right triangle. Since we know that <math>AB' = 20</math>, the base of the <math>30-60-90</math> triangle is <math>10</math>, the base of the <math>45-45-90</math> is <math>10\sqrt{3}</math>, and their common height is <math>10\sqrt{3}</math>. Thus, the total area of <math>[\triangle ADB'] = \frac{1}{2}(10\sqrt{3})(10\sqrt{3} + 10) = \boxed{150 + 50\sqrt{3}}</math>.<br />
<br />
<center>To find <math>[\triangle EFB']</math>:</center><br />
<br />
Since <math>\triangle AFB</math> is also a <math>15-75-90</math> triangle,<br />
<center><math>AF = 20\sin 75 = 20 \sin (30 + 45) = 20\left(\frac{\sqrt{2} + \sqrt{6}}4\right) = 5\sqrt{2} + 5\sqrt{6}</math></center><br />
and<br />
<center><math>FB' = AB' - AF = 20 - 5\sqrt{2} - 5\sqrt{6}</math></center><br />
Since <math>[\triangle EFB'] = \frac{1}{2} (FB' \cdot EF) = \frac{1}{2} (FB') (FB' \tan 75^{\circ})</math>. With some horrendous [[algebra]], we can calculate<br />
<center><math>\begin{align*}<br />
[\triangle EFB'] & = \frac{1}{2}\tan (30 + 45) \cdot (20 - 5\sqrt{2} - 5\sqrt{6})^2 \\<br />
& = 25 \left(\frac{\frac{1}{\sqrt{3}} + 1}{1 - \frac{1}{\sqrt{3}}}\right) \left(8 - 2\sqrt{2} - 2\sqrt{6} - 2\sqrt{2} + 1 + \sqrt{3} - 2\sqrt{6} + \sqrt{3} + 3\right) \\<br />
& = 25(2 + \sqrt{3})(12 - 4\sqrt{2} - 4\sqrt{6} + 2\sqrt{3}) \\<br />
[\triangle EFB'] & = \boxed{- 500\sqrt{2} + 400\sqrt{3} - 300\sqrt{6} +750}.<br />
\end{align*}</math></center><br />
<br />
To finish,<br />
<center><math>\begin{align*}<br />
[ADEF] &= [\triangle ADB'] - [\triangle EFB']\\<br />
&= \left(150 + 50\sqrt{3}\right) - \left(-500\sqrt{2} + 400\sqrt{3} - 300\sqrt{6} + 750\right)\\<br />
&=500\sqrt{2} - 350\sqrt{3} + 300\sqrt{6} - 600\\ \end{align*}</math></center><br />
Hence, <math>\frac{p-q+r-s}{2} = \frac{500 + 350 + 300 + 600}2 = \frac{1750}2 = \boxed{\boxed{875}}</math>.<br />
<br />
=== Solution 2 ===<br />
Redefine the points in the same manner as the last time (<math>\triangle AB'C'</math>, intersect at <math>D</math>, <math>E</math>, and <math>F</math>). This time, notice that <math>[ADEF] = [\triangle AB'C'] - ([\triangle ADC'] + [\triangle EFB']</math>.<br />
<br />
The area of <math>[\triangle AB'C'] = [\triangle ABC]</math>. The [[altitude]] of <math>\triangle ABC</math> is clearly <math>10 \tan 75 = 10 \tan (30 + 45)</math>. The [[trigonometric identity|tangent addition rule]] yields <math>10(2 + \sqrt{3})</math> (see above). Thus, <math>[\triangle ABC] = \frac{1}{2} 20 \cdot (20 + 10\sqrt{3}) = 200 + 100\sqrt{3}</math>. <br />
<br />
The area of <math>[\triangle ADC']</math> (with a side on the y-axis) can be found by splitting it into two triangles, <math>30-60-90</math> and <math>15-75-90</math> [[right triangle]]s. <math>AC' = AC = \frac{10}{\sin 15}</math>. The [[trigonometric identity|sine subtraction rule]] shows that <math>\frac{10}{\sin 15} = \frac{10}{\frac{\sqrt{6} - \sqrt{2}}4} = \frac{40}{\sqrt{6} - \sqrt{2}} = 10(\sqrt{6} + \sqrt{2})</math>. <math>AC'</math>, in terms of the height of <math>\triangle ADC'</math>, is equal to <math>h(\sqrt{3} + \tan 75) = h(\sqrt{3} + 2 + \sqrt{3})</math>. <br />
<center><math>\begin{align*}<br />
[ADC'] &= \frac 12 AC' \cdot h \\<br />
&= \frac 12 (10\sqrt{6} + 10\sqrt{2})\left(\frac{10\sqrt{6} + 10\sqrt{2}}{2\sqrt{3} + 2}\right) \\<br />
&= \frac{(800 + 400\sqrt{3})}{(2 + \sqrt{3})}\cdot\frac{2 - \sqrt{3}}{2-\sqrt{3}} \\<br />
&= \frac{400\sqrt{3} + 400}8 = 50\sqrt{3} + 50<br />
\end{align*}</math></center><br />
<br />
The area of <math>[\triangle EFB']</math> was found in the previous solution to be <math>- 500\sqrt{2} + 400\sqrt{3} - 300\sqrt{6} +750</math>. <br />
<br />
Therefore, <math>[ADEF] </math> <math>= (200 + 100\sqrt{3}) - \left((50 + 50\sqrt{3}) + (-500\sqrt{2} + 400\sqrt{3} - 300\sqrt{6} +750)\right)</math> <math>= 500\sqrt{2} - 350\sqrt{3} + 300\sqrt{6} - 600</math>, and our answer is <math>\boxed{875}</math>.<br />
<br />
=== Solution 3 ===<br />
[[Image:AIME I 2007-12b.png|left]] <br />
<br />
Call the points of the intersections of the triangles <math>D</math>, <math>E</math>, and <math>F</math> as noted in the diagram (the points are different from those in the diagram for solution 1). <math>\overline{AD}</math> [[bisect]]s <math>\angle EDE'</math>.<br />
<br />
Through [[HL]] congruency, we can find that <math>\triangle AED</math> is [[congruent]] to <math>\triangle AE'D</math>. This divides the region <math>AEDF</math> (which we are trying to solve for) into two congruent triangles and an [[isosceles triangle|isosceles]] [[right triangle]]. <br />
<center><math>AE = 20 \cos 15 = 20 \cos (45 - 30) = 20 \cdot \frac{\sqrt{6} + \sqrt{2}}{4} = 5\sqrt{6} + 5\sqrt{2}</math></center><br />
Since <math>FE' = AE' = AE</math>, we find that <math>[AE'F] = \frac 12 (5\sqrt{6} + 5\sqrt{2})^2 = 100 + 50\sqrt{3}</math>.<br />
<br />
Now, we need to find <math>[AED] = [AE'D]</math>. The acute angles of the triangles are <math>\frac{15}{2}</math> and <math>90 - \frac{15}{2}</math>. By repeated application of the [[trigonometric identity|half-angle formula]], we can find that <math>\tan \frac{15}{2} = \sqrt{2} - \sqrt{3} + \sqrt{6} - 2</math>.<br />
<br />
The area of <math>[AED] = \frac 12 \left(20 \cos 15\right)^2 \left(\tan \frac{15}{2}\right)</math>. Thus, <math>[AED] + [AE'D] = 2\left(\frac 12((5\sqrt{6} + 5\sqrt{2})^2 \cdot (\sqrt{2} - \sqrt{3} + \sqrt{6} - 2))\right)</math>, which eventually simplifies to <math>500\sqrt{2} - 350\sqrt{3} + 300\sqrt{6} - 600</math>. <br />
<br />
Adding them together, we find that the solution is <math>[AEDF] = [AE'F] + [AED] + [AE'D]</math> <math>= 100 + 50\sqrt{3} + 500\sqrt{2} - 350\sqrt{3} + 300\sqrt{6} - 600=</math> <math>= 500\sqrt{2} - 350\sqrt{3} + 300\sqrt{6} - 600</math>, and the answer is <math>\boxed{875}</math>.<br />
<br />
=== Solution 4 ===<br />
From the given information, calculate the coordinates of all the points (by finding the equations of the lines, equating). Then, use the [[shoelace]] method to calculate the area of the intersection.<br />
<br />
*<math>\overline{AC}</math>: <math>y = \sqrt{3}x</math><br />
*<math>\overline{AB'}</math>: <math>y = (\tan 15) x = \frac{\sqrt{6} - \sqrt{2}}{4}x</math><br />
*<math>\overline{BC}</math>: It passes thru <math>(20,0)</math>, and has a slope of <math>-\tan75 = -\frac{\sqrt{6} + \sqrt{2}}{4}</math>. The equation of its line is <math>y = -\frac{\sqrt{6} + \sqrt{2}}{4}x + 5\sqrt{6} + 5\sqrt{2}</math>. <br />
*<math>\overline{B'C'}</math>: <math>AC' = AC = \frac{10}{\sin 75} = 10\sqrt{6} + 10\sqrt{2}</math>, so it passes thru point <math>(0, 10\sqrt{6} + 10\sqrt{2})</math>. It has a slope of <math>-\tan 60 = -\sqrt{3}</math>. So the equation of its line is <math>y = -\sqrt{3}x + 10(\sqrt{6} + \sqrt{2})</math>.<br />
<br />
Now, we can equate the equations to find the intersections of all the points.<br />
<br />
*<math>A (0,0)</math><br />
<br />
*<math>D</math> is the intersection of <math>\overline{AB'},\ \overline{B'C'}</math>. <math>\frac{\sqrt{6} - \sqrt{2}}{4}x = -\sqrt{3}x + 10(\sqrt{6} + \sqrt{2})</math>. Therefore, <math>x = \frac{40\sqrt{6} + 40\sqrt{2}}{\sqrt{6} - \sqrt{2} + 4\sqrt{3}}</math>.<br />
<br />
*<math>E</math> is the intersection of <math>\overline{AB'},\ \overline{BC}</math>. <math>\frac{\sqrt{6} - \sqrt{2}}{4}x = -\frac{\sqrt{6} + \sqrt{2}}{4}x + 5\sqrt{6} + 5\sqrt{2}</math>. Therefore, <math>x = 10 + \frac{10\sqrt{3}}{3}</math>.<br />
<br />
*<math>F</math> is the intersection of <math>\overline{AC},\ \overline{B'C'}</math>. <math>\sqrt{3}x = -\sqrt{3}x + 10(\sqrt{6} + \sqrt{2})</math>. Therefore, <math>x = \frac{15\sqrt{2} + 5\sqrt{6}}{3}</math>, and <math>y = 5\sqrt{6} + 5\sqrt{2}</math>.<br />
<br />
We take these points and tie them together by shoelace, and the answer should come out to be <math>\boxed{875}</math>.<br />
<br />
== See also ==<br />
{{AIME box|year=2007|n=I|num-b=11|num-a=13}}<br />
<br />
[[Category:Intermediate Geometry Problems]]</div>Jtanmanhttps://artofproblemsolving.com/wiki/index.php?title=2005_AMC_12B_Problems/Problem_25&diff=304652005 AMC 12B Problems/Problem 252009-02-24T02:39:04Z<p>Jtanman: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
Six ants simultaneously stand on the six [[vertex|vertices]] of a regular [[octahedron]], with each ant at a different vertex. Simultaneously and independently, each ant moves from its vertex to one of the four adjacent vertices, each with equal [[probability]]. What is the probability that no two ants arrive at the same vertex?<br />
<br />
<math>\mathrm{(A)}\ \frac {5}{256}<br />
\qquad\mathrm{(B)}\ \frac {21}{1024}<br />
\qquad\mathrm{(C)}\ \frac {11}{512}<br />
\qquad\mathrm{(D)}\ \frac {23}{1024}<br />
\qquad\mathrm{(E)}\ \frac {3}{128}</math><br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
We approach this problem by counting the number of ways ants can do their desired migration, and then multiple this number by the probability that each case occurs.<br />
<br />
Let the octahedron be <math>ABCDEF</math>, with points <math>B,C,D,E</math> [[coplanar]]. Then the ant from <math>A</math> and the ant from <math>F</math> must move to plane <math>BCDE</math>. Suppose, without loss of generality, that the ant from <math>A</math> moved to point <math>B</math>. Then, we must consider three cases.<br />
<br />
<br />
<br />
*Case 1: Ant from point <math>F</math> moved to point <math>C</math><br />
On the plane, points <math>B</math> and <math>C</math> are taken. The ant that moves to D can come from either <math>E</math> or <math>C</math>. The ant that moves to <math>E</math> can come from either <math>B</math> or <math>D</math>. Once these two ants are fixed, the other two ants must migrate to the "poles" of the octahedron, points <math>A</math> and <math>F</math>. Thus, there are two degrees of freedom in deciding which ant moves to <math>D</math>, two degrees of freedom in deciding which ant moves to <math>E</math>, and two degrees of freedom in deciding which ant moves to <math>A</math>. Hence, there are <math>2 \times 2 \times 2=8</math> ways the ants can move to different points.<br />
<br />
<br />
*Case 2: Ant from point <math>F</math> moved to point <math>D</math><br />
On the plane, points <math>B</math> and <math>D</math> are taken. The ant that moves to C must be from <math>B</math> or <math>D</math>, but the ant that moves to <math>E</math> must also be from <math>B</math> or <math>D</math>. The other two ants, originating from points <math>C</math> and <math>E</math>, must move to the poles. Therefore, there are two degrees of freedom in deciding which ant moves to <math>C</math> and two degrees of freedom in choosing which ant moves to <math>A</math>. Hence, there are <math>2 \times 2=4</math> ways the ants can move to different points.<br />
<br />
<br />
*Case 3: Ant from point <math>F</math> moved to point <math>E</math><br />
By symmetry to Case 1, there are <math>8</math> ways the ants can move to different points.<br />
<br />
<br />
<br />
Given a point <math>B</math>, there is a total of <math>8+4+8=20</math> ways the ants can move to different points. We oriented the square so that point <math>B</math> was defined as the point to which the ant from point <math>A</math> moved. Since the ant from point <math>A</math> can actually move to four different points, there is a total of <math>4 \times 20=80</math> ways the ants can move to different points.<br />
<br />
Each ant acts independently, having four different points to choose from. Hence, each ant has probability <math>1/4</math> of moving to the desired location. Since there are six ants, the probability of each case occuring is <math>\frac{1}{4^6} = \frac{1}{4096}</math>. Thus, the desired answer is <math>\frac{80}{4096}= \boxed{\frac{5}{256}} \Rightarrow \mathrm{(A)}</math>.<br />
<br />
=== Solution 2 ===<br />
Let <math>f(n)</math> be the number of [[cycle]]s of length <math>n</math> the can be walked among the vertices of an octahedron. For example, <math>f(3)</math> would represent the number of ways in which an ant could navigate <math>2</math> vertices and then return back to the original spot. Since an ant cannot stay still, <math>f(1) = 0</math>. We also easily see that <math>f(2) = 1, f(3) = 2</math>. <br />
<br />
Now consider any four vertices of the octahedron. All four vertices will be connected by edges except for one pair. Let’s think of this as a [[square]] with one diagonal (from top left to bottom right). <br />
<center><asy><br />
size(30);<br />
defaultpen(0.6);<br />
pair A = (0,0), B=(5,0), C=(5,5), D=(0,5);<br />
draw(A--B--C--D--cycle); <br />
draw(B--D);<br />
</asy></center><br />
Suppose an ant moved across this diagonal; then the ant at the other end can only move across the diagonal (which creates 2-cycle, bad) or it can move to another vertex, but then the ant at that vertex must move to the spot of the original ant (which creates 3-cycle, bad). Thus none of the ants can navigate the diagonal and can either shift clockwise or counterclockwise, and so <math>f(4) = 2</math>.<br />
<br />
For <math>f(6)</math>, consider an ant at the top of the octahedron. It has four choices. Afterwards, it can either travel directly to the bottom, and then it has <math>2</math> ways back up, or it can travel along the sides and then go to the bottom, of which simple counting gives us <math>6</math> ways back up. Hence, this totals <math>4 \times (2+6) = 32</math>.<br />
<br />
<br />
<br />
Now, the number of possible ways is given by the sum of all possible cycles,<br />
<cmath>a \cdot f(2) \cdot f(2) \cdot f(2) + b \cdot f(2) \cdot f(4) + c \cdot f(3) \cdot f(3) + d \cdot f(6)</cmath><br />
<br />
where the [[coefficient]]s represent the number of ways we can configure these cycles. To find <math>a</math>, fix any face, there are <math>4</math> adjacent faces to select from to complete the cycle. From the four remaining faces there are only <math>2</math> ways to create cycles, hence <math>a = 8</math>.<br />
<br />
To find <math>b</math>, each cycle of <math>2</math> faces is distinguished by their common edge, and there are <math>12</math> edges, so <math>b = 12</math>.<br />
<br />
To find <math>c</math>, each three-cycle is distinguished by the vertex, and there are <math>8</math> edges. However, since the two three-cycles are indistinguishable, <math>c = 8/2 = 4</math>.<br />
<br />
Clearly <math>d = 1</math>. Finally,<br />
<br />
<cmath>8(1)(1)(1) + 12(1)(2) + 4(2)(2) + (32) = 80</cmath><br />
<br />
Each bug has <math>4</math> possibilities to choose from, so the probability is <math>\frac{80}{4^6} = \frac{5}{256}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2005|num-b=24|after=Last question|ab=B}}<br />
<br />
[[Category:Intermediate Combinatorics Problems]]</div>Jtanmanhttps://artofproblemsolving.com/wiki/index.php?title=2005_AMC_12B_Problems/Problem_25&diff=304642005 AMC 12B Problems/Problem 252009-02-24T02:37:45Z<p>Jtanman: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
Six ants simultaneously stand on the six [[vertex|vertices]] of a regular [[octahedron]], with each ant at a different vertex. Simultaneously and independently, each ant moves from its vertex to one of the four adjacent vertices, each with equal [[probability]]. What is the probability that no two ants arrive at the same vertex?<br />
<br />
<math>\mathrm{(A)}\ \frac {5}{256}<br />
\qquad\mathrm{(B)}\ \frac {21}{1024}<br />
\qquad\mathrm{(C)}\ \frac {11}{512}<br />
\qquad\mathrm{(D)}\ \frac {23}{1024}<br />
\qquad\mathrm{(E)}\ \frac {3}{128}</math><br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
We approach this problem by counting the number of ways ants can do their desired migration, and then multiple this number by the probability that each case occurs.<br />
<br />
Let the octahedron be <math>ABCDEF</math>, with points <math>B,C,D,E</math> [[coplanar]]. Then the ant from <math>A</math> and the ant from <math>F</math> must move to plane <math>BCDE</math>. Suppose, without loss of generality, that the ant from <math>A</math> moved to point <math>B</math>. Then, we must consider three cases.<br />
<br />
<br />
<br />
*Case 1: Ant from point <math>F</math> moved to point <math>C</math><br />
On the plane, points <math>B</math> and <math>C</math> are taken. The ant that moves to D can come from either <math>E</math> or <math>C</math>. The ant that moves to <math>E</math> can come from either <math>B</math> or <math>D</math>. Once these two ants are fixed, the other two ants must migrate to the "poles" of the octahedron, points <math>A</math> and <math>F</math>. Thus, there are two degrees of freedom in deciding which ant moves to <math>D</math>, two degrees of freedom in deciding which ant moves to <math>C</math>, and two degrees of freedom in deciding which ant moves to <math>A</math>. Hence, there are <math>2 \times 2 \times 2=8</math> ways the ants can move to different points.<br />
<br />
<br />
*Case 2: Ant from point <math>F</math> moved to point <math>D</math><br />
On the plane, points <math>B</math> and <math>D</math> are taken. The ant that moves to C must be from <math>B</math> or <math>D</math>, but the ant that moves to <math>E</math> must also be from <math>B</math> or <math>D</math>. The other two ants, originating from points <math>C</math> and <math>E</math>, must move to the poles. Therefore, there are two degrees of freedom in deciding which ant moves to <math>C</math> and two degrees of freedom in choosing which ant moves to <math>A</math>. Hence, there are <math>2 \times 2=4</math> ways the ants can move to different points.<br />
<br />
<br />
*Case 3: Ant from point <math>F</math> moved to point <math>E</math><br />
By symmetry to Case 1, there are <math>8</math> ways the ants can move to different points.<br />
<br />
<br />
<br />
Given a point <math>B</math>, there is a total of <math>8+4+8=20</math> ways the ants can move to different points. We oriented the square so that point <math>B</math> was defined as the point to which the ant from point <math>A</math> moved. Since the ant from point <math>A</math> can actually move to four different points, there is a total of <math>4 \times 20=80</math> ways the ants can move to different points.<br />
<br />
Each ant acts independently, having four different points to choose from. Hence, each ant has probability <math>1/4</math> of moving to the desired location. Since there are six ants, the probability of each case occuring is <math>\frac{1}{4^6} = \frac{1}{4096}</math>. Thus, the desired answer is <math>\frac{80}{4096}= \boxed{\frac{5}{256}} \Rightarrow \mathrm{(A)}</math>.<br />
<br />
=== Solution 2 ===<br />
Let <math>f(n)</math> be the number of [[cycle]]s of length <math>n</math> the can be walked among the vertices of an octahedron. For example, <math>f(3)</math> would represent the number of ways in which an ant could navigate <math>2</math> vertices and then return back to the original spot. Since an ant cannot stay still, <math>f(1) = 0</math>. We also easily see that <math>f(2) = 1, f(3) = 2</math>. <br />
<br />
Now consider any four vertices of the octahedron. All four vertices will be connected by edges except for one pair. Let’s think of this as a [[square]] with one diagonal (from top left to bottom right). <br />
<center><asy><br />
size(30);<br />
defaultpen(0.6);<br />
pair A = (0,0), B=(5,0), C=(5,5), D=(0,5);<br />
draw(A--B--C--D--cycle); <br />
draw(B--D);<br />
</asy></center><br />
Suppose an ant moved across this diagonal; then the ant at the other end can only move across the diagonal (which creates 2-cycle, bad) or it can move to another vertex, but then the ant at that vertex must move to the spot of the original ant (which creates 3-cycle, bad). Thus none of the ants can navigate the diagonal and can either shift clockwise or counterclockwise, and so <math>f(4) = 2</math>.<br />
<br />
For <math>f(6)</math>, consider an ant at the top of the octahedron. It has four choices. Afterwards, it can either travel directly to the bottom, and then it has <math>2</math> ways back up, or it can travel along the sides and then go to the bottom, of which simple counting gives us <math>6</math> ways back up. Hence, this totals <math>4 \times (2+6) = 32</math>.<br />
<br />
<br />
<br />
Now, the number of possible ways is given by the sum of all possible cycles,<br />
<cmath>a \cdot f(2) \cdot f(2) \cdot f(2) + b \cdot f(2) \cdot f(4) + c \cdot f(3) \cdot f(3) + d \cdot f(6)</cmath><br />
<br />
where the [[coefficient]]s represent the number of ways we can configure these cycles. To find <math>a</math>, fix any face, there are <math>4</math> adjacent faces to select from to complete the cycle. From the four remaining faces there are only <math>2</math> ways to create cycles, hence <math>a = 8</math>.<br />
<br />
To find <math>b</math>, each cycle of <math>2</math> faces is distinguished by their common edge, and there are <math>12</math> edges, so <math>b = 12</math>.<br />
<br />
To find <math>c</math>, each three-cycle is distinguished by the vertex, and there are <math>8</math> edges. However, since the two three-cycles are indistinguishable, <math>c = 8/2 = 4</math>.<br />
<br />
Clearly <math>d = 1</math>. Finally,<br />
<br />
<cmath>8(1)(1)(1) + 12(1)(2) + 4(2)(2) + (32) = 80</cmath><br />
<br />
Each bug has <math>4</math> possibilities to choose from, so the probability is <math>\frac{80}{4^6} = \frac{5}{256}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2005|num-b=24|after=Last question|ab=B}}<br />
<br />
[[Category:Intermediate Combinatorics Problems]]</div>Jtanmanhttps://artofproblemsolving.com/wiki/index.php?title=2005_AMC_12B_Problems/Problem_25&diff=304632005 AMC 12B Problems/Problem 252009-02-24T02:37:12Z<p>Jtanman: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
Six ants simultaneously stand on the six [[vertex|vertices]] of a regular [[octahedron]], with each ant at a different vertex. Simultaneously and independently, each ant moves from its vertex to one of the four adjacent vertices, each with equal [[probability]]. What is the probability that no two ants arrive at the same vertex?<br />
<br />
<math>\mathrm{(A)}\ \frac {5}{256}<br />
\qquad\mathrm{(B)}\ \frac {21}{1024}<br />
\qquad\mathrm{(C)}\ \frac {11}{512}<br />
\qquad\mathrm{(D)}\ \frac {23}{1024}<br />
\qquad\mathrm{(E)}\ \frac {3}{128}</math><br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
We approach this problem by counting the number of ways ants can do their desired migration, and then multiple this number by the probability that each case occurs.<br />
<br />
Let the octahedron be <math>ABCDEF</math>, with points <math>B,C,D,E</math> [[coplanar]]. Then the ant from <math>A</math> and the ant from <math>F</math> must move to plane <math>BCDE</math>. Suppose, without loss of generality, that the ant from <math>A</math> moved to point <math>B</math>. Then, we must consider three cases.<br />
<br />
<br />
<br />
*Case 1: Ant from point <math>F</math> moved to point <math>C</math><br />
On the plane, points <math>B</math> and <math>C</math> are taken. The ant that moves to D can come from either <math>E</math> or <math>C</math>. The ant that moves to E can come from either <math>B</math> or <math>D</math>. Once these two ants are fixed, the other two ants must migrate to the "poles" of the octahedron, points <math>A</math> and <math>F</math>. Thus, there are two degrees of freedom in deciding which ant moves to <math>D</math>, two degrees of freedom in deciding which ant moves to <math>C</math>, and two degrees of freedom in deciding which ant moves to <math>A</math>. Hence, there are <math>2 \times 2 \times 2=8</math> ways the ants can move to different points.<br />
<br />
<br />
*Case 2: Ant from point <math>F</math> moved to point <math>D</math><br />
On the plane, points <math>B</math> and <math>D</math> are taken. The ant that moves to C must be from <math>B</math> or <math>D</math>, but the ant that moves to <math>E</math> must also be from <math>B</math> or <math>D</math>. The other two ants, originating from points <math>C</math> and <math>E</math>, must move to the poles. Therefore, there are two degrees of freedom in deciding which ant moves to <math>C</math> and two degrees of freedom in choosing which ant moves to <math>A</math>. Hence, there are <math>2 \times 2=4</math> ways the ants can move to different points.<br />
<br />
<br />
*Case 3: Ant from point <math>F</math> moved to point <math>E</math><br />
By symmetry to Case 1, there are <math>8</math> ways the ants can move to different points.<br />
<br />
<br />
<br />
Given a point <math>B</math>, there is a total of <math>8+4+8=20</math> ways the ants can move to different points. We oriented the square so that point <math>B</math> was defined as the point to which the ant from point <math>A</math> moved. Since the ant from point <math>A</math> can actually move to four different points, there is a total of <math>4 \times 20=80</math> ways the ants can move to different points.<br />
<br />
Each ant acts independently, having four different points to choose from. Hence, each ant has probability <math>1/4</math> of moving to the desired location. Since there are six ants, the probability of each case occuring is <math>\frac{1}{4^6} = \frac{1}{4096}</math>. Thus, the desired answer is <math>\frac{80}{4096}= \boxed{\frac{5}{256}} \Rightarrow \mathrm{(A)}</math>.<br />
<br />
=== Solution 2 ===<br />
Let <math>f(n)</math> be the number of [[cycle]]s of length <math>n</math> the can be walked among the vertices of an octahedron. For example, <math>f(3)</math> would represent the number of ways in which an ant could navigate <math>2</math> vertices and then return back to the original spot. Since an ant cannot stay still, <math>f(1) = 0</math>. We also easily see that <math>f(2) = 1, f(3) = 2</math>. <br />
<br />
Now consider any four vertices of the octahedron. All four vertices will be connected by edges except for one pair. Let’s think of this as a [[square]] with one diagonal (from top left to bottom right). <br />
<center><asy><br />
size(30);<br />
defaultpen(0.6);<br />
pair A = (0,0), B=(5,0), C=(5,5), D=(0,5);<br />
draw(A--B--C--D--cycle); <br />
draw(B--D);<br />
</asy></center><br />
Suppose an ant moved across this diagonal; then the ant at the other end can only move across the diagonal (which creates 2-cycle, bad) or it can move to another vertex, but then the ant at that vertex must move to the spot of the original ant (which creates 3-cycle, bad). Thus none of the ants can navigate the diagonal and can either shift clockwise or counterclockwise, and so <math>f(4) = 2</math>.<br />
<br />
For <math>f(6)</math>, consider an ant at the top of the octahedron. It has four choices. Afterwards, it can either travel directly to the bottom, and then it has <math>2</math> ways back up, or it can travel along the sides and then go to the bottom, of which simple counting gives us <math>6</math> ways back up. Hence, this totals <math>4 \times (2+6) = 32</math>.<br />
<br />
<br />
<br />
Now, the number of possible ways is given by the sum of all possible cycles,<br />
<cmath>a \cdot f(2) \cdot f(2) \cdot f(2) + b \cdot f(2) \cdot f(4) + c \cdot f(3) \cdot f(3) + d \cdot f(6)</cmath><br />
<br />
where the [[coefficient]]s represent the number of ways we can configure these cycles. To find <math>a</math>, fix any face, there are <math>4</math> adjacent faces to select from to complete the cycle. From the four remaining faces there are only <math>2</math> ways to create cycles, hence <math>a = 8</math>.<br />
<br />
To find <math>b</math>, each cycle of <math>2</math> faces is distinguished by their common edge, and there are <math>12</math> edges, so <math>b = 12</math>.<br />
<br />
To find <math>c</math>, each three-cycle is distinguished by the vertex, and there are <math>8</math> edges. However, since the two three-cycles are indistinguishable, <math>c = 8/2 = 4</math>.<br />
<br />
Clearly <math>d = 1</math>. Finally,<br />
<br />
<cmath>8(1)(1)(1) + 12(1)(2) + 4(2)(2) + (32) = 80</cmath><br />
<br />
Each bug has <math>4</math> possibilities to choose from, so the probability is <math>\frac{80}{4^6} = \frac{5}{256}</math>.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2005|num-b=24|after=Last question|ab=B}}<br />
<br />
[[Category:Intermediate Combinatorics Problems]]</div>Jtanman