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

Author

Yifan Xie, May 28 2025

Keywords

• nonn
• more

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.

Examples

			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.
		

Links

• 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).

Crossrefs

Cf. A308129.