Olympiad Maths Prep

Library / /15 of 16

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Czech Republic

There is a figure of prince on a field of a 6×66 \times 6 square chessboard. The prince can in one move jump either horizontally or vertically. The lengths of the jumps are alternately either one or two fields, and the jump on the next field is the first one. Decide, whether one can choose the initial field for the prince, so that the prince visits in an appropriate sequence of 3535 jumps every field of the chessboard.

Solution

Let us suppose the appropriate sequence exists and let us enumerate the fields of the chessboard as follows:

| 1 | 2 | 3 | 4 | 1 | 2 |
|---|---|---|---|---|---|
| 2 | 3 | 4 | 1 | 2 | 3 |
| 3 | 4 | 1 | 2 | 3 | 4 |
| 4 | 1 | 2 | 3 | 4 | 1 |
| 1 | 2 | 3 | 4 | 1 | 2 |
| 2 | 3 | 4 | 1 | 2 | 3 |

The length one moves go from odd to even number and vice versa. The length two moves go from even to a different even number or from odd to a different odd number. If we denote P1,P2,,P36P_1, P_2, \dots, P_{36} the numbers of visited fields, then it follows that among P2,P3,P4,P5P_2, P_3, P_4, P_5 is each number (from 11 to 44) exactly once (P2P_2 and P3P_3 are different numbers with the same parity, and P4,P5P_4, P_5 as well, only the parity is different). From the same reasons, any of the four numbers is among P4k+2,P4k+3,P4k+4,P4k+5P_{4k+2}, P_{4k+3}, P_{4k+4}, P_{4k+5} for arbitrary k{0,1,,7}k \in \{0, 1, \dots, 7\}. Between the numbers P2,P3,,P33P_2, P_3, \dots, P_{33} is thus any of the numbers 11 to 44 exactly eight times.

The number 44 is on the chessboard just eight times, thus none of P1,P34,P35,P36P_1, P_{34}, P_{35}, P_{36} can be 44. The numbers P34P_{34} and P35P_{35} have the same parity and are different (they are the length two move apart). The number 44 is not among them, therefore both must be odd. Then P36P_{36} has to be even and P1P_1 as well. Thus it has to be number 22.

The initial field (P1P_1) thus has to be one of the coloured fields on the left chessboard. One can repeat the arguments for the numbering of the right chessboard (just a rotation of the left one). Since no field has number 22 on both chessboards, we come to a contradiction. The initial field cannot be chosen.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.