4. For a given natural number $n \geq 3$, we have an $n \times n$ board where all cells are white. We define a floating plus as a quintuple ( $M, L, R, A, B$ ) of unit cells on the board such that $L$ is to the left of $M$ in the same row, $R$ is to the right of $M$ in the same row, $A$ is above $M$ in the same column, and $B$ is below $M$ in the same column. It is allowed for $M$ to form a floating plus with non-adjacent cells. Determine the largest $k$ (in terms of $n$) for which some $k$ cells of the board can be colored black such that no black floating plus exists.
Solution. We will prove that the answer is $k=4 n-4$. If we color all the edge cells of the board in black, then we have exactly $4 n-4$ black cells, because each edge has $n$ and each corner (there are 4) is counted twice. If there is a black swan plus, then its center, $M$, is in a row with at least 3 black cells and in a column with at least 3 black cells. This means that $M$ must be a corner of the board, which is impossible since there is no swan plus with a center in a corner. We conclude that the construction is correct.

We will now prove that if the number of black cells on the board is at least $4 n-3$, then there is a black swan plus. If we assume the opposite, then no black cell is the center $M$ of any swan plus. This means that at least one of the four directions $\uparrow, \downarrow, \rightarrow$ and $\leftarrow$ relative to that cell does not contain another black cell. We consider all pairs of the form $(s, \leftarrow),(s, \rightarrow),(s, \uparrow)$ and $(s, \downarrow)$ where $s$ is a black cell, and the arrow in the pair points in the direction without black cells relative to $s$. Let $P$ be the number of such pairs. Since no cell is the center of a black swan plus, we conclude that there are at least $4 n-3$ such pairs.

We consider the first column from the left, $K_{l}$, that contains a black cell (which means that all columns to the left of it do not contain black cells). Let $x$ be the topmost black cell in column $K_{l}$. Then $x$ belongs to at least two of the considered pairs: namely, to $(x, \leftarrow)$ and $(x, \uparrow)$. Similarly, if $y$ is the bottommost black cell in the same column, then $y$ also belongs to at least two pairs: namely, $(y, \leftarrow)$ and $(y, \downarrow)$. This means that in column $K_{l}$ there are at least two additional pairs, even when $x=y$. The same applies to the first column from the right that contains a black cell, let's denote it as $K_{d}$. Clearly, $K_{l} \neq K_{d}$, because otherwise there are at most $n$ black cells (all in the same column), which is impossible ($4 n-3 > n$).

We conclude that there are at least $4 n-3+4=4 n+1$ pairs, i.e., $P \geq 4 n+1$.

For each pair, the arrow is in one of four possible directions. From $P \geq 4 n+1$ and the pigeonhole principle, we conclude that there are at least $n+1$ pairs with arrows in the same direction, say $\rightarrow$. This means that there are pairs $\left(s_{1}, \rightarrow\right),\left(s_{2}, \rightarrow\right), \ldots,\left(s_{n+1}, \rightarrow\right)$. Since the board has exactly $n$ rows, the pigeonhole principle implies that some $s_{i}$ and $s_{j}$ lie in the same row, and thus the pairs $\left(s_{i}, \rightarrow\right)$ and $\left(s_{j}, \rightarrow\right)$ are in the same row. The latter is impossible, because then one of $s_{i}$ and $s_{j}$ has a black cell in the $\rightarrow$ direction (one cell is to the right of the other). This contradiction proves that there can be at most $4 n-4$ black cells, provided that no black swan plus appears.