HMMT 二月 2010 · COMB 赛 · 第 7 题

英文解析

7. [ 6 ] For each integer x with 1 ≤ x ≤ 10, a point is randomly placed at either ( x, 1) or ( x, − 1) with equalprobability. What is the expected area of the convex hull of these points? Note: the convex hull of afinite set is the smallest convex polygon containing it.
   1793
   Answer: Let n = 10. Given a random variable X , let E ( X ) denote its expected value. If all
   2128
   points are collinear, then the convex hull has area zero. This happens with probability (either allnpoints are at y = 1 or all points are at y = − 1). Otherwise, the points form a trapezoid with height 2
   2 (the trapezoid is possibly degenerate, but this won’t matter for our calculation). Let x be the
   1 ,lx -coordinate of the left-most point at y = 1 and x be the x -coordinate of the right-most point at
   1 ,ry = 1. Define x and x similarly for y = − 1. Then the area of the trapezoid is − 1 ,l − 1 ,r
   ( x − x ) + ( x − x )
   1 ,r 1 ,l − 1 ,r − 1 ,l
   2 · = x + x − x − x .
   1 ,r − 1 ,r 1 ,l − 1 ,l
   The expected area of the convex hull (assuming the points are not all collinear) is then, by linearity of 2
   expectation,
   E ( x + x − x − x ) = E ( x ) + E ( x ) − E ( x ) − E ( x ) .
   1 ,r − 1 ,r 1 ,l − 1 ,l 1 ,r − 1 ,r 1 ,l − 1 ,l
   Combinatorics Subject Test
   We need only compute the expected values given in the above equation. Note that x is equal to
   1 ,rk − 1 n − 1
   2 2 − 1
   k with probability , except that it is equal to n with probability (the denominator isn n
   2 − 2 2 − 2
   n n
   2 − 2 instead of 2 because we need to exclude the case where all points are collinear). Therefore, theexpected value of x is equal to
   1 ,r
   (( ) )
   ∑nk − 11
   k · 2 − n · 1
   2 − 2 nk =1
   (( ) ( ) )
   n − 1 n − 1 n − 11 = 1 + 2 + · · · + 2 + 2 + 4 + · · · + 2 + · · · + 2 − nn
   2 − 2
   ( ( ) )
   n n n n − 11 = (2 − 1) + (2 − 2) + · · · + 2 − 2 − nn
   2 − 2
   n n 1 = ( n · 2 − (2 − 1) − n )
   2 − 2 nn
   2 − 1 = ( n − 1)
   2 − 2 nn
   2 − 1
   Similarly, the expected value of x is also ( n − 1) . By symmetry, the expected value of both − 1 ,r n
   2 − 2
   2 − 1 nx and x is n + 1 − ( n − 1) . This says that if the points are not all collinear then the expected
   1 ,l − 1 ,l n
   2 − 2
   ( )
   2 − 1 narea is 2 · ( n − 1) − ( n + 1) . So, the expected area isn − 1
   2 − 1
   ( ) ( )
   2 2 2 − 1 n
   · 0 + 1 − · 2 · ( n − 1) − ( n + 1)
   n n n − 1
   2 2 2 − 1
   ( )
   n − 1 n
   2 − 1 2 − 1 = 2 · · ( n − 1) − ( n + 1)
   n − 1 n − 1
   2 2 − 1
   n n − 1
   ( n − 1)(2 − 1) − ( n + 1)(2 − 1) = 2 ·
   n − 1
   n − 12
   ((2 n − 2) − ( n + 1))2 + 2 = 2 ·
   n − 1 = 2 n − 6 +12
   n − 3
   1 17932
   Plugging in n = 10, we get 14 + = .
   128 128