Maths Olympiad Prep

Library / /63 of 68

Combinatorics Difficulty 6.6 National Olympiad Prove it Estonia

Let nn and mm be positive integers. On one turn, an nn-mm-knight can move either horizontally by nn squares and vertically by mm squares or vertically by nn squares and horizontally by mm squares. (For instance, the usual chess knight, all possible target squares of one move of which are depicted by bullets in the figure, is a 11-22-knight.) Can an nn-mm-knight on an infinite in every direction chessboard return to the initial square in exactly 20192019 turns?

Solution

Consider three cases:

*Exactly one of the numbers nn, mm is odd.* Color the squares like on a chessboard. Every move changes the color of the square where the knight is, whence after an odd number of moves, the knight is on a square of the opposite color. Thus the knight cannot be on the initial square after 20192019 moves.

*Both numbers nn and mm are odd.* Color the horizontal lines of the board alternately black and white. Again, every move changes the color of the square where the knight is. Hence, similarly to the previous case, the knight cannot be on the initial square after 20192019 moves.

*Both numbers nn and mm are even.* Let n=2kpn = 2^k p, m=2lqm = 2^l q where pp and qq are odd. W.l.o.g., assume that klk \le l and the knight starts from square (0,0)(0,0). Obviously, the knight only visits squares with coordinates of the form (2ku,2lv)(2^k u, 2^l v) since 2k2^k divides the length of the step in either direction. Suppose that the knight is on the initial square after 20192019 moves. Shortening all moves 2k2^k times while retaining their directions, we obtain a route of a pp-2lkq2^{l-k}q-knight which in 20192019 moves returns to the initial square. But pp is odd which means that such route does not exist by previous cases. The contradiction shows that the knight cannot be on the initial square after 20192019 moves.

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.