HMMT 十一月 2012 · 团队赛 · 第 7 题
HMMT November 2012 — Team Round — Problem 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 interior of the 100-gon. Circumcircles The circumcircle of a triangle is the circle passing through all three vertices of the triangle.
解析
- [ 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 interior of the 100-gon. 4850 Answer: By linearity of expectation, the expected number of total intersections is equal to 3 the sum of the probabilities that any given intersection will occur. 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 share vertex π ( 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) are all 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 Round points that form a convex quadrilateral, exactly one of the three ways of pairing the points into two pairs (two pairs of opposite sides and the two diagonals) forms two segments that intersect inside the quadrilateral (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 twice i,j (once as ( i, j ) and once as ( j, i )), there are 9700 / 2 = 4850 distinct possible intersections, each of which occurs with probability 1 / 3, so the expected number of intersections is equal to 4850 / 3.