HMMT 二月 2010 · COMB 赛 · 第 7 题
HMMT February 2010 — COMB Round — Problem 7
题目详情
- [ 6 ] For each integer x with 1 ≤ x ≤ 10, a point is randomly placed at either ( x, 1) or ( x, − 1) with equal probability. What is the expected area of the convex hull of these points? Note: the convex hull of a finite set is the smallest convex polygon containing it.
解析
- [ 6 ] For each integer x with 1 ≤ x ≤ 10, a point is randomly placed at either ( x, 1) or ( x, − 1) with equal probability. What is the expected area of the convex hull of these points? Note: the convex hull of a finite 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 128 2 points are collinear, then the convex hull has area zero. This happens with probability (either all n 2 points are at y = 1 or all points are at y = − 1). Otherwise, the points form a trapezoid with height 2 (the trapezoid is possibly degenerate, but this won’t matter for our calculation). Let x be the 1 ,l x -coordinate of the left-most point at y = 1 and x be the x -coordinate of the right-most point at 1 ,r y = 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 2 The expected area of the convex hull (assuming the points are not all collinear) is then, by linearity of 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 ,r k − 1 n − 1 2 2 − 1 k with probability , except that it is equal to n with probability (the denominator is n 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, the expected value of x is equal to 1 ,r (( ) ) n ∑ 1 k − 1 k · 2 − n · 1 n 2 − 2 k =1 (( ) ( ) ) 1 n − 1 n − 1 n − 1 = 1 + 2 + · · · + 2 + 2 + 4 + · · · + 2 + · · · + 2 − n n 2 − 2 ( ( ) ) 1 n n n n − 1 = (2 − 1) + (2 − 2) + · · · + 2 − 2 − n n 2 − 2 1 n n = ( n · 2 − (2 − 1) − n ) n 2 − 2 n 2 − 1 = ( n − 1) n 2 − 2 n 2 − 1 Similarly, the expected value of x is also ( n − 1) . By symmetry, the expected value of both − 1 ,r n 2 − 2 n 2 − 1 x 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 ( ) n 2 − 1 area is 2 · ( n − 1) − ( n + 1) . So, the expected area is n − 1 2 − 1 ( ) ( ) n 2 2 2 − 1 · 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 2 n − 1 ((2 n − 2) − ( n + 1))2 + 2 = 2 · n − 1 2 1 = 2 n − 6 + n − 3 2 1 1793 Plugging in n = 10, we get 14 + = . 128 128