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 triangle by three of the sticks, and the three remaining balls must be connected by the three remaining sticks. ( ) 6 There are ways to pick the 3 balls for the first triangle. Note that once we choose the 3 balls for 3 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! = 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 ( ) 6 final answer is · 6! / 2 = 7200 . 3 Solution 2: First, we ignore all the symmetries in the problem. There are then 6! ways to arrange the balls and 6! ways to arrange the sticks. However, each triangle can be rotated or reflected, so we 2 have overcounted by a factor of 6 . Moreover, the triangles can be swapped, so we must also divide by