Sahand and Gholam play on a $1403\times 1403$ table. Initially all the unit square cells are white. For each row and column there is a key for it (totally 2806 keys). Starting with Sahand players take turn alternatively pushing a button that has not been pushed yet, until all the buttons are pushed. When Sahand pushes a button all the cells of that row or column become black, regardless of the previous colors. When Gholam pushes a button all the cells of that row or column become red, regardless of the previous colors. Finally, Gholam's score equals the number of red squares minus the number of black squares and Sahand's score equals the number of black squares minus the number of red squares. Determine the minimum number of scores Gholam can guarantee without if both players play their best moves.
Problem
Source: Iran MO 2024 second round P5
Tags: combinatorics, games
20.04.2024 12:03
The final answer is $1403$
20.04.2024 14:09
My solution during the exam: Let $r_i$ and $c_j$ be $i$-th row and $j$-th column respectively. Let $T$ be the best score that the second player can achieve, no matter how the first player acts. Claim 1. $T\ge 1403$ Proof. Let the first player choose $r_i$ at one of his moves, if the second player selects $c_i$ and the second player will do the same strategy again and again, it's clear that the cells with coordinate $i,i$ ($1\le i\le 1403$) will be red. Now note that among cells $(i,j)$ and $(j,i)$, one is red, thus the number of red cells is $\ge 1403\times 702$, so $T\ge 1403\times 702 - 1403\times 701=1403$ Claim 2. $T\le 1403$ Proof. Here is the strategy for first player: Each time, he will choose the largest amount of $k$ such that $r_1,\dots,r_{k-1}, c_1,\dots,c_{k-1}$ are already chosen, and then he selects $r_k$ if it isn't selected, else he will choose $c_k$. It's clear that this strategy works perfectly since the cell $(i,j)$ , $i<j$ is red, if $c_j$ is chosen by the second player and the cell $(i,j)$ , $i>j$ is red, if $r_i$ is chosen by the second player, thus the number of red cells at the end is$\le 1+2+\dots +1403=1403\times 702$, so $T\le 1403$ and we are done!
30.04.2024 04:12
Gholam can always guarantee a score of $\boxed{1403}$. Gholam's strategy to ensure he gets to a score of 1403: If Sahand changes a coulmn then Gholam should change a row and if Sahand changes a row then Gholam should change a column. We will show that every set of turns Gholam's score increases by exactly $1$. Let Sahand and Gholam have previously turned over $S_R$, $S_C$, and $G_R$, $G_C$ rows and coulmns respectively. Notice $S_R=G_C$ and $S_C=G_R$. WLOG assume that Sahand chooses to turn over a row next. Then Sahnd's score will increase by $n-S_C+G_C$. On his turn, Gholam's score will increase by $n-G_R+S_R+1$. Then Gholam gains a point each round. Sahand's strategy to ensure he gets to a score of -1403: After the first move Sahand should always play perpendicular of Gholam. Using similar reasoning each round Sahand's score will not decrease. Considering that Sahand's score was at $1403$ after the first move then after $2805$ moves he will still be able to guarantee a score of $1403$. Gholam's final move will move his score down to at worst $-1403$. Combined these finish the question.
01.05.2024 00:12
Any solution for the Sahand's strategy with induction?