Olympiad Maths Prep

Library / /37 of 45

Geometry Difficulty 6.8 National olympiad Prove it Ukraine

A square of size n×nn \times n is given. Some of its 1×11 \times 1 cells are marked. It turned out that there is no convex quadrilateral with vertices at these marked points. For each natural number n3n \ge 3, find the largest value of mm for which this is possible.
A quadrilateral is called convex if both of its diagonals lie inside the quadrilateral.

Figure 1
Fig. 6

Solution

We mark two points in the corner cells of the left column, as well as all the points in some non-edge row. Then we have n+2n + 2 marked points, none of which form a vertex of a convex quadrilateral (Fig. 6).

We will show by contradiction that it is not possible to mark more than n+2n + 2 points. Suppose at least n+3n + 3 cell centers are marked. It is clear that if there are two rows, each with at least 2 marked points, then by taking exactly 2 points from each of these two rows, we obtain a convex quadrilateral. Otherwise, in at least the (n1)(n-1)-th row, no more than 1 point is marked. Then there must be a row in which at least 4 points are marked. Similarly, there must be a column in which at least 4 points are marked. Let this row and column intersect at point AA. It is easy to see that there are at least 2 points in this row that lie on one side of point AA, and similar 2 points can be found for the column. These 4 points form a convex quadrilateral.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.