|
|
A375298
|
|
Length of the longest winning path in n X n Hex.
|
|
2
|
|
|
1, 2, 5, 8, 11, 16, 23, 30, 37, 47, 57, 69, 81, 94, 109, 124, 140, 157, 175, 195, 215, 236, 259, 282, 306, 331, 357, 385, 413, 442, 473, 504, 536, 569, 603, 639, 675, 712, 751, 790, 830, 871, 913, 957, 1001, 1046, 1093, 1140, 1188, 1237, 1287, 1339, 1391, 1444, 1499, 1554, 1610, 1667, 1725, 1785
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A winning path is a set of cells connecting the top edge to the bottom edge, minimal with respect to inclusion.
|
|
LINKS
|
|
|
FORMULA
|
Provably for n >= 10: a(n) = n^2/2 - n/4 - 3/4 if n ≡ 3 (mod 8), and a(n) = floor(n^2/2 - n/4 + 1/4) otherwise.
|
|
EXAMPLE
|
The longest winning path for 10 X 10 Hex has length 47.
====================
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 . . . . . . . . .
====================
|
|
PROG
|
(Python)
def a(n):
if n == 1:
return 1
elif n == 2:
return 2
elif n == 3:
return 5
elif n == 4:
return 8
elif n == 9:
return 37
elif n % 8 == 3:
return (2*n**2 - n + 1) // 4 - 1
else:
return (2*n**2 - n + 1) // 4
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,new
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|