62nd Ukrainian National Mathematical Olympiad

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+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+2$ points. Suppose at least $n+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 $(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 $A$. It is easy to see that there are at least 2 points in this row that lie on one side of point $A$, and similar 2 points can be found for the column. These 4 points form a convex quadrilateral.