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 a chess king and places it on the chessboard. Then they move in turn by the rules of the king. However, it is not allowed to put the king on the field that Andriy began from or was already used. The loser is the one who cannot move. Who wins if both are trying to win?
Solution
Olesia always wins.
For every chessman the chessboard is divided into couples of squares that are connected by the move of the chosen chessman. Then the win strategy of Olesia is as follows: Andriy moves the chessman to the square of some couple (it 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.
Fig. 19
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 (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 direction where they have 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 every chessman the chessboard is divided into couples of squares that are connected by the move of the chosen chessman. Then the win strategy of Olesia is as follows: Andriy moves the chessman to the square of some couple (it 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.
Fig. 19
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 (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 direction where they have 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 always wins.
Techniques
Matchings, Marriage Lemma, Tutte's theoremGames / greedy algorithms