3
$\begingroup$

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?

  • 0
    This is pro$b$lem J59 from Mathemati$c$al Reflections Volume 4 (2007).2012-08-30

2 Answers 2

3

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

3

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.

  • 1
    @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.2012-09-03