In a $12\times 12$ grid, colour each unit square with either black or white, such that there is at least one black unit square in any $3\times 4$ and $4\times 3$ rectangle bounded by the grid lines. Determine, with proof, the minimum number of black unit squares.
Problem
Source: CGMO 2015 Q3
Tags: combinatorics, geometry, rectangle
buzzychaoz
27.03.2016 16:09
Breaking up the $12\times 12$ grid into $12$ non-intersecting $3\times 4$ rectangles, clearly at least $12$ black squares are needed.
\begin{tabular} {|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &X &\space &\space &\space &X &\space &\space &X &\space &\space\\
\hline \space &\space &\space &\space &\space &X &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &X &\space &\space &\space &\space &\space &\space &X &\space &\space\\
\hline \space &\space &\space &\space &\space &X &\space &\space &X &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &X &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &X &\space &\space &\space &X &\space &\space &X &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline
\end{tabular}
lemon94
25.07.2019 16:37
buzzychaoz wrote:
Breaking up the $12\times 12$ grid into $12$ non-intersecting $3\times 4$ rectangles, clearly at least $12$ black squares are needed.
\begin{tabular} {|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &X &\space &\space &\space &X &\space &\space &X &\space &\space\\
\hline \space &\space &\space &\space &\space &X &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &X &\space &\space &\space &\space &\space &\space &X &\space &\space\\
\hline \space &\space &\space &\space &\space &X &\space &\space &X &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &X &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &X &\space &\space &\space &X &\space &\space &X &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline \space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space &\space\\
\hline
\end{tabular}
Proof that it's the minimum?
P2nisic
29.03.2024 00:22
buzzychaoz wrote: In a $12\times 12$ grid, colour each unit square with either black or white, such that there is at least one black unit square in any $3\times 4$ and $4\times 3$ rectangle bounded by the grid lines. Determine, with proof, the minimum number of black unit squares. Cut the board at $12$ boards of $4\times 3$ this means that we need at least $12$ black square.And use the cunstraction of two @adove