A simple problem came to mind a while ago, but I couldn't think of a clear solution.
Quote:
What is the maximum number of liberties a group can have on an n × n Go board?
We can name a function for this as maxlib(n).
A brute force approach to compute maxlib has insane time complexity. I actually wrote and ran a program to compute this brute force, and could only reach n = 6 after about 2 hours, maybe.
I posted a
programming challenge about this, and still haven't got a fast enough solution, but a user named Loopy Walt did post a convincing conjecture that,
Code:
maxlib(n) = 0, if n = 1
2, if n = 2
6, if n = 3
(2n - 1)⌊n / 3⌋, if n % 3 = 0
(2n - 1)⌊n / 3⌋ + n, if n % 3 = 2
2n⌊n / 3⌋ + 1, otherwise
This conjecture is justified although not proved by the following group patterns.
Code:
n % 3 = 0
............
XXXXXXXXXXXX
.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.
Code:
n % 3 = 2
...........
XXXXXXXXXXX
.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
Code:
n % 3 = 1
..........
XXXXXXXXXX
.X..X..X..
.X..X..X..
.X..X..XXX
.X..X..X..
.X..X..X..
.X..X..XXX
.X..X..X..
.X..X..XX.
An OEIS sequence (
A320666) exists for maxlib. The currently known values are only up to n = 24.
Code:
n maxlib(n)
1 0
2 2
3 6
4 9
5 14
6 22
7 29
8 38
9 51
10 61
11 74
12 92
13 105
14 122
15 145
16 161
17 182
18 210
19 229
20 254
21 287
22 309
23 338
24 376