Library / /40 of 48

, 2021

Combinatorics Difficulty 6.5 National Olympiad Prove it Hong Kong

There is an $n \times n$ chessboard where $n \ge 4$ is a positive even number. The cells of the chessboard are coloured black and white such that adjacent cells sharing a common side have different colours. Let $A$ and $B$ be two interior cells (which means cells not lying on an edge of the chessboard) of distinct colours. Prove that a chess piece can move from $A$ to $B$ by moving across adjacent cells such that every cell of the chessboard is passed through exactly once.

Solution

For convenience, suppose all cells are unit squares. We first prove two claims.

Claim 1. For any rectangular chessboard, a chess piece can move from one corner to the opposite corner by visiting every cell exactly once if at least one side has an odd length.

Claim 2. For any rectangular chessboard, a chess piece can move from one corner to an adjacent corner by visiting every cell exactly once if the side containing the two corners has an even length.
These can be easily proved by considering a snake-shaped path as shown. The assumptions in the claims are sufficient by checking the parity.

Now, we provide a construction of a path from $A$ to $B$ . Since $A$ and $B$ have distinct colours, the side lengths of the rectangular chessboard with $A$ and $B$ as opposite corners must have different parities. WLOG, assume the vertical side has an odd length and the horizontal side has an even length. Since the whole chessboard has an even length, we may assume there is an even number of rows above $A$ . Partition the chessboard as shown below (the left figure).

even
* Firstly, the chess piece moves from $A$ upwards until it reaches the top edge.
* Then it enters the top-left rectangle and moves from corner $C$ to corner $D$ (by claim 1, since the vertical side has an odd length).
* Next, it enters the bottom rectangle and moves from corner $E$ to corner $F$ (by claim 2, since the horizontal side has an even length).
* Afterwards, it enters the top right rectangle and moves from corner $G$ to corner $H$ (by claim 1, since the vertical side has an odd length).

Then it enters the top rectangle and moves from corner I* to corner J (by claim 1, since the horizontal side has an odd length).
Lastly, it goes back to the rectangle with A* and B as opposite corners and moves to B (by claim 1, since the vertical size has an odd length).
An example is given above (the right figure).

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.