Greatest number of red coloured points

Question

Problem: Let m and n be integers greater than 1. Consider an m×n rectangular grid of points in the plane. Some k of these points are coloured red in such a way that no three red points are the vertices of a right angled triangle two of whose sides are parallel to the sides of the grid. Determine the greatest possible value of k.

Please help me. I dont even know how to approach this problem. I tried small cases without any success.

Answer 1

HINT: Pick any point $p$, and color all of the other points in $p$’s row and column red; that arrangement is acceptable. Thus, you can get at least $m+n-2$ red points. Now let $P$ be an acceptable arrangment of red points. There’s no harm in assuming that $m\le n$, where $m$ is the number of rows and $n$ the number of columns.

For $r=1,\ldots,m$ let $C_r$ be the set of column numbers of points of $P$ in row $r$. Interchanging two rows of the grid does not affect the acceptability of the arrangement, so we may assume that $|C_1|\ge|C_2|\ge\ldots\ge|C_m|$. Let $\ell$ be maximal such that $|C_\ell|>1$. (Such an $\ell$ must exist; why?)

• Show that the sets $C_1,\ldots,C_\ell$ are pairwise disjoint. Let $C=\bigcup_{i=1}^\ell C_i$. Conclude that $|C|\le n$.
• Show that $P$ has at most $m-\ell$ members altogether in rows $\ell+1,\ldots,m$, and conclude that $|P|\le n+m-1$. This is almost good enough.
• Show that if $r>\ell$, then $C_r\cap C=\varnothing$. Use this to show that either $|P|=|C|=n$, or $|C|<n$ and hence $|P|<n+m-1$, so that in either case $|P|\le m+n-2$.