A384424 The maximal possible number of 'good' steps in a Hamiltonian cycle on the n X n king's graph, as is specified in the comments.

0, 0, 5, 8, 16, 24, 36, 44

Offset

1,3

Comments

The cycle is drawn on an n X n square grid. Denote the geometric center of the grid by O. An edge a -> b on the cycle is 'good' if the distance from b to O is strictly less than the distance from a to O.

The n = 8 case is Grade 9, Problem 4 of 2025 All-Russian Olympiad.

Links

Table of n, a(n) for n=1..8.

S. I. Tokarev, Problem 9.4 from day one of the last stage of the LI All-Russian Mathematical Olympiad, 2025. [in Russian]

Yifan Xie, Illustration of a(n), n = 2..8, 'good' steps are green, the others are blue and the red circles are the centers of the grids (the construction for n = 6 from Sean A. Irvine).

Example

Proof that a(6) <= 24: Mark the cells on a 6 X 6 grid with the following symbols:
  ABXXBA
  BXXXXB
  XXOOXX
  XXOOXX
  BXXXXB
  ABXXBA
The 4 steps to A and the 4 steps from O must be non-'good'. For each A, the 2 steps to the neighboring B's cannot both be 'good', or they must both be A -> B. So there are at least 4 + 4 + 4 = 12 non-'good' steps, hence a(6) <= 24.

Crossrefs

Cf. A308129.

Sequence in context: A357276 A088586 A350347 * A073136 A063924 A340997

Adjacent sequences: A384421 A384422 A384423 * A384425 A384426 A384427

Keyword

nonn,more

Author

Yifan Xie, May 28 2025

Status

approved