In an $m \cdot n$ rectangular grid of points, $k$ points are marked, such that no three marked points form a right triangle with legs parallel to the sides of the rectangular grid. What is the expression for the value of $k$ in relation to $m$ and $n$?
I've worked out that it is possible to create an arrangement with $m+n-2$ points, but how do I prove that given $m+n-1$ points, at least one right triangle is formed. Should I use pigeonhole principle, and how would I do so?