HMMT 十一月 2020 · GEN 赛 · 第 3 题
HMMT November 2020 — GEN Round — Problem 3
题目详情
英文原题
- 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.
解析
英文解析
- 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.
Proposed by: Daniel Zhu
Answer: 7200
Solution 1: For two disjoint triangles to be formed, three of the balls must be connected into a triangleby three of the sticks, and the three remaining balls must be connected by the three remaining sticks.
( )
There are ways to pick the 3 balls for the first triangle. Note that once we choose the 3 balls for 6
the first triangle, the remaining 3 balls must form the vertices of the second triangle.3
Now that we have determined the vertices of each triangle, we can assign the 6 sticks to the 6 totaledges in the two triangles. Because any ordering of the 6 sticks works, there are 6! = 720 total waysto assign the sticks as edges.
Finally, because the order of the two triangles doesn’t matter (i.e. our initial choice of 3 balls couldhave been used for the second triangle), we must divide by 2 to correct for overcounting. Hence the
( )
final answer is · 6! / 2 = 7200 .6
Solution 2: First, we ignore all the symmetries in the problem. There are then 6! ways to arrange 3
the balls and 6! ways to arrange the sticks. However, each triangle can be rotated or reflected, so wehave overcounted by a factor of 6 . Moreover, the triangles can be swapped, so we must also divide by 2