Smallest number of squares to color on a board
Source: 2022 Abelkonkurransen Finale, Problem 3
March 12, 2024
combinatoricsTiling
Problem Statement
Nils has an board where and are positive integers, and a tile shaped as shown below. What is the smallest number of squares that Nils must color, so that it is impossible to place the tile on the board without covering a colored square? The tile can be freely rotated and mirrored, but it must completely cover four squares.
[asy]
usepackage("tikz");
label("%
\begin{tikzpicture}
\draw[step=1cm,color=black] (0,0) grid (2,1);
\draw[step=1cm,color=black] (1,1) grid (3,2);
\fill [yellow] (0,0) rectangle (2,1);
\fill [yellow] (1,1) rectangle (3,2);
\draw[step=1cm,color=black] (0,0) grid (2,1);
\draw[step=1cm,color=black] (1,1) grid (3,2);
\end{tikzpicture}
");
[/asy]