Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 6.6 National olympiad Find the answer

Esmeralda has created a special knight to play on quadrilateral boards that are identical to chessboards. If a knight is in a square then it can move to another square by moving 1 square in one direction and 3 squares in a perpendicular direction (which is a diagonal of a 2×42\times4 rectangle instead of 2×32\times3 like in chess). In this movement, it doesn't land on the squares between the beginning square and the final square it lands on.

A trip of the length nn of the knight is a sequence of nn squares C1,C2,...,CnC1, C2, ..., Cn which are all distinct such that the knight starts at the C1C1 square and for each ii from 11 to n−1n-1 it can use the movement described before to go from the CiCi square to the C(i+1)C(i+1).

Determine the greatest N∈NN \in \mathbb{N} such that there exists a path of the knight with length NN on a 5×55\times5 board.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we will analyze the movement of Esmeralda's special knight on a 5×55 \times 5 board and determine the longest possible path without revisiting any square. The knight moves in an "L" shape spanning across a 2×42 \times 4 rectangle, rather than the traditional 2×32 \times 3 from chess. These movements include any moves like (x,y)→(x±3,y±1)(x, y) \to (x \pm 3, y \pm 1) or (x±1,y±3)(x \pm 1, y \pm 3), provided the new position remains on the board.

The solution involves proving the maximum number of distinct squares a knight can visit is 12.

### Steps to Demonstrate the Solution

1. Understand the Movement: The knight moves in 2×42 \times 4 rectangle diagonals. The possible moves, if within board boundaries, are:
- (x,y)→(x±3,y±1) (x, y) \to (x \pm 3, y \pm 1)
- (x,y)→(x±1,y±3) (x, y) \to (x \pm 1, y \pm 3)

2. Determine Board Coverage:
- Begin by attempting to cover the entire 5×55 \times 5 grid without revisiting any square.
- A 5×55 \times 5 board consists of 25 cells, implying that a knight could potentially visit all squares in a perfect path. However, given the board's structure and this knight's movement restriction, not all paths are possible.

3. Build a Long Trail:
- Start from the corner, say (1,1)(1,1), attempting to construct a continuous path using moves detailed above.
- Use backtracking or systematic trial and error to navigate through the board.

4. Calculate Maximum Path:
- Empirically, it's been found that the maximum non-revisiting path length for such a board with the given moves is 12.
- Attempt paths and verify each step stays within the 5×55 \times 5 limits and no square is revisited.

5. Verification of Maximum Length:
- Through various trials, observe if paths longer than 12 squares are feasible, considering edge constraints.
- Verify potential paths visually or through algorithmic approaches. In every feasible attempt, the longest attainable non-repetitious sequence is consistently found to be 12.

Thus, the greatest N N fulfilling the conditions such that there exists a path of the knight of length N N on a 5×55\times5 board is:
12 \boxed{12}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.