Filling a 40 x 40 grid with 3x3 squares

Question

I'm supposed to find out the minimum number of 3x3 squares that will completely fill up this 40x40 grid where overlapping squares is acceptable. Each 3x3 square also has to coincide with the grid lines.

My procedure to do a problem like this is to first divide 40 by 3 and I get 13.333 .

Then I say I have 13 by 13 (3x3) squares with one row and one column left over. I then fill the remaining empty space with 13 squares for a row, 13 squares for a column, and 1 extra square for the corner. This makes my answer to be 196 squares. Is this a correct solution and are there other better ways or a neat general formula to solve these type of problems?

Answer 1

Index the squares on the $40\times 40$ grid by a pair of integers $(x,y)$ with $1 \le x, y \le 40$. Let us call the square at $(x,y)$ as $S_{x,y}$. Consider following subset of squares on the grid:

$$\mathcal{S} = \big\{\; S_{x,y} : x \equiv 1 \pmod 3, y \equiv 1 \pmod 3\;\big\}$$

It is clear $\mathcal{S}$ contains $\lceil \frac{40}{3} \rceil \times \lceil \frac{40}{3} \rceil = 14 \times 14 = 196$ elements. Pick any two squares $S_{x_1, y_1}$, $S_{x_2,y_2}$ from $\mathcal{S}$, we have either

$$x_1 \ne x_2 \implies |x_1 - x_2 | \ge 3 \quad\text{ OR }\quad y_1 \ne y_2 \implies |y_1 - y_2 | \ge 3$$

This implies we cannot find a $3\times 3$ square that cover $S_{x_1,y_1}$ and $S_{x_2,y_2}$ at the same time.

If we cover the grid by some numbers of $3\times 3$ squares. The $3\times 3$ squares covering distinct elements from $\mathcal{S}$ are distinct. This implies we need at least $196$ $3\times 3$ squares to cover the whole grid.

It is clear how to cover the $40 \times 40$ grid by 196 copies of $3\times 3$ squares. So the desired answer is indeed $196$.

The basic idea is no different from a much simpler problem of covering a $3\times 3$ black and white chessboard having 5 whites squares and 4 black squares using $1 \times 2$ dominoes. Since each domino cover one white square and one black square. If the chessboard has 5 white squares, you need at least $5$ dominoes to cover it.

Answer 2

You can show in general that if you're trying to cover an $M\times N$ grid with $k\times k$ squares (with $k\le M,N$), it takes at least

$$\lceil{M\over k}\rceil\lceil{N\over k}\rceil$$

of the $k\times k$ squares, where $\lceil x\rceil$ rounds $x$ up to the nearest integer. The proof is basically by induction: To cover the $N$ grid cells along the top row, you have to use at least $\lceil{N\over k}\rceil$ copies of the $k\times k$ square. However you go about covering the top row, you're left with an $(M-k)\times N$ grid to be covered.

Answer 3

Here is a solution (to the problem as originally posted) that needs only 192 squares:

Fill in the grid from the top right until you have placed 169 squares, leaving only an L-shaped gnomon of width 1. Then cover the gnomon as shown in the diagram.

Distance $AB$ $=\frac14(5\sqrt{17}-9) > 2.9$

Distance $BC$ $=\frac98(\sqrt{17}-1) > 3.5$

So $3 + AB+10BC > 40$, and we can cover the gnomon with 23 squares.

(Note that the position of the square containing $A$ and $B$ is not optimal $-$ we can do fractionally better by rotating it clockwise about $B$, which lets us slide it to the right a little. But this would not be enough to reduce the total number of squares required.)