Filling a 40 x 40 grid with 3x3 squares

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?

• To be sure, this is simply $14^2$ squares. – Omnomnomnom Jul 21 '14 at 17:32
• A $1/2$ square is it valid? – hlapointe Jul 21 '14 at 17:36
• @Omnomnomnom In the back of my mind, I always feel like these questions are trick questions and there is some arrangement of squares that allows for less than the predictable x^2 number. Then I just keep second guessing myself. – krikara Jul 21 '14 at 17:37
• @hlapointe The square would simply overlap with another square. – krikara Jul 21 '14 at 17:37
• Among the 40 numbers, $1, 2, \ldots, 40$, there are 14 of them $\equiv 1 \pmod 3$. This means there are $196 = 14\times14$ squares whose $(x,y)$ coorindates are both $\equiv 1 \pmod 3$. Every $3\times 3$ squares can cover one and only one of this sort of square. So you need at least $196$ copies of $3\times 3$ squares to cover the whole grid. – achille hui Jul 21 '14 at 17:45

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.

• I think your proof assumes, not only that the sides of the squares must be parallel to the gridlines, but that they must actually coincide with the gridlines. The first condition is necessary to make the proof work, but the second is not: you just have to space the points out so that they are a little more than 3 units apart. – TonyK Jul 21 '14 at 19:38

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.)

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.

• This assumes that the $k \times k$ squares are aligned with the axes. I'm not sure that is required. – Ross Millikan Jul 21 '14 at 19:03
• @RossMillikan, you are quite right. I assumed (and still suspect) the OP was thinking of the $40\times40$ "grid" as a checkboard, with the $3\times3$ squares filling entire $3\times3$ arrays of grid cells, but it will help if the OP clarifies things. – Barry Cipra Jul 21 '14 at 19:30