Each square of a $7 \times 8$ board is painted black or white, in such a way that each $3 \times 3$ subboard has at least two black squares that are neighboring. What is the least number of black squares that can be on the entire board? Clarification: Two squares are neighbors if they have a common side.
Problem
Source: 2017 Peru MO (ONEM) L3 p2 - finals
Tags: Coloring, combinatorics
25.01.2024 22:11
Answer: $10$. Example: $\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|} \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{tabular}$ $\rule{430pt}{1pt}$ Proof: $\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|} \hline 1 & 1 & 1 & 0 & 0 & 2 & 2 & 2 \\ \hline 1 & 1 & 1 & 0 & 0 & 2 & 2 & 2 \\ \hline 1 & 1 & 1 & X& X& 2 & 2 & 2 \\ \hline 0 & 0 & A& X& X& B & 0 & 0 \\ \hline 3 & 3 &3 & X& X& 4 & 4 & 4 \\ \hline 3 & 3 &3 & 0 & 0 & 4 & 4 & 4 \\ \hline 3 & 3 &3 & 0 & 0 & 4 & 4 & 4 \\ \hline \end{tabular}$ There must be at least $2$ black squares in each of $3x3$ squares created by $1,2,3,4'$s. So there must be $\geq 8$ black squares. If there is no black square in $A$ or $X$, then there don't exist two neighbour black squares in the $3x3$ square which contains $X'$s and $A,1,3$. Similarly, if there is no black square in $B$ or $X$, then there don't exist a pair of neighbour black squares in the $3x3$ square which contains $X'$s and $B,2,4$. If there are $\leq 9$ black squares, there are two cases. $i)$ Both $A,B$ are empty $\implies$ There must be at least $2$ black squares in $X'$s. $ii)$ One of $A,B$ is empty and $X'$s are empty $\implies$ The $3x3$ square which contains $X's$ and the empty one among $A,B$ doesn't have a pair of black neighbour squares. For both cases, we get contradiction. So there must be at least $10$ black squares as desired.$\blacksquare$