Maths Olympiad Prep

Library / /128 of 133

, 2015

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Saudi Arabia

Hamza and Majid play a game on a horizontal 3×20153 \times 2015 white board. They alternate turns, with Hamza going first. A legal move for Hamza consists of painting three unit squares forming a horizontal 1×31 \times 3 rectangle. A legal move for Majid consists of painting three unit squares forming a vertical 3×13 \times 1 rectangle. No one of the two players is allowed to repaint already painted squares. The last player to make a legal move wins. Which of the two players, Hamza or Majid, can guarantee a win no matter what strategy his opponent chooses and what is his strategy to guarantee a win?

Solution

Hamza has a winning strategy.
We divide the rectangle into 671671 squares of size 3×33 \times 3 and a small rectangle of size 3×23 \times 2.
Hamza will play as follows: He will paint at each time a horizontal 1×31 \times 3 rectangle in a white 3×33 \times 3 square (all unit squares in this 3×33 \times 3 square are not colored yet) until he cannot continue to do so. In each step, Majid can only paint a 3×13 \times 1 rectangle in a square of size 3×33 \times 3 or in the small rectangle 3×23 \times 2. So the number of 3×33 \times 3 squares that will be used by a rectangle of Hamza is at least 336336.

Note that, whenever Hamza paints a horizontal 1×31 \times 3 in a 3×33 \times 3 square then Majid cannot paint a vertical 3×13 \times 1 in such a square. Hence, Hamza can play at least 336×3=1008336 \times 3 = 1008 steps. Since the game ends after at most 20152015 steps so Majid can play at most 2015−1008=1007<10082015 - 1008 = 1007 < 1008 steps. In other words, Hamza has a winning strategy.

Want a route through all this instead of 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.