Browse · MathNet
Print55rd Ukrainian National Mathematical Olympiad - Third Round (Second Tour)
Ukraine counting and probability
Problem
Andriy and Olesia play such game. Firstly, Andriy chooses an arbitrary chessman (a king, a queen, a rook, a bishop or a knight) and places it on the chessboard. Then they move in turn by the rules of the chosen chessman. However, it is not allowed to put the chessman on the field that Andriy began from or that has already been used. The loser is the one who cannot move. Who wins if both are trying to win?
Remind that when a knight moves, it can move to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The bishop has no restrictions in distance for each move, but is limited to diagonal movement. The rook moves horizontally or vertically, through any number of unoccupied squares. A king can move one square in any direction (horizontally, vertically, or diagonally).
Fig. 19
Remind that when a knight moves, it can move to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The bishop has no restrictions in distance for each move, but is limited to diagonal movement. The rook moves horizontally or vertically, through any number of unoccupied squares. A king can move one square in any direction (horizontally, vertically, or diagonally).
Fig. 19
Solution
For every chessman the chessboard is divided into couples of squares that are connected by the move of the chosen chessman. Then the winning strategy of Olesia is as follows: Andriy moves the chessman to the square of some couple (this also concerns the first Andriy's choice of placing the chessman) and Olesia moves the chessman to the other square of this couple. She always can move, because after her move for all chosen couples either both squares are used or none are used.
For the king, the queen, the rook it is enough to make couples of the neighboring squares horizontally in 1st and 2nd, 3rd and 4th, 5th and 6th, 7th and 8th columns (see Fig. 19).
For the knight it is enough to make couples of the neighboring squares in 1st and 3rd, 2nd and 4th, 5th and 7th, 6th and 8th columns as is shown in Fig. 20.
For the bishop the couples are made in such a way. Look at all diagonals of one color (black or white) in the direction where they have an even amount of squares. This direction is parallel to the biggest appropriate diagonal that contains 8 squares. Then make couples of the neighboring squares.
For the king, the queen, the rook it is enough to make couples of the neighboring squares horizontally in 1st and 2nd, 3rd and 4th, 5th and 6th, 7th and 8th columns (see Fig. 19).
For the knight it is enough to make couples of the neighboring squares in 1st and 3rd, 2nd and 4th, 5th and 7th, 6th and 8th columns as is shown in Fig. 20.
For the bishop the couples are made in such a way. Look at all diagonals of one color (black or white) in the direction where they have an even amount of squares. This direction is parallel to the biggest appropriate diagonal that contains 8 squares. Then make couples of the neighboring squares.
Final answer
Olesia
Techniques
Games / greedy algorithmsMatchings, Marriage Lemma, Tutte's theorem