HMMT 十一月 2012 · 团队赛 · 第 7 题

英文解析

7. [ 8 ] Let A A . . . A be the vertices of a regular 100-gon. Let π be a randomly chosen permutation of
   1 2 100
   the numbers from 1 through 100. The segments A A , A A , . . . , A A , A Aπ (1) π (2) π (2) π (3) π (99) π (100) π (100) π (1)
   are drawn. Find the expected number of pairs of line segments that intersect at a point in the interiorof the 100-gon.
   4850
   Answer: By linearity of expectation, the expected number of total intersections is equal tothe sum of the probabilities that any given intersection will occur.3
   Let us compute the probability p that A A intersects A A (where 1 ≤ i, j ≤ 100,
   i,jπ ( i ) π ( i +1) π ( j ) π ( j +1)
   i 6 = j , and indices are taken modulo 100). Note first that if j = i + 1, then these two segments sharevertex π ( i + 1) and therefore will not intersect in the interior of the 100-gon; similarly, if i = j + 1,
   these two segments will also not intersect. On the other hand, if π ( i ), π ( i + 1), π ( j ), and π ( j + 1) areall distinct, then there is a 1 / 3 chance that A A intersects A A ; in any set of fourπ ( i ) π ( i +1) π ( j ) π ( j +1)
   Team Roundpoints that form a convex quadrilateral, exactly one of the three ways of pairing the points into twopairs (two pairs of opposite sides and the two diagonals) forms two segments that intersect inside thequadrilateral (namely, the two diagonals).
   Now, there are 100 ways to choose a value for i , and 97 ways to choose a value for j which is not i ,
   i + 1, or i − 1, there are 9700 ordered pairs ( i, j ) where p = 1 / 3. Since each pair is counted twicei,j
   (once as ( i, j ) and once as ( j, i )), there are 9700 / 2 = 4850 distinct possible intersections, each of whichoccurs with probability 1 / 3, so the expected number of intersections is equal to 4850 / 3.