Olympiad Maths Prep

Library / /31 of 55

Combinatorics Difficulty 6.0 AIME, harder Prove it Ukraine

Andrew and Olesya in turn cut some squares from the rectangle 4000×20194000 \times 2019, 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)

Figure 1
Fig. 34

Solution

In her first turn Olesya cuts the square 2018×20182018 \times 2018 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.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.