|
|
A320666
|
|
a(n) is the maximum number of liberties a single group can have on an otherwise empty n X n Go board.
|
|
1
|
|
|
0, 2, 6, 9, 14, 22, 29, 38, 51, 61, 74, 92, 105, 122, 145, 161, 182, 210, 229, 254, 287, 309, 338, 376
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
For 1 X 1 the solution is a single stone on the only possible position and is not a valid final board state in a real game of Go.
Also seems to be the answer to the following parking problem: maximum number of cars in an n X n carpark such that any car can leave through a single exit. See Puzzling StackExchange links. - Dmitry Kamenetsky, Mar 26 2021
|
|
LINKS
|
|
|
FORMULA
|
Exact for n <= 24, conjectured for n > 24 but it is at least a lower bound:
a(n) = 0 if n = 1.
a(n) = 2 if n = 2.
a(n) = 6 if n = 3.
a(n) = n*(2*n-1)/3 if n = 0 (mod 3) and n != 3.
a(n) = ((2n-1)^2+5)/6 if n = 1 (mod 3) and n != 1.
a(n) = ((2n-1)^2+3)/6 if n = 2 (mod 3).
G.f.: x^2*(2 + 4*x + 3*x^2 + x^3 + x^5 + x^6 + x^7 - x^8) / ((1 - x)^3*(1 + x + x^2)^2).
a(n) = a(n-1) + 2*a(n-3) - 2*a(n-4) - a(n-6) + a(n-7) for n>9.
(End)
|
|
EXAMPLE
|
For n = 7 one of many a(7) = 29 solutions:
*********
*.O.....*
*.OOOOOO*
*.O....O*
*.O.....*
*.O.OOO.*
*.OOO.O.*
*.O...O.*
*********
|
|
PROG
|
(Perl)
sub a {
# Conjectured: This program is valid for any m X n board size
my ($m, $n) = @_;
$n = $m if !defined $n;
($m, $n) = ($n, $m) if $m > $n;
# So now $m <= $n
# This program is certain to be valid for all $m <= 24
if ($m >= 4) {
return $m*(2*$n-1)/3 if $m % 3 == 0;
return $n*(2*$m-1)/3 if $n % 3 == 0;
return ((2*$m-1)*(2*$n-1)+5)/6 if $m % 3 == 1 && $n % 3 == 1;
return ((2*$m-1)*(2*$n-1)+3)/6; # if $m % 3 == 2 || $n % 3 == 2
}
return 2*$n if $m == 3;
return $n == 3 ? 4 : $n if $m == 2;
return $n >= 3 ? 2 : $n-1 if $m == 1;
die "Bad call";
}
|
|
CROSSREFS
|
A071619 is a trivial upper bound for this sequence.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|