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

Question

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.

Answer 1

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.

Answer 2

It's not possible, as can be quickly checked with a SAT solver. Here's the Python code I used:

from ortools.sat.python import cp_model
forbidden_corners = [(2,4),(4,2),
                     (38-4,2),(38-2,4),
                     (38-4,40-2),(38-2,40-4),
                     (2,40-2)]
model = cp_model.CpModel()
cells = {}
for i in range(38-8):
    for j in range(40-8):
        #first check if the square is inside the region
        if not any([(i<=corner[0]<i+9 and j<=corner[1]<j+9) for corner in forbidden_corners]):
            cells[(i,j)] = model.NewBoolVar(f'cell_{i}_{j}')

#constraint: no two overlapping squares at once
for s1 in cells:
    for s2 in cells:
        if s1!=s2 and (s1[0]<=s2[0]<s1[0]+9 or s2[0]<=s1[0]<s2[0]+9) and (s1[1]<=s2[1]<s1[1]+9 or s2[1]<=s1[1]<s2[1]+9):
            model.AddBoolOr([cells[s1].Not(),cells[s2].Not()])

#at least 16 squares
model.Add(sum([cells[s] for s in cells])>=16)
solver = cp_model.CpSolver()
solver.Solve(model)
print(solver.StatusName())

I don't know if there's an elegant proof of this fact that doesn't involve substantial casework.

Answer 3

Every $9\times 9$ square covers at least two of the following $31$ black cells, which immediately implies an upper bound of $\lfloor 31/2 \rfloor = 15$ nonoverlapping squares: