Maximum number of unit squares sharing vertices in a grid

Question

In a board of $2021 \times 2021$ grids, we pick $k$ unit squares such that every picked square shares vertice(s) with at most $1$ other picked square. Determine the maximum of $k$.

This seems extremely familiar but maybe I'm confusing it with some other related problem. I searched it up on all math sites I know, but I didn't find anything about it.

---

Examples:

$1\times 1$ grid: Trivially, the answer is $1$.

$2 \times 2$ grid: The answer is $2$.

$3\times 3$ grid: Experimenting, we see that the answer is $4$.

$4 \times 4$ grid: Here's where it starts to get complex. So, we number the squares:

$$1 \quad 2 \quad 3 \quad 4$$

$$5 \quad 6 \quad 7 \quad 8$$

$$9 \quad 10 \quad 11 \quad 12$$

$$13 \quad 14 \quad 15 \quad 16$$

We have two options that came to my mind while optimizing:

1. pick $5,9,7,8,15,16$. This gives us $6$ squares.
2. CREDIT TO PREM: $1,2,4,8,16,15,9,13$. This gives us $8$ squares.

So, our answer for a $4\times 4$ grid is $8$.

---

Now, for an arbitrary $n \times n$ grid, I don't know what to do. My idea is to use recursion from the results for the previous smaller grids, but I'm not sure how exactly to do this. My idea might be completely off-track, so if you have a better idea, you can comment it.

---

Could somebody please help?

---

Answer 1

The following MiniZinc model confirms the first numbers of the OEIS sequence A260090 $(1, 2, 4, 8, 12, 16, 21, 26, 33, ...)$ referenced in the comments:

int: n = 9;
set of int: N = 1..n;
set of int: Nx = 0..n+1;

%  extra frame cells added to make neighbor constraint easier
array[Nx, Nx] of var bool: x;

%  periphery grid cells are all false
constraint 
  forall(i in {0, n+1}, j in Nx) 
    (not (x[i, j] \/ x[j, i]));

%  at most one neighbor grid cell is true
array[1..8] of -1..1: dRow = [-1, -1, -1,  0, 0,  1, 1, 1];
array[1..8] of -1..1: dCol = [-1,  0,  1, -1, 1, -1, 0, 1];

constraint 
  forall(row in N, col in N)
    (( not x[row, col]) \/ 
     (1 >= sum([x[row + dRow[i], col + dCol[i]] | i in 1..8])));
    
% objective to maximize
var 1..n*n: k = sum(x);

solve maximize k;

output ["\(k)"] ++ 
       [if col == 1 then "\n" else "" endif ++ 
       if fix(x[row, col]) then "1 " else "0 " endif 
       | row in N, col in N ];

Example solution for $n=8$:

k = 26

1 1 0 1 1 0 1 1 
0 0 0 0 0 0 0 0 
1 0 1 0 1 0 0 1 
1 0 1 0 1 0 1 0 
0 0 0 0 0 0 0 0 
1 1 0 1 1 0 1 1 
0 0 0 0 0 0 0 0 
1 1 0 1 1 0 1 1

Using the COIN-BC solver (COIN-OR CBC) backend, the solution time for $n=9$ is about one minute. CPLEX 12 with $8$ threads found a solution for $n=11$ in $2.5$ minutes.

Answer 2

Adjacent picked squares can come in one of three groupings:

• A single isolated square.
• Two squares sharing a side.
• Two squares with just one corner in common.

For each of these groupings, we can draw an "exclusion zone" around them that must be free from any other picked squares, either because of the "picked square can have only one neighbor" rule, or in the case of an isolated square, because it is isolated. Letting the sidelength of a square be $1$, if we limit that exclusion zone to extend only a distance of $\frac 12$ away from the picked squares, then the exclusion zones of separate groupings cannot overlap:

The exclusion zones of picked squares on the edges on the grid will extend outside the grid. But if we define an exclusion region enlarging the grid by $\frac 12$ on all sides, for an $n \times m$ grid, we get an exclusion region of area $(n+1)(m+1)$ which contains the exclusion zones of all groupings in it.

• The exclusion zone of an isolated picked square has area $4$, so the picked square itself fills $\frac 14$ of the area of the zone.
• The exclusion zone of two picked squares sharing a common side has area $6$, and the picked squares account for $\frac 13$ of that area.
• The exclusion zone of two picked squares sharing a single corner has area $7$, and the picked squares account for $\frac 27$ of that area.

Since the largest of these ratios is $\frac 13$, the picked squares, each of which has area $1$, can account for at most $\frac 13$ of the $(n+1)(m+1)$ area of the exclusion region. I.e., there can be at most $$\left\lfloor\frac{(n+1)(m+1)}3\right\rfloor$$ picked squares in the grid.

In the special case where $n+1$ is divisible by $3$ and $m+1$ by $2$, or vice versa, this upper limit on the number of picked squares can be obtained with a simple array of groupings of two squares sharing a side. For example, when $n = 8, m = 9$, where the exclusion zones are indicated with alternating colors:

The particular case for this question has $n = m = 2021$, and it so happens that $2021+1$ is divisible by both $2$ and $3$. Thus the maximum number of squares that can be picked is exactly $$\dfrac{2022^2}3 = 1362828$$

---

[Edit: The rest of this has changed. Upon further investigation, I found this idea settles the entire matter, not just the square $n + 1 \equiv 0 \mod 6$ case.]

More generally, these exclusion zones convert the original question for an $n \times m$ grid into a question of non-overlapping tilings fitting in an $(n+1) \times (m+1)$ grid using these five shapes:

Call the $3 \times 2$ rectangles "bricks", the $2 \times 2$ square a "block", and for lack of anything better, the other shapes "diamonds". Assign a weight to each shape based on the number of square vertices that are in the interior of the shape: the block has a weight of $1$, and the bricks and diamonds have a weight of $2$. The weight of a tiling is the sum of the weights of the tiles used in it. These internal vertices correspond to the picked squares of the original problem, and to the kings in the 1-dependence kings graph interpretation.

The task is then to find a tiling that fits inside an $(n+1) \times (m+1)$ grid and has maximum weight. This maximum weight will also be the maximum number of picked squares or kings in the other interpretations.

We can quickly see that certain conditions will produce a tiling of maximum weight:

• A tiling that covers the entire grid with bricks, with the possible exception of $3$ or fewer untiled squares, will have maximum weight.
• A tiling that covers the entire grid with bricks and a single block will also have maximum weight.

If a tiling uses nothing but bricks and leaves $3$ or fewer squares uncovered, then it is impossible to add another tile without removing a brick first. But the weight of the removed brick matches or exceeds anything it can be replaced with. A brick and $2$ untiled squares might be replaced with two blocks, but the weight of the removed brick is the same as the two blocks, so the total weight of the tiling does not increase. Similarly, a brick and one untiled square might be replaced by a diamond, but again, the diamond is not worth more than the brick. Removing additional bricks only makes matters worse. Bricks have the greatest weight-to-area ratio, so changing bricks out for other tiles is a losing proposition. Similarly, if the grid is completely tiled by bricks and a single block, your only choices are to switch bricks out for blocks or diamonds, reducing or at best keeping level on the total weight. It cannot be increased.

So all that remains is to show that all grids can be tiled with bricks alone, leaving at most three squares untiled, or by bricks with a single block. I will show this for square grids, but I believe the same method can be adapted for any rectangular grid.

Tilings for the ten smallest square grids can be found by inspection (the $4 \times 4$ grid is a special case, but is easily seen to be maximal):

Tilings for larger squares of sidelength $n+1$ can be found by extending the tiling for $(n+1) - 6$. Put the $(n+1)-6$ tiling in the upper left corner. Copy the bricks on the left side of that tiling two or three times to cover six more columns of squares, and similarly copy the bricks on the bottom of the $(n+1)-6$ tiling down to cover six more rows of squares. Once this is done, there will be a $6 \times 6$ region on the lower right that is still untiled. Cover it with a copy of the $6 \times 6$ tiling:

Since the tilings from $5$ and on all have only bricks on their right and bottom, this will always work. And per the discussion above, it will always produce a maximum weight.

By this we can determine the maximum weight / number of picked squares / number of kings for any size grid:

• If $(n+1)$ is divisible by $6$, then the weight is $\dfrac{(n+1)^2}3$
• If $(n+1)$ is odd and divisible by $3$, then the weight is $\dfrac{(n+1)^2}3-1$
• Otherwise, the weight is $\dfrac{(n+1)^2-1}3$