Q:

showing that there is a shape which has three connected black squares

We have square lattice with dimensions $n × n$, such that $n \ge 2$. Some of the squares on this lattice are coloured black. How can we show that there are at least 3 connected black squares if there are $$1+\frac{n^{2}}{2}$$ black squares when $n$ is even and $$\frac{n(n+1)}{2}$$ black squares when $n$ is odd? 

A:

If $n$ is even, just cut the board into $2\times2$ tiles. At least one of these tiles must contain three black squares.

A:

Note that any $2\times 2$ tile can contain at most $2$ black squares. In addition, any path of $k$ squares can contain at most $2(k+1)/3$ black squares.  For an $n\times n$ square region where $n$ is even, the decomposition into $\frac{1}{4}n^2$ tiles gives an upper bound of $\frac{1}{2}n^2$ black squares.  For an $n\times n$ square region where $n$ is odd, the decomposition into $\frac{1}{4}(n-1)^2$ tiles and a path of length $2n-1$ gives an upper bound of $\frac{1}{2}(n-1)^2+\frac{4}{3}n=\frac{1}{2}n^2+\frac{1}{3}n+\frac{1}{2}$ black squares.  This latter is a tighter bound than the one in the problem, which is $\frac{1}{2}n^2+\frac{1}{2}n-1$.
Note that the checkerboard pattern with black squares in the four corners, which is an obvious candidate for optimality in the odd-$n$ case, has only $\frac{1}{2}n^2+\frac{1}{2}$ black squares.  To see that this is not optimal, consider the $5\times5$ region.  The checkerboard pattern has $13$ black squares; but a pattern with $14$ black squares is obtained by placing $4$ black squares in the first, third, and fifth columns and a single black square in the second and fourth columns.

