HMMT 十一月 2014 · 团队赛 · 第 5 题

英文解析

5. [ 5 ] Let A, B, C, D, E be five points on a circle; some segments are drawn between the points so that
   ( )
   each of the = 10 pairs of points is connected by either zero or one segments. Determine the number 5
   of sets of segments that can be drawn such that:2
   • It is possible to travel from any of the five points to any other of the five points along drawnsegments.
   • It is possible to divide the five points into two nonempty sets S and T such that each segmenthas one endpoint in S and the other endpoint in T .
   Team Round
   Answer: 195 First we show that we can divide the five points into sets S and T according to the
   ′ ′
   second condition in only one way. Assume that we can divide the five points into S ∪ T and S ∪ T .
   ′ ′ ′ ′ ′ ′
   Then, let A = S ∩ S, B = S ∩ T, C = T ∩ S , and D = T ∩ T . Since S, T and S , T partition the setof five points, A, B, C, D also partition the set of five points.
   ′
   Now, according to the second condition, there can only be segments between S and T and between S
   ′
   and T . Therefore, the only possible segments are between points in A and D , or between points in Band C . Since, according to the first condition, the points are all connected via segments, it must be
   ′ ′
   that A = D = ∅ or B = C = ∅ . If A = D = ∅ , then it follows that S = T and T = S . Otherwise, if
   ′ ′ ′ ′
   B = C = ∅ , then S = S and T = T . In either case, S, T and S , T are the same partition of the fivepoints, as desired.
   We now determine the possible sets of segments with regard to the sets S and T .
   ( )
   Case 1 : the two sets contain 4 points and 1 point. Then, there are = 5 ways to partition the points 5
   in this manner. Moreover, the 1 point (in its own set) must be connected to each of the other 4 points,1
   and these are the only possible segments. Therefore, there is only 1 possible set of segments, which,
   combining with the 5 ways of choosing the sets, gives 5 possible sets of segments.
   ( )
   Case 2 : the two sets contain 3 points and 2 points. Then, there are = 10 ways to partition the 5
   points in this manner. Let S be the set containing 3 points and T the set containing 2 points. We 2
   consider the possible degrees of the points in T .
   • If both points have degree 3, then each point must connect to all points in S , and the five pointsare connected via segments. So the number of possible sets of segments is 1.
   • If the points have degree 3 and 2. Then, we can swap the points in 2 ways, and, for the point
   ( )
   with degree 2, we can choose the elements of S it connects to in = 3 ways. In each case, the 3
   five points are guaranteed to be connected via segments. Hence 6 ways.2
   • If the points have degree 3 and 1. Similarly, we can swap the points in 2 ways and connect the
   ( )
   point with degree 1 to the elements of S in = 3 ways. Since all five points are connected in 3
   all cases, we have 6 ways.1
   • If both points have degree 2. Then, in order for the five points to be connected, the two pointsmust connect to a common element of S . Call this common element A . Then, for the other twoelements of S , each one must be connected to exactly one element of T . We can choose A in 3
   ways, and swap the correspondence between the other two elements of S with the elements of Tin 2 ways. Hence 6 ways.
   • If the points have degree 2 and 1. Then, in order to cover S , the point with degree 2 must connectto 2 points in S , and the point with degree 1 to the remaining point in S . But then, the fivepoints will not be connected via segments, an impossibility.
   • If both points have degree 1. Then, similar to the previous case, it is impossible to cover all the
   3 points in S with only 2 segments, a contradiction.
   Combining the subcases, we have 1 + 6 + 6 + 6 = 19 possible sets of segments with regard to a partition.
   With 10 possible partitions, we have a total of 19 · 10 = 190 possible sets of segments.
   Finally, combining this number with the 5 possibilities from case 1, we have a total of 5 + 190 = 195
   possibilities, as desired.