Skip to main content
OlympiadHQ

Browse · MathNet

Print

65th Czech and Slovak Mathematical Olympiad

Czech Republic counting and probability

Problem

There is a figure of prince on a field of a 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 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:
123412
234123
341234
412341
123412
234123
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 the numbers of visited fields, then it follows that among is each number (from to ) exactly once ( and are different numbers with the same parity, and as well, only the parity is different). From the same reasons, any of the four numbers is among for arbitrary . Between the numbers is thus any of the numbers to exactly eight times.

The number is on the chessboard just eight times, thus none of can be . The numbers and have the same parity and are different (they are the length two move apart). The number is not among them, therefore both must be odd. Then has to be even and as well. Thus it has to be number .

The initial field () 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 on both chessboards, we come to a contradiction. The initial field cannot be chosen.
Final answer
No, it is impossible to choose such a starting field.

Techniques

Coloring schemes, extremal argumentsInvariants / monovariants