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?
showing that there is a shape which has three connected black squares
3
$\begingroup$
combinatorics
-
1The induction should do the trick. Just make inductive proofs for even and odds separetly. – 2012-08-30
-
0Do diagonal connections count, or do the squares have to connect along an edge? – 2012-08-30
-
0This is problem J59 from Mathematical Reflections Volume 4 (2007). – 2012-08-30