The plane is divided into unit cells, and each of the cells is painted in one of two given colors. Find the minimum possible number of cells in a figure consisting of entire cells which contains each of the $16$ possible colored $2\times2$ squares.
Problem
Source: Mongolia 1999 Grade 9 P1
Tags: geometry, combinatorics, combinatorial geometry
Diego17
05.05.2021 18:51
The answer is 25
[asy][asy]
unitsize(15);
fill((0,0)--(2,0)--(2,1)--(0,1)--cycle, grey);
fill((4,1)--(4,0)--(5,0)--(5,1)--cycle, grey);
fill((2,1)--(4,1)--(4,3)--(3,3)--(3,4)--(4,4)--(4,5)--(2,5)--(2,4)--(1,4)--(1,3)--(2,3)--(2,1)--cycle, grey);
draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0));
draw((1,0)--(1,5));
draw((2,0)--(2,5));
draw((3,0)--(3,5));
draw((4,0)--(4,5));
draw((0,1)--(5,1));
draw((0,2)--(5,2));
draw((0,3)--(5,3));
draw((0,4)--(5,4));
[/asy][/asy]
jasperE3
05.05.2021 19:14
And the proof of minimality?
Diego17
06.05.2021 15:36
We take out all the upperleft grid of the 16 $2\times2$ square. Suppose there are a total of $m$ rows and $n$ column in these 16 taken out grids.(it is not necessary that the rows and columns are adjacent and there could be a "hole" in the figure.) Notice that $m\times n\ge 16$, we have $m+n\ge 8$ Consider the lowest grid of each column, the whole figure must contain the grids under them. The same for each row Also, the grid that is bottom right to the bottom right grid (there might be more than one bottom right grid) is also contained in the whole figure. So there's at least $16+m+n+1\le 25$ grids in the whole figure.