Skip to main content
OlympiadHQ

Browse · MathNet

Print

37th Iranian Mathematical Olympiad

Iran counting and probability

Problem

Alice and Bob take turns alternatively on a 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 .

First we show Bob's strategy. Let 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 . 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 points more than Alice.

Now we show that Alice can make sure the difference will not be greater than points. In each move, Alice chooses the cell that she can earn the maximum possible points by coloring. Assume that she earns 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 colored cells. This means the point difference in the end will be at most and we're done.
Final answer
Bob; maximum guaranteed point difference 2020^2/2

Techniques

Games / greedy algorithms