Max packing of cars in square parking lot

Question

An $n\times n$ square grid represents a parking lot, each of the $n^2$ squares may be occupied by at most one car. However, each car (not on the boundary) must have a clear path to the boundary of the grid, moving only to adjacent squares sharing a side.

What is the maximum number $M(n)$ of cars that can fit in the parking lot?

This was posted recently by @Benenom but for some reason was deleted 3 mins after appearing.

Clearly, $M(n)=n^2$ for $n<3$. For $n=3$ we need at least one vacant square (any non-corner square will do). For $n=4$ we need at least 3 vacant squares (eg a line of three starting from a non-corner boundary square).

At first I thought that the idea used for $n=4$ might work for all $n$. Eg for $n=8$ make vacant the first 7 squares of the third and sixth rows.

$$\begin{matrix}C&C&C&C&C&C&C&C\\ C&C&C&C&C&C&C&C\\ C&.&.&.&.&.&.&.\\ C&C&C&C&C&C&C&C\\ C&C&C&C&C&C&C&C\\ C&.&.&.&.&.&.&.\\ C&C&C&C&C&C&C&C\\ C&C&C&C&C&C&C&C\end{matrix}$$

That gives:

$M(1)=1\\ M(2)=4\\ M(3)=9-1=8\\ M(4)=16-3=13\\ M(5)=25-4=21\\ M(6)=36-2\cdot5=26\\ M(7)=49-3\cdot6=37\\ M(8)=64-2\cdot7=50$

In general we would get

$M(3n+2)=(3n+2)^2-n(3n+1)=6n^2+11n+4\\ M(3n+1)=(3n+1)^2-3n^2=6n^2+6n+1\\ M(3n)=(3n)^2-n(3n-1)=6n^2+n.$

[the last one for $n>1$]

However, as @RobPratt points out in his answer below, we can do better than that for $M(6)$, getting 36-8=28. Presumably the same is true for all $M(3n)$.

For $3n=6$ we can write the last four rows as: $$\begin{matrix}C&.&.&.&.&.\\ C&C&.&C&.&C\\ C&C&.&C&C&C\\ C&C&C&C&C&C\end{matrix}$$ In a similar way we could write the last four rows for $3n=9$ as: $$\begin{matrix}C&.&.&.&.&.&.&.&.\\ C&C&.&C&C&.&C&.&C\\ C&C&.&C&C&.&C&C&C\\ C&C&C&C&C&C&C&C&C\end{matrix}$$ and in general we would get $M(3n)=6n^2+2n$. The other two cases are unchanged: $M(3n+1)=6n^2+6n+1$ and $M(3n+2)=6n^2+11n+4$.

In any case I have not yet got a proof of maximality even for $M(3n+2)$.

Answer 1

Six of your values for $M(n)$ are correct, but $M(6)=28$: \begin{matrix} C &C &C &C &C &C \\ C &C &. &C &C &. \\ C &C &. &C &C &C \\ C &C &. &. &. &. \\ C &C &. &C &C &C \\ C &C &C &C &C &C \end{matrix} And $M(7)=37$: \begin{matrix} C &C &. &C &C &C &C \\ C &C &. &C &. &C &C \\ C &C &. &C &. &C &C \\ C &C &. &C &. &C &C \\ C &. &. &. &. &C &C \\ C &C &C &C &C &. &C \\ C &C &C &C &C &C &C \end{matrix} I used integer linear programming, with a binary variable $c_{i,j}$ to indicate whether square $(i,j)$ contains a car and a binary variable $e_{i,j}$ to indicate whether square $(i,j)$ does not contain a car but can exit the lot. Let $N_{i,j}$ be the set of neighbors of square $(i,j)$. The problem is to maximize $\sum_{i,j} c_{i,j}$ subject to linear constraints: \begin{align} c_{i,j} + e_{i,j} &\le 1 &&\text{for all $i,j$}\\ c_{i,j} &\le \sum_{(i',j')\in N_{i,j}} e_{i',j'} &&\text{for all interior $i,j$}, \end{align} together with flow variables and constraints that send one unit of flow from each exit square to a dummy sink node.

Answer 2

Not an answer. Just wanna report that I found another "divide-and-conquer" strategy to get the same answer for side length $m=3n$ cases. It is based on $4$ "center aisles" forming an offset $+$ like pattern. This divides the $m \times m$ square into $4$ rectangles, and since $m=3n$, we can arrange each rectangle to have dimensions $(3k+2) \times (3j)$, and the $(3k+2)$ side makes it in a sense easier to deal with.

Here is the $m=12=3n$ example. The $4$ center aisles split all remaining squares into (1) four cars at the center of the $+$ denoted "b", and (2) four separate $6\times 5$ rectangles, one of which I have highlighted as "a" instead of "c". The total number of spaces $= 5 \times 8 = 40 = n(3n-2)$, so it achieves the same $M(n)$ as the already found solution.

c c . c c . c c c c c c
c c . c c . c c c c c c
c c . c c . c . . . . .
c c . c c . c c c c c c
c c . c c . c c c c c c
c c c c c b b . . . . .
. . . . . b b a a a a a
c c c c c c . a a . a a
c c c c c c . a a . a a
. . . . . c . a a . a a
c c c c c c . a a . a a
c c c c c c . a a . a a

This also works when $m=3n$ is odd, because there is no need for the four rectangles to be the same dimensions. E.g here is the $m=9=3n$ case. The number of spaces $=21 = n(3n-2)$, again equaling the already found solution.

c c . c c . c c c
c c . c c . c c c
c c . c c . c . .
c c . c c . c c c
c c . c c . c c c
c c c c c b b . .
. . . . . b b a a
c c c c c c . a a
c c c c c c . a a

I have played around with this "divide-and-conquer" strategy for a bit, with different original side lengths and different splits, but was never able to find a better solution.