For a fixed positive integer $n \geq 3$ we are given a $n$ $\times$ $n$ board with all unit squares initially white. We define a floating plus as a $5$-tuple $(M,L,R,A,B)$ of unit squares such that $L$ is in the same row and left of $M$, $R$ is in the same row and right of $M$, $A$ is in the same column and above $M$ and $B$ is in the same column and below $M$. It is possible for $M$ to form a floating plus with unit squares that are not next to it. Find the largest positive integer $k$ (depending on $n$) such that we can color some $k$ squares black in such a way that there is no black colored floating plus. Proposed by Nikola Velov
Problem
Source: Macedonian Mathematical Olympiad 2021 P4
Tags: combinatorics
steppewolf
25.05.2021 22:46
One of my best problems
We will prove that the answer is $4n-4$. To see that $4n-4$ is possible, color black all the unit squares on the edges of the table. There are $n$ unit squares on each edge, and the corners are counted twice, so this gives us exactly $4n-4$ black squares. To see that they form no black floating plus, note that the center $M$ of any floating plus lies in a row with at least three black squares and in a column with at least three black squares. In this coloring, the only possible squares for $M$ are thus the corners of the board, but obviously they cannot form a floating plus.
We will show that if there are at least $4n-3$ black squares, there must be some black floating plus formed by them. Assume that this is not a case. Then every black unit square is not the center $M$ of a black floating plus. That means that at least one of four directions $\leftarrow$, $\rightarrow$, $\uparrow$ and $\downarrow$ with respect to that square does not contain another black unit square. We will now look at all pairs of the form $(s,\leftarrow)$, $(s, \rightarrow)$, $(s,\uparrow)$ and $(s,\downarrow)$ where $s$ is a black square and the arrow in the square points in the direction with respect to $s$ that has no other black square. Let there be $P$ such pairs. Because no black square is the center of a black floating plus, there are at least $4n-3$ such pairs.
Now observe the leftmost column that contains black squares (all columns to the left of it are entirely white). The top black unit square in this column $x$ is part of at least two pairs, $(x, \leftarrow)$ and $(x, \uparrow)$. The bottom black unit square in this column $y$ is part of at least two pairs $(y, \leftarrow)$ and $(y, \downarrow)$. This means that the black unit squares in this column generate at least two extra pairs, even if $x=y$. The same is true for the rightmost column. Now notice that the leftmost and the rightmost column are not the same, because that would imply that we have at most $n$ squares, which is strictly less than $4n-3$. This means that we have at least $(4n-3)+4 = 4n+1$ pairs, in other words, $P \geq 4n+1$.
Every pair has four possible directions for the arrow. It follows from $P \geq 4n+1$ and the pigeonhole principle that there are at least $n+1$ pairs with the same direction, for example the direction $\rightarrow$. Thus, we have some pairs $(s_{1}, \rightarrow)$, $(s_{2}, \rightarrow)$,...,$(s_{n+1}, \rightarrow)$. However, there are only $n$ rows, so there must be two black squares $s_{i}$ and $s_{j}$ in the same row. This means that the pairs $(s_{i}, \rightarrow)$ and $(s_{j}, \rightarrow)$ are from the same row, which is not possible, because one is to the right of the other. This contradiction shows that there are at most $4n-4$ black squares.