# A construction problem

Recently I was revisiting Harry Fearnley’s collection and became interested in this position from a Dutch magazine:

White cannot make a living group even with an arbitrary number of moves in a row, and it seems like this may be the least amount of black stones required to achieve this (although I’m not sure anyone has claimed that it actually is optimal, so feel free to try to improve it!).

Obviously this question will not get more interesting on bigger boards (20x20, 21x21…), since the same pattern can be easily extended. But how about small boards?

Here are some quickly thrown together solutions for sizes 2-5 to get us started:

2x2

Obviously optimal, since just one stone can’t prevent white from making this shape instead. The two black stones could possibly be placed next to each other, since even after white captures making two eyes is not possible… but if suicide is legal, or if superko is used, white would actually live. So better keep it straightforward like above.

3x3

Obviously optimal, since two stones can always be captured. This strategy of dividing the board in two is very powerful here, but doesn’t really work on bigger sizes (except for 3xN), since it relies on white not being able to form even a false eye inside either territory. Note for instance that surrounding a single corner with three stones wouldn’t work.

4x4

Six stones can be done in a number of different ways, but I can’t make five work. I suspect six is optimal but haven’t proved it.

5x5

This solution wasn’t as immediately obvious to me as the other ones. It seems optimal but I haven’t proved it yet.

Edit: Just realized that we could simply extend the 4x4 pattern for an alternative 8-stone solution with more symmetry:

But we can’t keep extending like this for bigger sizes, since then there’s too much room in the corner!

Would anyone like to try their hand at sizes 6, 7, 8, 9? Or perhaps some rectangular boards?

At some point the solutions will start to look very similar to the 19x19 solution, but based on the diversity of sizes 2-5 I think we will see some more interesting ones before then!

9 Likes

I like this challenge but too difficult for me. I will leave it for others but I look forward to seeing the solutions

2 Likes

Here’s some more attempts:
(didn’t try super hard to optimize these, so I’m sure there’s improvements possible!)

6x6, 12 stones

7x7, 17 stones

8x8, 23 stones

9x9, 28 stones

Table of upper bounds so far
Size Stones
2 2
3 3
4 6
5 8
6 12
7 17
8 23
9 28

Looking at the 19x19 pattern, it seems very likely that the values will trend to (n^2)/3 for big boards. The fit actually isn’t half bad already for these values:

(dotted line = (n^2)/3, red line = values from table above)
(sorry for bad plot, plotting is not my strong suit )

7 Likes

how about taking the 5-1 stone off, doesnt that work just as well? So 27?

edit: ahh nevermind, i see it now xD

1 Like

Then white can capture

Edit: But 27 is actually possible on 9x9 with a slight modification!

Edit2: And 21 is doable on 8x8! (I’ll post more diagrams tomorrow)

5 Likes

Improvements inspired by the original 19x19 solution:

7x7, 16 stones

8x8, 21 stones

9x9, 27 stones

Now there are only two values which do not agree with the simple formula:

size stones floor(area/3)
0 0 0
1 0 0
2 2 1
3 3 3
4 6 5
5 8 8
6 12 12
7 16 16
8 21 21
9 27 27
19 120 120

(sizes 0 and 1 thrown in for completeness… white can’t make a living group on 0x0 or 1x1 board )

Note that for square boards, floor(area/3) = round(area/3), since n2 mod 3 ≠ 2. It remains to be seen whether flooring or rounding fits better for rectangular boards.

4 Likes

So do you think the 4x4 is an exception because it might be impossible to make a living shape with less than 6 stones, that is living in the sense of passing forever as opposed to the usual sense? (given a big enough board I suppose has to be added)

1 Like

Well 4x4 is small enough that 5 stones suffices to be pass-alive, it’s just unfortunate that it leaves enough space for white to live…

I would say that it’s not surprising that small boards show some irregularites, the surprising part is how quickly the approximate formula is (as far as we can tell so far) exact!

The reason the values approach area/3 in the limit is of course this repeating pattern where the stones make up exactly 1/3 of the area:

This tells us that the sequence should be n2/3 + O(n), but a priori there’s no reason to expect it to be close to n2/3 for small n.

For instance, if we try this other repeating pattern, which also covers exactly 1/3 of the area:

… we find that “finishing off” the chains when they reach the edges requires a lot more work, so the O(n) term is a lot more noticable.

5 Likes

Nice problem!

We could break formula with less stones too:

1 Like

Unfortunately, we always need at least one black stone on the first line, otherwise white can live with “locally false” eyes in the corners!

5 Likes

You are right! You could even strengthen white’s position to be alive with arbitrary number of black moves too.

I’m happy to see that this thread is still getting some interest, so let me share a few more diagrams to make the “obvious” repeating pattern a bit more explicit

Here are solutions for 8x8, 9x9 and 10x10:

In each case, number of stones = floor(area/3). To create a solution for any larger square board, pick the boardsize above with the same remainder mod 3, then extend the repeating pattern down and to the left.

For instance, 9x9-solution gets extended to 12x12-solution like so: (newly added stones in white)

This “proof by ellipsis”, along with the earlier solutions for sizes 5 to 7, establishes:

Theorem. On an n*n go board with n > 4, the number of stones required to prevent the opponent from making a living group (even with an arbitrary number of moves) is at most n2/3.

It also seems extremely likely that this is optimal, except for possibly some minor improvement we’ve missed on the small boards (before the regular pattern kicks in around size 8).

3 Likes

What is it?

I searched different patterns.
My quick result is to be optimal:
(If you go with not small boards which are specific cases)

Black need two eyes. If not you need to prevent white to make eyes or fake eyes, see at the end of the post)
Black stones should form one group only (or you need more eyes and you will have more sub areas to manage).
Note that the double snake pattern with two fake eyes to live doesnt seem that efficient.
It’s better to use the corner as the center to make the two eyes.
When there is a central axe symetry, it’s interesting to use it to spare moves although i didn’t succeed on a 9x9.
One approach could be useful for exploring when black don’t have two eyes is to deny white to make smallest living shapes for n-2 sub areas, if n is the number of subareas. And to have no eyes or fake eyes at all in the remaining two areas.

Just a joke meaning that it’s not a very solid proof, I skipped over some of the details

(Ellipsis are often used to mean something like “and so on in that manner”: 1, 2, 3, …)

Some other nice proof techniques.

4 Likes

I’d call this proof by picture, though. Which is perfectly fine, because I say so (proof by authority).

I miss ‘proof by leaving it as an exercise for the reader’ in that list

7 Likes
9 Likes

This is exactly how the biweekly meetings for my reading group turn out