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
Pathological
11.03.2020 19:59
Bob wins by using a simple symmetry argument. Whenever Alice colors a certain cell, Bob colors the one which is symmetric to the one Alice colored w.r.t. the vertical axis of symmetry of the $2020 \times 2020$ board.
In this way, it's easy to check that Bob always earns exactly one more point than Alice earned on the previous move. Hence, Bob wins by $\frac12 \cdot 2020 \cdot 2020 = 2040200$ points with this strategy.
Now we will show that this is the maximum amount that Bob can win by. Indeed, we will construct a strategy which allows Amy to lose by at most $2040200$.
Indeed, Amy simply employs a greedy strategy. At each point in the game, she colors in a cell to maximize the number of points that she earns on that turn. With this strategy, it's easy to see that on each turn, Bob can earn at most one more point than Amy did on the previous turn.
In conclusion, Bob has the winning strategy and he can guarantee a win by $\boxed{2040200}.$
MarkBcc168
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$.
TheUltimate123
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.
stroller
22.05.2020 20:43
Refer to the square in the $i$th row and $j$th column by $(i,j)$. Consider a domino tiling where the dominos connect $(i,2j-1),(i,2j), 1\le j \le n := 1010$ and $1\le i \le 2n$. $B$'s strategy to guarantee $2n^2$ can be coloring the square in the same domino that has been colored by $A$ the last step. $A$'s strategy to make sure an at most $2n^2$ lead is to color in the other square of the domino last colored by $B$ until $B$ visits the domino colored by $A$ that he was supposed to color according to the previous strategy.
We show that after the completion of each cycle, the gain of $B$ increases by at most the number of dominos in the cycle. Let the colored squares be $A_0,B_1\sim A_1, B_2\sim A_2,\dots, B_{l-1} \sim A_{l-1}, B_l$ with $B_l \sim A_0$. Here $\sim$ denotes connected by a domino. When we ignore $A_0$, the point contribution of $B_i$ is one less than the point contribution of $A_i$ for each $1\le i \le l-1$. Moreover $B_l$ contributes $k$ points more than $A_0$ where $k$ is $2\times$ number of dominos colored in the cycle in the same row as $A_0$ prior to the addition of $B_l$. Let $d_i$ denote the difference in point contributions of $B_i$ and $A_i$. We have $d_i = -1\forall 1\le i \le l-1$. Now, put $A_0$ back into consideration when calculating point contributions, the $d_i$ with domino $A_iB_i$ intersecting the column containing $A_0$ receive an increase of at most $1$, and these dominos cannot be contained in the same row as $A_0$. Moreover, all other $d_i$ remain unaffected. Suppose the total number of dominos intersecting the column containing $A$ is $t$, then $k+t \le l-1$, hence the total lead increase $\text{score}(B) - \text{score}(A)$ after the cycle is completed must be at most $(2k+1) + t + (-1)(l-1) \le k + (l-1) + 1 + (-1)(l-1) = k+1 \le l$. After the game is finished, $A$ has forced the board into a disjoint number of cycles whose lengths have sum equal to the number of dominos which is $2n^2$, and each cycle contributes to $B$'s lead of at most the number of points as its cycle length, so $B$ leads by at most $2n^2$ points, as desired.
mathaddiction
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.
L567
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$