Maths Olympiad Prep

Library / /484 of 520

Combinatorics Difficulty 6.3 National olympiad Prove it

6. On some square of a 6×66 \times 6 chessboard, we place a prince figure. This figure can jump in one move either vertically or horizontally. The length of this jump alternates between one and two squares, starting with a jump to an adjacent square. Determine whether it is possible to choose an initial position of the figure so that after a suitable sequence of 35 jumps, it visits each square of the chessboard exactly once.

(Peter Novotný)

Solution

Solution. Suppose that a suitable initial position and a sequence of 35 jumps exist, and number the squares of the chessboard according to the following scheme:

123412
234123
341234
412341
123412
234123

Moves of length one lead from an odd number to an even number and vice versa. Moves of length two always lead from an even number to another even number and from an odd number to another odd number. If the visited squares are denoted by P1,P2,,P36P_{1}, P_{2}, \ldots, P_{36}, it follows from the above that among the four squares P2,P3P_{2}, P_{3}, P4,P5P_{4}, P_{5}, each of the numbers is represented exactly once (on P2P_{2} and P3P_{3} are different numbers with the same parity, and similarly on P4,P5P_{4}, P_{5} with the other parity). For the same reasons, each of the numbers is represented exactly once in the quadruples of squares P4k+2,P4k+3,P4k+4,P4k+5P_{4 k+2}, P_{4 k+3}, P_{4 k+4}, P_{4 k+5} for each k{0,1,,7}k \in\{0,1, \ldots, 7\}. Among the numbers on the squares P2,P3,,P33P_{2}, P_{3}, \ldots, P_{33}, each of the numbers is thus represented a total of 8 times.

The number 4 appears on the chessboard only 8 times, so none of the numbers on P1,P34,P35,P36P_{1}, P_{34}, P_{35}, P_{36} can be 4. The numbers on P34P_{34} and P35P_{35} have the same parity and are different (they are separated by a jump of length 2). Since 4 is not on either of them, they must both be odd. Then the number on square P36P_{36} must be even, and the same even number must also appear on square P1P_{1}. Therefore, both must be the number 2.

The initial square must thus be one of those shaded on the left chessboard. However, this argument can also be repeated for the second numbering on the right, which is just a "rotation" of the first numbering. Since no square is shaded on both chessboards, we have reached a contradiction. Therefore, it is impossible to traverse the chessboard in the desired manner, regardless of the initial square chosen.

123412
234123
341234
412341
123412
234123

234123
123412
412341
341234
234123
123412

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.