Maths Olympiad Prep

Library / /77 of 82

Geometry Difficulty 5.7 AIME, harder Prove it United States

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 180180^{\circ}). Let SS be the set of points (x,y)(x, y) such that xx and yy are integers and 1x,y261 \leq x, y \leq 26. Find the number of ways to choose a convex subset of SS that contains exactly 98 points.

Solution

Solution:
4958

For this problem, let n=26n=26. A convex set may be divided into four subsets: a set of points with maximal yy coordinate, a set of points with minimal yy 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 nn points. (All points in the top or bottom have distinct xx coordinates while all points in the left or right have distinct yy coordinates.) Moreover, there are four corners each of which is contained in two of these regions. This implies that at most 4n44n-4 distinct points are in any convex set. To find a set of size 4n64n-6 we can remove 2 additional points. Either exactly one of the top, bottom, left, or right contains exactly n2n-2 points or some two of them each contain exactly n1n-1 points.

Any of the (10098)=4950\binom{100}{98}=4950 sets of 98 points with either xx or yy coordinate either 1 or 26 have this property. Suppose instead that some of the points have xx coordinate and yy coordinate both different from 1 and from 26. In this case we can check that it is impossible for one side to have n2n-2 points. If two opposite sides (top/bottom or left/right) have n1n-1 points, then we obtain all the points on the boundary of an n1n-1 by nn rectangle (of which there are four). If two adjacent sides (any of the other pairs) have n1n-1 points, then we obtain the points on the boundary of an nn by nn square with the points (1,1),(1,2)(1,1),(1,2), (2,1)(2,1) missing and the point (2,2)(2,2) added (or one of its rotations). There are an additional 4 such sets, for a total of 4958.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.