Alice and Bob take turns alternatively on a $2020\times2020$ board with Alice starting the game. In every move each person colours a cell that have not been coloured yet and will be rewarded with as many points as the coloured cells in the same row and column. When the table is coloured completely, the points determine the winner. Who has the wining strategy and what is the maximum difference he/she can grantees? Proposed by Seyed Reza Hosseini
Problem
Source: Iran TST2 Day1 P2
Tags: combinatorics, 2020, game
11.03.2020 19:59
12.03.2020 06:36
Same as above The answer is Bob wins with difference $2\cdot 1010^2$. Alice's strategy: Alice needs to repeatedly pick cells that will acheive most points for that turn. It's easy to see that Bob will get at most one point ahead in the next turn so Bob will have at most $2\cdot 1010^2$ points lead. Bob's strategy: Bob keeps making the table symmetric around the vertical axis. This will guarantee that Bob will get points equal to Alice from the column while getting a one point lead from the row. Hence Bob can make a one-point lead every turn so he can guarantee the difference $2\cdot 1010^2$.
21.03.2020 23:27
Solved with goodbear and Th3Numb3rThr33. Bob wins, earning $2020^2/2$ points. Just note that: Bob can always earn at least $2020^2/2$ points by playing the reflection of Alice's move across the midline, $~$ If Alice plays greedily, so that on each move, she earns as many points as possible, Bob can earn at most one more point than she, so he earns at most $2020^2/2$ points. The end.
22.05.2020 20:43
28.03.2021 07:03
$B$ always won, and he can ensure that he wins by $$\frac{2020^2}{2}=2040200$$points. Indeed, divide the board into $1\times 2$ subboards, when ever $A$ fill in a cell in one of the $1\times 2$ subboard, $B$ will fill in the other cell. Notice that the score $A$ by filling in that cell is exactly one less than that of $B$, hence after $\frac{2020^2}{2}$ turns $B$ will lead by exactly that much. On the other hand, $A$ will apply the greedy algorithm by coloring the cell which maximize his score. Let $T$ be the score of the empty cell with the highest score, then in each turn $T$ can only increase by $1$, in other words $B$ can only increase his lead by $1$. Therefore, $A$ can always cut the lead down to $\frac{2020^2}{2}$ points.
16.02.2022 14:30
Replace $2020$ with $n$, the answer is $2n^2$. For Bob's strategy, he partitions the board into dominoes and each time Alice plays in a square, he plays on the corresponding square of the domino, this way he ensures that he gets exactly one more than whatever Alice got the previous move, and since there are $2n^2$ moves, he can get a difference of at least $2n^2$. For Alice's strategy, we claim that after $k$ moves Bob can have at most $k$ more points than Alice. To do this, each time, Alice plays in the square that gets her the most points. Then when Bob plays, he can get at most how much Alice got $+1$ for the square Alice just colored, so he still can have at most $k+1$ points, so at the end, he leads by at most $2n^2$ points. $\blacksquare$