Browse · MathNet
Print59th Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
Andrew and Olesya in turn cut some squares from the rectangle , following the lines in such a way that after every turn the remaining figure stays connected. The one who cannot make a move loses. Who is going to win if both children play the best they can, and Olesya is first?
(Bogdan Rublyov)
Fig. 34
(Bogdan Rublyov)
Solution
In her first turn Olesya cuts the square as shown in fig. 34.
After this move Olesya can follow the symmetric strategy, with the only not trivial moves regarding the black unit squares.
However, if Andrew is able to cut (w.l.o.g.) the left black square then it implies that all squares to the left were cut as well. Because of the symmetric play it also implies that all squares to the right were cut, meaning that Olesya can cut the right black square.
After this move Olesya can follow the symmetric strategy, with the only not trivial moves regarding the black unit squares.
However, if Andrew is able to cut (w.l.o.g.) the left black square then it implies that all squares to the left were cut as well. Because of the symmetric play it also implies that all squares to the right were cut, meaning that Olesya can cut the right black square.
Final answer
Olesya
Techniques
Games / greedy algorithms