HMMT 十一月 2009 · GEN1 赛 · 第 9 题
HMMT November 2009 — GEN1 Round — Problem 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 ) such that x and y are integers and 1 ≤ x, y ≤ 26. Find the number of ways to choose a convex subset of S that contains exactly 98 points.
解析
- [ 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 ) such that x and y are integers and 1 ≤ x, y ≤ 26. Find the number of ways to choose a convex subset of S that contains exactly 98 points. Answer: 4958 For this problem, let n = 26. A convex set may be divided into four subsets: a set of points with maximal y coordinate, a set of points with minimal y coordinate, the points to the left of one of these subsets, and the points to the right of one of these subsets (the left, top, right, and bottom of the corresponding convex polygon). Each of these four parts contains at most n points. (All points in the top or bottom have distinct x coordinates while all points in the left or right have distinct y coordinates.) Moreover, there are four corners each of which is contained in two of these regions. This implies that at most 4 n − 4 distinct points are in any convex set. To find a set of size 4 n − 6 we can remove 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. ( ) 100 Any of the = 4950 sets of 98 points with either x or y coordinate either 1 or 26 have this property. 98 Suppose instead that some of the points have x coordinate and y coordinate both different from 1 and from 26. In this case we can check that it is impossible for one side to have n − 2 points. If two opposite sides (top/bottom or left/right) have n − 1 points, then we obtain all the points on the boundary of an n − 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.