Problem:
A set of points is convex if the points are the vertices of a convex polygon (that is, a non-selfintersecting polygon with all angles less than or equal to ). Let be the set of points such that and are integers and . Find the number of ways to choose a convex subset of that contains exactly 98 points.
Solution
Solution:
4958
For this problem, let . A convex set may be divided into four subsets: a set of points with maximal coordinate, a set of points with minimal 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 points. (All points in the top or bottom have distinct coordinates while all points in the left or right have distinct coordinates.) Moreover, there are four corners each of which is contained in two of these regions. This implies that at most distinct points are in any convex set. To find a set of size we can remove 2 additional points. Either exactly one of the top, bottom, left, or right contains exactly points or some two of them each contain exactly points.
Any of the sets of 98 points with either or coordinate either 1 or 26 have this property. Suppose instead that some of the points have coordinate and coordinate both different from 1 and from 26. In this case we can check that it is impossible for one side to have points. If two opposite sides (top/bottom or left/right) have points, then we obtain all the points on the boundary of an by rectangle (of which there are four). If two adjacent sides (any of the other pairs) have points, then we obtain the points on the boundary of an by square with the points , missing and the point added (or one of its rotations). There are an additional 4 such sets, for a total of 4958.