# 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
@StevenStadnicki: Of course you're right. Is it correct now? – mjqxxxx Aug 30 '12 at 19:29
It looks clean to me now! – Steven Stadnicki Aug 30 '12 at 20:43
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
@TonyK: OK. In a 3x3 the center square must be white. Otherwise you either have two black squares touching it or you have one black square touching it and two black corners. If the center square is white, there are only two white squares in the ring of eight, so three in a row must be black. – Ross Millikan Sep 3 '12 at 16:45