Zombie Survival: What is the optimal way to place seven entities on an infinite grid to reduce number of adjacent pairs?

Solution 1:

For a small number of players, we can find minimal configurations by hand. Here are some ($n$ is the number of players, $z$ is the total zombie count, and the numbers in the diagrams show each player's individual zombie count):

n=1, z=8: 8

n=2, z=14: 7 7

n=3, z=18: 6
           6 6

n=4, z=20: 5 5
           5 5

             5
n=5, z=24: 5 4 5  or  5 4 
             5        5 4 6

n=6, z=26: 5 3 5
           5 3 5

           5 4        5 4
n=7, z=28: 3 2 5  or  4 2 4
           5 4          4 5

I think these are unique minimal configurations up to reflection and rotation.

At the other end of the scale, we can look at what happens when $n$ becomes very large. In the limit, we can ignore corner effects, which simplifies the analysis. Suppose we arrange the players in a square $a \times a$ grid, so that $n = a^2$ and $-$ ignoring corner effects $-$ $z = 12a$ (because each edge player has an individual zombie count of $3$). So we get, for a square grid in the limit: $$n=\frac{z^2}{144}$$

Now let's try to round off the corners, by constructing an octagon like this:

      x x x x x x
    x x x x x x x x
  x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x x x x x x x x x x
  x x x x x x x x x x
    x x x x x x x x
      x x x x x x

where the horizontal and vertical edges contain $a$ players, and the diagonal edges contain $b$ players. In the diagram, $a=6$ and $b=4$ (this double-counts the corners, but we don't care about corner effects here because we are interested in the limiting behaviour as $n$ becomes large). All players on an edge have individual zombie counts of $3$, but players in the second rank of a diagonal edge have a zombie count of $1$. So we get: $$z = 12a+16b$$ $$n = a^2 + 4ab + 2b^2$$ Suppose $z$ fixed. Then the first equation gives us $b$ in terms of $a$, which we can substitute in the second equation to give a quadratic equation in $a$. Then we can find the maximum value for $n$ by setting the derivative to $0$. If you do the algebra, you get, surprisingly: $$a = b = \frac{z}{28}$$

(I was surprised, anyway.) So we get, for an optimal octagon in the limit: $$n=\frac{z^2}{112}$$

This is significantly better than a square.

Note that, although $a$ and $b$ are equal, this is not a regular octagon $-$ for that, we would need $a=b\sqrt 2$. The reason that a regular octagon is not best is that diagonals cost fewer zombies per Euclidean unit distance ($2\sqrt 2$) than horizontals and verticals ($3$). So it seems clear that the limiting shape is not a circle.

Edited to add: The zombie cost per unit distance along the edge depends on the slope $\delta$ as follows: $$\frac{3|\delta|+1}{\sqrt{1+\delta^2}} \text{ if } |\delta| \ge 1$$ $$\frac{|\delta|+3}{\sqrt{1+\delta^2}} \text{ if } |\delta| \le 1$$

Perhaps better brains than I can work out the optimal limiting shape from this.

Solution 2:

If we wish to maximize area given the perimeter then the optimal figure is a circle.

In the discrete case you have to do a complete enumeration of all possible positions, but the optimal shape will be close to a "circle".

I guess in the case of 7 players it would be something like

ooooo
ooxoo
oxxxo
oxxxo
ooooo