Maths Olympiad Prep

Library / /39 of 62

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Jody has 6 distinguishable balls and 6 distinguishable sticks, all of the same length. How many ways are there to use the sticks to connect the balls so that two disjoint non-interlocking triangles are formed? Consider rotations and reflections of the same arrangement to be indistinguishable.

Solutions — 2

Solution 1

Solution:

For two disjoint triangles to be formed, three of the balls must be connected into a triangle by three of the sticks, and the three remaining balls must be connected by the three remaining sticks.

There are (63)\binom{6}{3} ways to pick the 3 balls for the first triangle. Note that once we choose the 3 balls for the first triangle, the remaining 3 balls must form the vertices of the second triangle.

Now that we have determined the vertices of each triangle, we can assign the 6 sticks to the 6 total edges in the two triangles. Because any ordering of the 6 sticks works, there are 6!=7206! = 720 total ways to assign the sticks as edges.

Finally, because the order of the two triangles doesn't matter (i.e. our initial choice of 3 balls could have been used for the second triangle), we must divide by 2 to correct for overcounting. Hence the final answer is (63)6!/2=7200\binom{6}{3} \cdot 6! / 2 = 7200.

Solution 2

Solution:

First, we ignore all the symmetries in the problem. There are then 6!6! ways to arrange the balls and 6!6! ways to arrange the sticks. However, each triangle can be rotated or reflected, so we have overcounted by a factor of 626^{2}. Moreover, the triangles can be swapped, so we must also divide by 2. Thus the answer is
(6!)2622=12022=7200 \frac{(6!)^{2}}{6^{2} \cdot 2} = \frac{120^{2}}{2} = 7200

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.