Maths Olympiad Prep

Library / /19 of 19

Combinatorics Difficulty 8.6 Shortlist Find the answer

[i]Superchess[/i] is played on on a 12×1212 \times 12 board, and it uses [i]superknights[/i], which move between opposite corner cells of any 3×43\times4 subboard. Is it possible for a [i]superknight[/i] to visit every other cell of a superchessboard exactly once and return to its starting cell ?

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

Solution

To determine whether a superknight can visit every cell of a 12×1212 \times 12 chessboard exactly once (a Hamiltonian cycle) and return to the starting cell, we must examine the movement capabilities of the superknight.

### Superknight Movement
The superknight on the board moves between opposite corner cells of any 3×43 \times 4 subboard. This move is analogous to the "L" shaped move of a knight in traditional chess but extended to three cells in one direction and four in the other.

### Coloring Argument
To evaluate whether a Hamiltonian cycle is feasible, consider using a coloring argument. We can color the board in a pattern using 2 colors such that no two adjacent cells have the same color.

1. Coloring the Board:
- Color the board such that each 3×43 \times 4 subboard contains alternating colors starting with black (B) and white (W).
- The superknight leap will always land on a square of the opposite color in the context of this coloring.

More precisely, if (i,j) (i, j) is the coordinate of the starting position of the superknight, then its landing position must be (i±3,j±4)(i \pm 3, j \pm 4) or (i±4,j±3)(i \pm 4, j \pm 3). Thus, if it starts on a black square, it must land on a white square each move.

2. Chessboard Dimensions:
- The 12×1212 \times 12 board has an even number of rows and columns, thus it contains an equal number of black and white squares when colored in a checkerboard pattern.
- Given the superknight’s movement (always between opposite colors in our coloring system), for the superknight to return to its starting position (to complete a Hamiltonian cycle), it must make an even number of moves (there has to be parity in the color switches made).

3. Conclusion on Hamiltonian Cycle:
- For the superknight to visit every square once and return to the start, the tour needs to cover an even number of total cells, i.e., 144 moves for the 12×1212 \times 12 board.
- However, the count of moves equals the number of vertices that the superknight passes plus the return trip, leading to one additional trip beyond the 12×12 12 \times 12 based logic, breaking parity.

Therefore, it isn't possible to cover all cells in a single round trip that adheres to the visit each square exactly once constraint while correctly alternating the colors.

Thus, it is not possible for a superknight to visit every cell of a superchessboard exactly once and return to its starting cell.

No \boxed{\text{No}}

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.