62nd Ukrainian National Mathematical Olympiad

We will show that there is an example where the marked number of points satisfies the conditions of the problem. For this, we will denote the centers of all the cells in the first row and the first column, except for the center of the cell at the intersection of the first row and the first column (see Fig. 3). By simple enumeration, it is easy to see that no three marked points are vertices of a right triangle.

Suppose that this is not the maximum possible value for the number of marked points, i.e., it is possible to mark $2n-1$ centers of the marked centers in such a way that no three of them form the vertices of a right triangle. It follows that for each marked point, this is the only marked point in the row or column with this point. Let there be $a_1,a_2,...,a_n$ marked points in the columns respectively. If $a_i>1$ for some $i$, then for each of the marked points in the $i$-th column, this point is the only one in its row, otherwise a triangular rectangle will be formed. Therefore, the total number of such points for which $a_i>1$ is no more than $n$ — the total number of rows. But if there are exactly $n$ of these points, then the total number of marked points is also $n$, which does not exceed $2n-2$. Otherwise, the sum of all $a_i$ greater than one does not exceed $n-1$. On the other hand, the sum of all $a_i$ that are equal to one is also no more than $n$. If there are exactly $n$ of these points, then again all the marked points are $n$, which does not exceed $2n-2$. Thus, the number of both types of marked points is no more than $n-1$, and therefore their total number is no more than $2n-2$. Thus, there cannot be more marked points than this value.

Fig. 3