A375298 Length of the longest winning path in n X n Hex.

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

Offset: 1

Author

Peter Selinger, Aug 12 2024

Keywords

• easy
• nonn

Comments

A winning path is a set of cells connecting the top edge to the bottom edge, minimal with respect to inclusion.

Examples

			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 . . . . . . . . .
          ====================
		

Links

• Peter Selinger, Table of n, a(n) for n = 1..10000
• Peter Selinger, Longest winning paths in Hex, arXiv:2408.05601 [math.CO], 2024.

Crossrefs

Number of solutions is A375299.

Cf. A357234.

Programs

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

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.