[ Combinatorics (miscellaneous). [ Geometry on graph paper ]

Given a table of size $m \times n$ ( $m, n>1$ ). The centers of all cells are marked. What is the maximum number of marked centers that can be selected so that no three of them form the vertices of a right-angled triangle

#
You can reduce the table by crossing out a row that contains more than two selected points.

## Solution

Select the centers of all cells in the bottom row and the right column, except for the bottom-right corner cell. In total, $m+n-2$ points are selected, and every triplet of marked points forms an obtuse triangle.

We will prove that it is impossible to select more than $m+n-2$ cell centers. For each marked center, there are no other marked centers in its row or column. Mark this row. If all rows are marked, then no more than $m \leq m+n-2$ centers are selected. The same applies if all columns are marked.

If not all rows and not all columns are marked, then the total number of marked rows (and thus, marked centers) is no more than

$(m-1)+(n-1)=m+n-2 \ldots$

## Answer

$m+n-2$.