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

I am designing a zombie-survival type scenario in a tabletop RPG game. My system is going to work in such a way that the players take damage at the start of their turns based on how many adjacent squares on the battle grid are filled with zombies. I want to determine the optimal formation for a group of 7 players to stand to take the least amount of damage.

Assuming no walls or other terrain on the map, so an infinite grid of zombies (Z's), what is the optimal way to position 7 players (numbered) to reduce the number of adjacent pairs with respect to each player? Note that diagonal squares are considered adjacent.

Example:

In the above formation, we can observe the following:

Player 1:  5 Adjacent zombies



What is the minimum possible number of total adjacent zombies, and what is a formation that achieves this number? Are there multiple optimal setups?

Bonus Points: Is there a generic way to solve this problem for a variable number of players in case someone doesn't show up?

-
Zombies...a strange game. The only winning move is not to play. How about a nice game of chess? – Michael McGowan Sep 22 '11 at 15:56
The number of adjacent player-zombie is $8n$ minus the number of adjacent (ordered) player-player pairs. It might be easier to consider maximizing the latter, because you can think of it as a kind of discrete attraction potential. – Rahul Sep 22 '11 at 17:36
@RahulNarain that is certainly a more intuitive way to think of the problem and reinforces Roah's answer nicely. – dpatchery Sep 22 '11 at 18:39

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.

-
BETTER BRAAAINS. – kinokijuf Nov 12 '13 at 20:56

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

-
Zombies, Roah. With a 'Z'. Not Ombies. – TonyK Sep 22 '11 at 15:50
@TonyK: perhaps there was an allusion to the circle - closer to an "O" than a "Z"??! – Mark Bennet Sep 22 '11 at 21:19
It's not a circle $-$ see my answer. – TonyK Sep 24 '11 at 16:47