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 chessman and place it on the chessboard. Then they moves 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 was already been used. Looser is the one who can not move. Who wins if both are trying to win and Andriy choose: a) a knight; b) a bishop?
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.
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.
Solution
Olesia always wins.
For every chessman the chessboard is divided into couples of squares that are connected by the move of chosen chessman. Then the win strategy of Olesia is as follows: Andriy moves the chessman to the square of some couple (it also concerns to 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 castle 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.
Fig. 20
For every chessman the chessboard is divided into couples of squares that are connected by the move of chosen chessman. Then the win strategy of Olesia is as follows: Andriy moves the chessman to the square of some couple (it also concerns to 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 castle 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.
Fig. 20
Final answer
Olesia wins in both cases (knight and bishop).
Techniques
Games / greedy algorithmsInvariants / monovariantsMatchings, Marriage Lemma, Tutte's theoremColoring schemes, extremal arguments