# 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?

-
The induction should do the trick. Just make inductive proofs for even and odds separetly. –  Godot Aug 30 '12 at 14:36
Do diagonal connections count, or do the squares have to connect along an edge? –  Ross Millikan Aug 30 '12 at 14:37
This is problem J59 from Mathematical Reflections Volume 4 (2007). –  Byron Schmuland Aug 30 '12 at 15:05

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

-
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.
'Any path of $2k$ squares can contain at most $k$ black squares' : What if they go BBWBBWBBW? –  Steven Stadnicki Aug 30 '12 at 18:02
Not quite right -- it fails for the case $n=3$, when $\frac{1}{2}n^2+\frac{1}{3}n+\frac{1}{2}$ is greater than $\frac{1}{2}n^2+\frac{1}{2}n-1$. I think you have to prove the case $n=3$ separately, by hand-waving (which is why I never completed my own answer!). –  TonyK Aug 30 '12 at 21:40