HMMT 二月 2021 · 冲刺赛 · 第 36 题
HMMT February 2021 — Guts Round — Problem 36
题目详情
- [20] A set of 6 distinct lattice points is chosen uniformly at random from the set { 1 , 2 , 3 , 4 , 5 , 6 } . Let A 4 be the expected area of the convex hull of these 6 points. Estimate N = b 10 A c . ( ⌊ ⌋) ( ) 1 / 3 | E − N | An estimate of E will receive max 0 , 20 − 20 points. 4 10
解析
- [20] A set of 6 distinct lattice points is chosen uniformly at random from the set { 1 , 2 , 3 , 4 , 5 , 6 } . Let 4 A be the expected area of the convex hull of these 6 points. Estimate N = b 10 A c . ( ⌊ ⌋) ( ) 1 / 3 | E − N | An estimate of E will receive max 0 , 20 − 20 points. 4 10 Proposed by: Milan Haiman Answer: 104552 Solution: The main tools we will use are linearity of expectation and Pick’s theorem. Note that the resulting polygon is a lattice polygon, and this the expected area A satisfies B A = I + − 1 , 2 where I is the expected number of interior points and B is the expected number of boundary points. We may now use linearity of expectation to write this as ∑ A = − 1 + E [ X ] , p 2 p ∈{ 1 , 2 ,..., 6 } where X is 1 if the point is inside the polygon, 1 / 2 if the point is on the boundary, and 0 otherwise. p Letting f ( p ) = E [ X ], we may write this by symmetry as p A = − 1 + 4 f (1 , 1) + 8 f (1 , 2) + 8 f (1 , 3) + 4 f (2 , 2) + 8 f (2 , 3) + 4 f (3 , 3) . There are many ways to continue the estimation from here; we outline one approach. Since X is (1 , 1) 1 / 2 if and only if (1 , 1) is one of the selected points (and 0 otherwise), we see 1 f (1 , 1) = . 12 On the other hand, we may estimate that a central point is exceedingly likely to be within the polygon, and guess f (3 , 3) ≈ 1. We may also estimate f (1 , y ) for y ∈ { 2 , 3 } ; such a point is on the boundary if and only if (1 , y ) is selected or (1 , z ) is selected for some z < y and for some z > y . The first event happens with probability 1 / 6, and the second event happens with some smaller probability that can be estimated by choosing the 6 points independently (without worrying about them being distinct); this works out to give the slight overestimate 1 f (1 , 2) , f (1 , 3) ≈ . 8 From here, it is not so clear how to estimate f (2 , 2) and f (2 , 3), but one way is to make f ( x, y ) somewhat linear in each component; this works out to give 1 1 f (2 , 2) ≈ , f (2 , 3) ≈ . 4 2 (In actuality the estimates we’d get would be slightly higher, but each of our estimates for f ( x, y ) up 31 until this point have been slight overestimates.) Summing these up gives us an estimate of A ≈ or 3 E = 103333, which earns 10 points. The actual value of A is 10 . 4552776 ... , and so N = 104552.