A puzzle about the maximum number of favorable squares on a board of any given size.

Question

I have come up with an interesting puzzle but I can't for the life of me figure out how to solve it.

It follows like this:

You have 2 types of squires that are congruent with one another. Let's call them A-squares and B-squares. They both have an area of n²

The rules are:

1. You can place as many B-squares on a square board with a side length of N as you want. (imagine placing Black squares on an empty chess board)

2. A-squares must be placed next to at least 1 B-square (they can be placed next to each other as long as both squares are touching at least 1 B-square)

The question is: What is the Maximum number of A-squares that is possible for any n-length square board?

If this question can't easily be answered I want to at least know if it's possible to calculate the maximum number of A-Squares that can fit into a 7x7 board.

This is an image of the two best configurations that i could come up with manually for a 7x7 board. (The green squares are A, blue squares are B and the the yellow/black squares outlines the board)

For context, I came up with this puzzle a long time ago when I wanted to create the most space-efficient sugarcane farm i could in minecraft seeing as how sugarcanes could only be planted adjacent to water blocks. I don't play minecraft anymore but I like the mathy-ness of many of it's aspects.

I'm still in high-school and i'm not good at programming. Sorry for all the trouble.

Answer 1

There is a straightforward bound saying that at least $\frac15$ of the $A$-squares and $B$-squares must be $B$-squares. Each $A$-square has an adjacent $B$-square, and each $B$-square has at most $4$ adjacent $A$-squares, so if there are $a$ $A$-squares and $b$ $B$-squares, then then number of $A$-to-$B$ adjacencies is at least $a$ and at most $4b$, giving $4b \ge a$.

This gives an upper bound of $a \le \frac45 N^2$ for $N \times N$ boards, which I expect to be approximately correct, with only the boundary causing problems. For the $7\times 7$ problem, however, this says only that we can't do better than $10$ $B$-squares and $39$ $A$-squares, whereas your second solution has $b=12$ and $a=37$. This is almost but not quite there. After several computer searches, though, I get the feeling that $a=37$ is the best we can do.

We can make partial progress and prove $a \le 38$ by looking at what happens in each corner square. If the corner square is an $A$-square, then one of the adjacent edge squares is a $B$-square and we get a "wasted" $A$-to-$B$ adjacency where it touches the side of the board. If the corner square is a $B$-square, we get two wasted adjacencies. If the corner square is empty, we lose the chance at having an $A$-square there.

So we have $4b-s \ge a$ and $a+b \le 49-t$, where $s$ is the number of occupied corners and $t$ is the number of empty corners. We can $a \le 4b-s$ and $a\le 49-b-t$ to get $2a \le 49+3b-s-t$ or $2a \le 45+3b$ (since $s+t=4$); in particular, $2a \le 45 + 3(49-a)$, which reduces to $a \le 38.4$. Because $a$ is an integer, we must have $a\le 38$.

I don't expect $a=38$ is possible, but I can't prove it yet.

Answer 2

Inspired by @MishaLavrov answer, here's a slightly improved accounting method that proves $a=$ no. of A-squares $=38$ is impossible, and therefore $a=37$ is optimal, for the $7\times 7$ board.

First consider any board with empty (non-A, non-B) squares. Since the optimality criterion is no. of A-squares, we can change all empty squares into B squares without affecting optimality. Therefore, from now on, without loss we can consider only boards filled with A & B squares (i.e. no empty squares).

Incidentally, this is why @HenningMalkolm is right that this problem is equivalent to covering the board using + pentominoes (overlap allowed). In the following I will use B-square and + pentomino somewhat interchangeably.

Anyway, let $b =$ no. of B-squares. So $a+b = 49$.

Any B-square can "enable" $4$ A-squares. Imagine you place the B-squares one by one, and for each one, count the increase in the total number of enabled A-squares. This number is often $4$, but can be $<4$. We will consider any deficit from $4$ as a "wastage" of A-squares. E.g. a B-square at a corner has a wastage of $2$ (assuming no overlap with previous + pentominoes), a B-square along an edge has a wastage of $1$ (assuming no overlap with previous + pentominoes) and a B-square whose + pentomino overlaps $1$ square with a previous pentomino (e.g. B-squares at $(i,j)$ and $(i, j+2)$) has a wastage of $1$ (at $(i,j+1)$ where the two + pentominoes overlap), etc. Let $w=$ the total no. of wastages. By definition, $4b = a + w$.

Thus we have $2$ equations with $3$ unknowns. If $a=38$, this would imply $b=11$ and $w=6$. To show that $a=38$ is impossible, all we need is to show $w=6$ is impossible. In fact we will now show $w \ge 8$.

Lemma: Consider any $2\times 2$ corner. Filling this corner alone would require $w \ge 2$.

Proof: Consider the case of $\{(0,0), (0,1), (1,0), (1,1)\}$. If $(0,0)$ is a B-square we are done. If it isn't, then without loss let $(0,1)$ be a B-square, which causes a wastage of $1$. To fill $(1,0)$, we would need $(1,0)$ or $(2,0)$ to be a another B-square (another wastage of $1$) or, even worse, $(1,1)$ to be a B-square (another wastage of $2$, since it is next to the $(0,1)$ B-square). QED

On a $7\times 7$ board, the $4$ separate $2\times 2$ corners are far apart so that each would cause a wastage of $\ge 2$. Thus filling these $16$ squares alone would cause $w \ge 8$.