Placing units on a board which produces some revenue (two types of units)

Question

My problem is about filling an $m\times n$ board with $A$'s and $B$'s to get the maximum possible score. The score is computed by these rules. Let $y\ge 1$ be a real number.

• Each $A$ which is not edge-adjacent to a $B$ is worth one point.

• Each $A$ which is edge-adjacent to a $B$ is worth $y$ points.

• Each $B$ is worth zero points (the only value of $B$ is to increase the value of neighboring $A$'s).

Question: In terms of $y$, what is the maximum possible score?

My thoughts: If $y < 1$, it's simply best to fill the whole board with unit $A$s. If, $y \geq 2$, then it seems the placing would be more complicated. The solution for this case seems to be above my weight class.

Answer 1

First, a single B can be adjacent to up to 4 A's, making a cross shape. If $y \le 5/4$ this is worse then just placing 5 A's so for such $y$ the best solution is just to place A's everywhere regardless of board size.

If $y > 5/4$ this cross shape with a B surrounded by 4 A's gives the most points per field of the board. One can't fill any rectangular grid completely with these crosses but one can arrange them without any empty spaces inbetween so the only problem arises around the edges of the board. So if the board is very large, filling the entire center with these crosses is best.

For the edges you can start with all A's and then check whether you can improve this a bit by placing a few more B's that are adjacent to 2 or 3 A's. Whether this helps depends on whether $y > 3/2$ and $y>4/3$ and the optimal configuration will take some trial and error.

Answer 2

Whenever $y\le 5/4$, it is optimal to fill the board with $A$'s. This is because the added value of a $B$ square is at most $4(y-1)$, which is achieved when the $B$ is adjacent to four other $A$'s which were not boosted by other $B$'s. If $y$ is too small, then this added value is less then the value of an $A$.

If instead $y\ge 3/2$, then I believe that the following strategy is close to optimal. Place $B$'s at the following spots, and fill the rest with $A$'s. When you do this, almost every $A$ square is boosted. The only unboosted squares are those marked with *. Furthermore, every $B$ is placed "efficiently", in the sense that no squares are wastefully double-boosted.

_ B _ _ * _ B _ 
_ _ _ B _ _ _ *
B _ _ _ _ B _ _
_ _ B _ _ _ _ B
* _ _ _ B _ _ _
_ B _ * _ _ B _

The exact description of this pattern to fill a square in the $i^\text{th}$ row and $j^\text{th}$ column with a $B$ if and only if $i+2j$ is a multiple of five. In general, this assures that all of the internal $A$'s are boosted, and most of the $A$'s on the border are boosted as well. Alternatively, you can choose a number $r\in \{1,2,3,4\}$, and place $B$ at $(i,j)$ if $i+2j+r$ is a multiple of five. Different values of $r$ should give comparable scores, so you can just choose whichever happens to be best.

If you only have $4/3\le y<3/2$, then a similar strategy works, with the following exception; if the strategy tells you to place $B$ in a corner, then place an $A$ there instead.

If you only have $5/4 \le y <3/2$, then you should do the same strategy, except you refuse to place a $B$ in either a corner square or an edge square.