# Square board with $N\times N$ squares, at least $N(\sqrt N + {1\over 2})$ colored

In a square board made of $N\times N$ equal squares, at least $N(\sqrt N + {1\over 2})$ squares are colored (all other squares are, say, white). Prove that there are four colored squares that form a rectangle (the four colored squares are at the corners of some rectangle found on the board; for example, in a chess board, squares b2, b7, e2 and e7 form a rectangle while squares a1, a5, b1 and b6 do not).

I have tried to count all rectangles in the board, which is pretty easy, and sum the number of corners found in it, then to count to number a corners defined by coloured squares and make same comparison between the two but I fell short.

Any ideas?

This problem is well-known. I first met it when I was a schoolboy, learning the following problem from All-Soviet-Union mathematical competition from the year when I was born. :-)

208 a) Given a big square consisting of $7\times 7$ squares. You should mark the centres of $k$ points in such a way, that no quadruple of the marked points will be the vertices of a rectangle with the sides parallel to the sides of the given squares. What is the greatest k such that the problem has solution? b) The same problem for $13\times 13$ square.

I scanned its solution from [VE] (in Russian). About the beginning of the millennium I met a similar problem related to graphs at Erich Friedman's Math Magic. Similarly to the scanned solution of the competition problem or to the proof of Proposition 1 from my paper, we can find an upper bound on the maximal number $s=s(m,n)$ of squares which can be colored in a rectangular $m\times n$ board without forming rectangles. Namely, $s\le \frac 12(m+\sqrt{D})$, where $D=4mn^2-4mn+m^2$. In particular, if $D$ is a perfect square, that is $m=\frac{n(n-1)}{k(k-1)}$ for some natural $k$ then the upper bound proposed above becomes $s(m,n)\le km$. See also hardmath’s answer to this question about Füredi’s paper. But the board case is a bit different from the graph case and the known result do not need such subtle analysis as that done by Füredi. Namely, if there exists a Steiner system $S(2,k,n)$ then it yields $s(m,n)\ge km$, so in this case the inequality becomes an equality. This yield us an exact solution for a rectangular board $q^2\times (q^2+q)$ and a square board with a side $q^2+q+1$, where $q$ is a power of a prime number we still cannot construct respective Steiner systems for other $q$ and a rectangular board $n\times n(n-1)/6$, where $n$ has a form $6q+1$ or $6q+3$ for some $q$.

References

[VE] Vasil'ev N.B, Egorov A.A. The problems of the All-Soviet-Union mathematical competitions, Moscow.:Nauka, 1988 (in Russian).

• Simple and elegant solution with a nice story added as a bonus. I just want to mention that the expression mentioned in the problem statement is slightly different from the solution explained in the book, but the difference is neglectable and could be eliminated with an additional approximation. Many thanks! – Oldboy Nov 22 '17 at 12:28

If you remove any row and column, and there are at least $(N-1)(\sqrt{N-1}+1/2)$ coloured squares left, then there is a rectangle by induction.
So you can assume that fewer coloured squares remain when any row and column are removed;
so each of the row and column you removed has at least a certain number of coloured squares, to make the grand total grow from below $(N-1)(\sqrt{N-1}+1/2)$ to at least $N(\sqrt{N}+1/2)$

• This looks like an idea how to prove it by induction but it's far from the complete solution. – Oldboy Nov 19 '17 at 13:47
• Perhaps you should have asked for the complete solution :) – Michael Nov 19 '17 at 13:52
• Ok, I'm asking for the complete solution ;) – Oldboy Nov 19 '17 at 14:03