# How many $9\times 9$ squares can I cut from this figure (it's $38\times 40$ without some corners)

Can I cut 16 ones (along the grid)?
I've tried to paint some $15$ cells so that every $9\times 9$ square contain only $1$ painted cell (so I prove there can't be $16$), but to no avail.

The figure (bold): EDIT: I can now prove "the reduced version", thanks to Dacian Bonta, that we can't "fit 4 9 x 9 squares in a 22 x 20 grid, given missing corner grid cells": There are $7$ painted cells and every possible $9\times 9$ square covers at least $2$ of them. If $4\ 9\times 9$ squares would be possible, each covering at least $2$ painted cells, the total number of painted cells must be $\ge 8$, but we have $7$.

But I can't get to "expanded" version from this.

• 15 I see possible. 16 should be 4x4 arrangement. At a minimum 36x36. I don't see 16. – Dacian Bonta Dec 15 '15 at 2:22
• This grid is small enough to brute-force if someone is willing to put in the time to write a program to... – qwr Dec 15 '15 at 4:22
• @qwr Is it? Simple brute-force would take at least $896$ positions for the first square, $896-81$ for the second one and then resulting $\ge 2.3\cdot 10^{29}$ overall. – Alexey Burdin Dec 15 '15 at 4:28
• @AlexeyBurdin Well, maybe not that brute-force! I meant brute-force as in not a clever solution, but something like backtracking. – qwr Dec 15 '15 at 4:34

Here is my attempt. However, I think that we can erase the central two rows and the central two columns of squares, with the corresponding underlying grid cells, reducing the problem to a "fit 4 9 x 9 squares in a 22 x 20 grid, given missing corner grid cells". That problem should be easier to tackle.

the cut grid looks like this: I think that I can see it now. On the top row, either the left square fits in the middle dent, which pushes the right top row square to the lower dent (the situation in the picture), or vice-versa. In the first scenario the four rightmost columns under the right upper square become off-limits, and you have only 16 cells to fit the lower row of squares (i.e. one cannot fit two squares side by side in the bottom row). In the second scenario the two leftmost and the two rightmost columns become off-limits for the bottom row, again only 16 cells, in which two 9 x 9 squares cannot fit side by side, again.

So no 16. 15 is max.

• Yep, much easier. Here's a proof that one can't fit $4$: i.imgur.com/UWbNqeb.png . There are 7 painted cells and every possible $9\times 9$ square covers at least $2$ of them. How can I get to OP from there? – Alexey Burdin Dec 15 '15 at 3:30
• well, in any solution you have 4rows of 4 squares. For each column, the 18 cells corresponding to the 2 central rows of squares can be deleted. Because you did that to each row, the squares in the top and bottom rows remain squares. Same thing done on the rows; then you're left with oonly the corner squares. This reduces the problem from 4x4 to 2x2. The central two rows and two columns are dummy elements, only the corners matter (for this problem). Actually the problem can be made into any \ y^2 question by adding dummy rows and columns. – Dacian Bonta Dec 15 '15 at 3:38