Open Contests

All vertices of squares lie on $n+1$ horizontal and $m+1$ vertical lines. Suppose that at least $n+m+1$ points are marked in the grid. Because $m>0$, the number of marked points is greater than $n+1$. Hence by the pigeonhole principle, at least one horizontal line contains more than one marked point. Hence at most $n$ marked points are alone on their horizontal lines. Similarly, at most $m$ marked points are alone on their vertical lines. Thus there exists a marked point that lies neither alone on its horizontal line nor alone on its vertical line. But then there is a right-angled triangle with vertices at marked points. So at most $n+m$ points can be marked according to the conditions of the problem.

By marking all vertices of squares of the grid that lie at the left and lower edge of the grid except for the lower left corner we have marked exactly $n+m$ points (Fig. 13 depicts the choice for a $5\times 7$ grid). Any three of the marked points either lie on a common line or are the vertices of an obtuse triangle, so the construction satisfies the conditions of the problem.



Fig. 13