A square of size is given. Some of its cells are marked. It turned out that there is no convex quadrilateral with vertices at these marked points. For each natural number , find the largest value of for which this is possible.
A quadrilateral is called convex if both of its diagonals lie inside the quadrilateral.
Fig. 6
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 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 points. Suppose at least 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 -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 . It is easy to see that there are at least 2 points in this row that lie on one side of point , and similar 2 points can be found for the column. These 4 points form a convex quadrilateral.