Olympiad Maths Prep

Library / /29 of 29

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Iran

Alice and Bob take turns alternatively on a 2020×20202020 \times 2020 board with Alice starting the game. In each move every person colors a cell that has not been colored yet and will be rewarded with as many points as the colored cells in the same row and column. When the table is colored completely, the points determine the winner. Who has a winning strategy and what is the maximum difference he/she can guarantee?

Solution

We claim that Bob has a winning strategy and the maximum point difference he can make sure will happen is 202022\frac{2020^2}{2}.

First we show Bob's strategy. Let \ell be the vertical line that dissects the table into two equal tables. After Alice colors a cell, Bob can easily color the cell symmetric to that cell with respect to \ell. This way, Bob gets the same point Alice got from the column and gets one more point than Alice got from the row, because the cell he colored is in the same row as Alice's cell. So after each move, Bob earns exactly one more point than Alice, which means at the end he has earned 202022\frac{2020^2}{2} points more than Alice.

Now we show that Alice can make sure the difference will not be greater than 202022\frac{2020^2}{2} points. In each move, Alice chooses the cell that she can earn the maximum possible points by coloring. Assume that she earns pp points by this move. Because it is the maximum choice, any cell that Bob chooses in the next move will be in the same row or column with at most p+1p+1 colored cells. This means the point difference in the end will be at most 202022\frac{2020^2}{2} and we're done.

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.