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?

  • 1
    The induction should do the trick. Just make inductive proofs for even and odds separetly.2012-08-30
  • 0
    Do diagonal connections count, or do the squares have to connect along an edge?2012-08-30
  • 0
    This is problem J59 from Mathematical 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.

  • 2
    'Any path of $2k$ squares can contain at most $k$ black squares' : What if they go BBWBBWBBW?2012-08-30
  • 0
    @StevenStadnicki: Of course you're right. Is it correct now?2012-08-30
  • 0
    It looks clean to me now!2012-08-30
  • 0
    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!).2012-08-30
  • 0
    Indeed, the $5 \times 5$ pattern you describe can be extended to a pattern with $\frac12n(n-1)+\left\lceil\frac23n\right\rceil = \left\lceil\frac12n^2+\frac16n\right\rceil$ black squares for any odd $n$.2012-08-30
  • 0
    You have to prove the $3 \times 3$ case separately, as TonyK says. But there are not many cases to consider, as there are only three white squares.2012-09-01
  • 0
    @Ross: Are those your hands I can see waving?2012-09-03
  • 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