Competition problem — Combinatorics

Combinatorics Difficulty 6.6 National Olympiad Prove it Italy

Consider the infinite quadrant in the figure, where all the small squares have side $1$ . Is it possible to color some of the small squares black in such a way that both of the following properties are satisfied?
- For every natural number $n$ , the square with a vertex at $O$ and side $n$ (with sides parallel to the axes) has a number of black squares greater than the number of white squares.
- On every infinite diagonal of small squares parallel to the one shown in the figure, there are at most a finite number of black squares.

Solution

Solution:

Yes, it is possible. For example, let us color black:
- the first small square having a vertex at $O$ ;
- the first $2$ small squares on the two diagonals adjacent to the central diagonal;
- the first $3$ small squares on the two diagonals adjacent to the previous ones, and so on.

It is clear that every $45^{\circ}$ diagonal has a finite number of black squares.

Moreover, the number of black squares in a square of side $n$ with a vertex at the origin can be counted as follows:
- if $n=2k$ is even, the number is
$1 + 2(2 + 3 + \ldots + k - 1 + k + k + k - 1 + \ldots + 2 + 1) = 2k^{2} + 2k - 1 > 2k^{2} = \frac{1}{2} n^{2}$
- if $n=2k+1$ is odd, the number is:
$1 + 2(2 + 3 + \ldots + k + k + 1 + k + \ldots + 2 + 1) = 2k^{2} + 4k + 1 > 2k^{2} + 2k + \frac{1}{2} = \frac{1}{2} n^{2}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.