HMMT 十一月 2009 · GEN1 赛 · 第 9 题

英文解析

9. [ 7 ] A set of points is convex if the points are the vertices of a convex polygon (that is, a non-self-
   °
   intersecting polygon with all angles less than or equal to 180 ). Let S be the set of points ( x, y ) suchthat x and y are integers and 1 ≤ x, y ≤ 26. Find the number of ways to choose a convex subset of Sthat contains exactly 98 points.
   Answer: 4958 For this problem, let n = 26. A convex set may be divided into four subsets: a set ofpoints with maximal y coordinate, a set of points with minimal y coordinate, the points to the left ofone of these subsets, and the points to the right of one of these subsets (the left, top, right, and bottomof the corresponding convex polygon). Each of these four parts contains at most n points. (All pointsin the top or bottom have distinct x coordinates while all points in the left or right have distinct ycoordinates.) Moreover, there are four corners each of which is contained in two of these regions. Thisimplies that at most 4 n − 4 distinct points are in any convex set. To find a set of size 4 n − 6 we canremove 2 additional points. Either exactly one of the top, bottom, left, or right contains exactly n − 2
   points or some two of them each contain exactly n − 1 points.
   ( )
   Any of the = 4950 sets of 98 points with either x or y coordinate either 1 or 26 have this property.100
   Suppose instead that some of the points have x coordinate and y coordinate both different from 1 and 98
   from 26. In this case we can check that it is impossible for one side to have n − 2 points. If two oppositesides (top/bottom or left/right) have n − 1 points, then we obtain all the points on the boundary of ann − 1 by n rectangle (of which there are four). If two adjacent sides (any of the other pairs) have n − 1
   points, then we obtain the points on the boundary of an n by n square with the points (1 , 1), (1 , 2),
   (2 , 1) missing and the point (2 , 2) added (or one of its rotations). There are an additional 4 such sets,
   for a total of 4958.