What is the minimal number of pieces to surround n pieces in a Go game?

Question

Go is a game of black and white pieces on a lattice of $19\times 19$. Pieces have liberty by having empty spaces next to them and are killed if the liberty are occupied by the opponent. Pieces are connected if they are next to each other (vertical/horizontal connection only, not diagonal connection) and share their liberty.

For the problem, we assume it's played on an infinite lattice $\mathbb{Z}^2$.

The problem is, for $n$ pieces, what is the least liberty they can have? for example, for two pieces, we can make it like XX and there will be $6$ liberty, make it XOX then $7$, and XOOX then $8$. Then the answer is $6$. Here is the construction for small numbers.

we have a conjecture on OEIS saying that the answer is $2+\lceil\sqrt{8n-4}\rceil$. But It doesn't have the proof, or at least I didn't see it.

I have some trivial thinking about the problem:

1. This minimum value must exist and can be reached. Since they are all integers, this is obvious.

2. The pieces must be connected. For situations where they are not connected, connecting them can reduce the amount of liberty. (Edit: for $n=2$, this is incorrect, because the direct or diagonal connection both give $6$, meaning the proof is invalid. Probably the statement is "it has to be connected or 'connected' diagonally, and we can always find a connected construction if a non-connected solution exists." And for greater $n$, this statement should be right. But I can't yet prove it.)

3. For a shape of $n$ pieces, you can always take away a piece from the edge and achieve the same number of liberty or less. This is not obvious enough because you have to choose "convex" edges, otherwise he will actually have more liberty. We need to prove that there is always a point that can be taken away so that the number of liberty does not increase. Our idea of ​​proof is: if all the pieces are "concave", the number of pieces will explode to infinity. First, when taking away a piece, we check whether there are pieces in all four directions. For example, the piece's coordinates are $(a, b)$, then we check $x<a, x>a, y<a, y>a$ whether there are pieces in the four regions. Once there are no pieces in one of the regions, then this is the piece we want to take away, since at this time, there are only three positions around the piece that can affect the changes of liberty upon removal. Just enumerate all possibilities. And if there are always pieces in the four directions, we will find that the distribution of pieces is unbounded, which contradicts with the finite number of chess pieces.

4. This sequence is constant or increasing. This is a corollary of 3.

5. The chess shape that reaches the minimum value should have no eyes (meaning holes inside the shape), and even if it does have eyes, there will be a solution without eyes. For the case where there are eyes, just remove a piece from the edge and fill in the eyes (this is also a corollary of 3).

Can anyone figure out or find the full proof?

Answer 1

As pointed out by Izaak van Dongen in the comments, this problem is solved in the paper Discrete Isoperimetric Problems by Da-Lun Wang and Ping Wang.

The paper has two main results: solving this problem for a set of points in $I_+^n$ (an $n$-fold Cartesian product of the nonnegative integers) and for a set of points in $I^n$ (an $n$-fold Cartesian product of the integers). Here, we are interested in the problem for $I^2$, in their notation.

The authors prove that the optimal solution is to place pieces by filling in the "diamond" sets of the form $\{(x,y) : |x|+|y|=m\}$ one at a time, first for $m=0$, then for $m=1$, then for $m=2$, and so on. There is $1$ piece in the $0^{\text{th}}$ diamond, and $4m$ pieces in the $m^{\text{th}}$ diamond for all $m \ge 1$, so the first natural stopping points to consider are the values $$n = 1 + \sum_{j=1}^m 4j = 2m^2 + 2m + 1$$ where we've just filled in the $m^{\text{th}}$ diamond. At this point, there are exactly $4m+4$ liberties: the points in the $(m+1)^{\text{th}}$ diamond.

In the middle between two natural stopping points, we must fill out the $(m+1)^{\text{th}}$ diamond in a reasonably sane order. In the paper, optimality is proved for a specific sane order described in §6. However:

• In the $n=2$ special case, a simpler description is "go counterclockwise, starting at a point just after one of the four corners of the diamond".
• It all adds up to the sequence in A261491 really giving the minimum number of liberties, as conjectured; the interesting part of the paper is that it proves optimality, which I am not going to reproduce here.

Answer 2

To prove the conjecture you need to show that $2 + \sqrt{8n - 4}$ is always enough and that lesser number is not enough. Here I give a scheme for the first part. (And I guess this conjecture appeared as a consequence of similar thoughts.)

Let $n = k^2 + (k - 1)^2 = 2k^2 - 2k + 1$ for $k \ge 1$. We can arrange $k^2$ pieces into a square $k \times k$ rotated by $\frac{\pi}4$ and add $(k - 1) \times (k - 1)$ pieces between them. (Like for $n = 1$ and $n = 5$.) Then liberty of such structure is $$4k = 2 + \sqrt{(4k - 2)^2} = \sqrt{16k^2 - 16k + 4} = \sqrt{8n - 4}.$$

Let $n = k^2 + (k - 1)k = 2k^2 - k$ for $k \ge 2$. (Case $k = 1$ gives $n = 1$ which is already considered.) We can append to the previous case $k - 1$ pieces, each of which is adjacent to two pieces of the same side of the previous square. (Like for $n = 6$.) It increases liberty by $1$, and $$4k + 1 = 2 + \lceil\sqrt{(4k - 1)^2 - 1}\rceil = 2 + \lceil\sqrt{16k^2 - 8k}\rceil 2 + \lceil\sqrt{8n - 4}\rceil.$$

Let $n = k(k + 1) + (k - 1)k = 2k^2$ for $k \ge 1$. We can arrange $k(k + 1)$ pieces into a rectangle $k \times (k + 1)$ rotated by $\frac{\pi}4$ and add $(k - 1)k$ pieces between them. (Like for $n = 2$ and $n = 8$.) Then the liberty of this structure is $$4k + 2 = 2 + \sqrt{16k^2} = 2 + \lceil\sqrt{16k^2 - 4}\rceil = 2 + \lceil\sqrt{8n - 4}\rceil.$$

And the last case is $n = k(k + 1) + k^2 = 2k^2 + k$ for $k \ge 1$. Now we can append to the previous case $k$ pieces, each of which is adjacent to two pieces of the same longer side of the previous rectangle. (Like for $n = 3$ and $n = 10$.) It increases liberty by $1$, and $$4k + 3 = 2 + \lceil\sqrt{(4k + 1)^2 - 1}\rceil = 2 + \lceil\sqrt{16k^2 + 8k}\rceil = 2 + \lceil\sqrt{8n - 4}\rceil.$$

Now use your third statement to finish the proof of the first part for all other values of $n$.

The second part is about lower bound. And here I also share an idea, still not rigorous at all. We can notice that for linearly convex (along horizontal and vertical lines) liberty may be equal up to the number of outer sides, which is twice greater than the sum of height and width. And usual square is the construction which minimizes such a sum. On the other hand, some of surrounding pieces may touch both horizontal and vertical borders. This decreases the liberty bound down to the sum of height and width plus $2$. At the same time every pair of vertically or horizontally adjacent pieces of the border increases this bound by $\frac 12$. Therefore the maximum number of pieces for the same liberty is achieved by making some structure close to rotated square. So you can try to formalize this thoughts.

Answer 3

I have a proof of $\lceil2+\sqrt{8n-4}\rceil$ is necessary, but I don't know if it is strict enough. Here is it.

Firstly, remove a piece in the leftmost column of a shape won't increase the liberty, so it is safe to consider the reverse problem: maximum pieces with less or equal than given amount of liberty.

If the pieces divide the whole board into more than one area, fill finite areas with pieces will decrease liberty. Now it is safe to define the surrounding of the shape (for every 8-connected subshape).

A shape can be determined from its angles (including straight angles) in order, so we can just talk about the angles.

If there are two consecutive 270 degree angle, making something like a hole, then fill the hole won't increase liberty. It's easy to check same thing holds for consecutive 180 degree or a 180 followed by a 270.

Since a shape always have interior angle sum to (n-2)x180 degree, the angles should be like: there are $k$ 90 in a circle, put $k-4$ 270 into the gaps, and the remaining 4 gaps can be either empty or have a 180.

Thus the shape must be like an equal-angle octagon. The four sides parallel to coordinates is of length either 1 or 2, the four 45 degree slant sides are jagged in.

Since the above method can apply to all 8-connected components, if there are still multiple, they can only share liberty in the four parallel sides. If such share form a cycle, fill the interior of the cycle won't increase liberty, so the share must form an acyclic graph. But now, for any pair of share, move them together (with their other shares) won't increase liberty, so there must be no share. Thus there must be only one component.

By checking all possible shapes of the above form, we can conclude the result. Here are the actual constructions:

$4k$ liberty: $2k^2-2k+1$ pieces, forming a $k\times k$ slant square, like this:

  X
 XXX
XXXXX
 XXX
  X

$4k+1$ liberty: $2k^2-k$ pieces, forming a $k\times k$ slant square with $k-1$ extra pieces on one side, like this:

  X
 XXX
XXXXX
 XXXX
  XX

$4k+2$ liberty: $2k^2$ pieces, forming a $k\times (k+1)$ slant rectangle, like this:

  X
 XXX
XXXXX
 XXXXX
  XXX
   X

$4k+3$ liberty: $2k^2+k$ pieces, forming a $k\times (k+1)$ slant rectangle with $k$ extra pieces on the longer side, like this:

  XX
 XXXX
XXXXXX
 XXXXX
  XXX
   X

The formula can be written as $\lfloor t^2/8-t/2+1\rfloor$, and the reverse is just $\lceil2+\sqrt{8n-4}\rceil$.