A $100 \times 100$ table is given. At the beginning, every unit square has number $"0"$ written in them. Two players playing a game and the game stops after $200$ steps (each player plays $100$ steps). In every step, one can choose a row or a column and add $1$ to the written number in all of it's squares $\pmod 3.$ First player is the winner if more than half of the squares ($5000$ squares) have the number $"1"$ written in them, Second player is the winner if more than half of the squares ($5000$ squares) have the number $"0"$ written in them. Otherwise, the game is draw. Assume that both players play at their best. What will be the result of the game ? Proposed by Mahyar Sefidgaran
Problem
Source: Iran MO 3rd round 2016 finals - Combinatorics P2
Tags: Iran, Game Theory, combinatorics, Combinatorial games, table, modular arithmetic
muriloogps
17.09.2016 18:21
Can anyone elaborate a solution?
bgn
17.09.2016 18:48
The game is going to be "draw"
We'll set a strategy for each players so each one won't lose.
Strategy for $1st$ player:
It's enough for the $1st$ player to choose all the rows, each row once.We claim that the $1st$ player doesn't lose in this case. Assume otherwise, which means $2nd$ player, can somehow win the game in this case. Note that the order of moves doesn't matter for the final result, be cause the number written in each cell is only defined by the amount of times that it's chosen, not the order of them. So assume that the $1st$ player does the first $100$ moves and then, $2nd$ player does the other $100$ ones.
By the first $100$ moves, we'll have a table that number $1$ is written in each cell. For any cell that's going to have the number $0$ written in it, it needs to be chosen at least $2$ more times (note that $2nd$ player is playing the rest of the game). Now, if there's more than $5000$ cells with number $0$ in them at the end of the game, we know that only these cells, have to be chosen for more than $2\times5000=10000$ times. But each player chooses exactly $100\times100=10000$ cells. Therefore, it's impossible for the $2nd$ player to win in this case.
Strategy for $2nd$ player.
It's enough for the $2nd$ player to do the exact same moves that the $1st$ player does, which means if the $1st$ player chooses the $i$th row/column, then the $2nd$ player chooses the same row/column.We claim that the $2nd$ doesn't lose in this case. Assume otherwise, that $1st$ player can somehow win.
Note that if a cell is chosen by $1st$ player for $k$ times, it's also chosen by the $2nd$ player for exactly $k$ times.
Now, for any cell with number $1$ written in it, we must have: $2k\equiv1 \pmod 3$ which implies $k \equiv 2 \pmod 3$ so $k \ge 2$
Which means, $1st$ player must choose this cell for at least $2$ times. Same inequality gives us the same contradiction.
muriloogps
17.09.2016 19:02
Nice! Thanks did yiu find it that easy?
bgn
17.09.2016 19:06
muriloogps wrote: Nice! Thanks did yiu find it that easy? Yes, the problem wasn't that hard, actually. I've seen couple of other strategies that also work, so it appears that almost any routine strategy will work in this problem
H.HAFEZI2000
26.07.2018 08:50
lemma: if both side have strategy of not losing then the game will end up draw lemma: if operations $A_1,A_2,...,A_n$ are one then the order would have to effect on the final result! strategy of not losing for $player 2$: choosing the same column or row the first player chooses strategy of not losing for $player one$: because he has $100$ steps then choosing at each of step a different row (so all rows would be selected)
Shayan-TayefehIR
15.09.2022 16:14
For proving that the game's result is draw , we'll show that both players have not losing strategy. $A)$ First player's strategy : If this player chooses each $100$ columns once , then we'll show that the number of zeroes unit at last , is less or equal to $5000$. Suppose that $a_1$ and $b_1$ are number of columns which are chosen $2$ and $1$ times by second player respectively and define $a_2$ and $b_2$ similarly for rows. Now while in unit $(i,j)$ exist number zero if and only if the number of times which $i$'th row and $j$'th column are chosen equals to $(0,0)$ or $(1,2)$ , for the number of zero units and proving this part we have : $$a_1(100-a_2-b_2)+a_2(100-a_1-b_1)=100(a_1+a_2)-3a_1a_2+(a_1-b_1)(a_2-b_2) \le \frac{100^2}{2}$$$$2(a_1+a_2)+b_1+b_2 \le 100 (I)$$Because the $(I)$ value is the minimum movements were the second player makes. So $a_1+a_2 \le 50$ and if $(a_1-b_1)(a_2-b_2) \le 0$ or $a_1 > b_1$ and $a_2 > b_2$ , then we have : $$100(a_1+a_2)-3a_1a_2+(a_1-b_1)(a_2-b_2) \le 100(a_1+a_2) \le \frac{100^2}{2}$$So suppose that $b_1 > a_1$ and $b_2 > a_2$ , then if $b_1+b_2=s$ , one can see that : $$100(a_1+a_2)-3a_1a_2+(a_1-b_1)(a_2-b_2) \le 100(a_1+a_2)+b_1b_2 \le 100(\frac{100-s}{2})+\frac{s^2}{4} \le \frac{100^2}{4} \iff \frac{100s}{2} \ge \frac{s^2}{4} \iff s \le 200$$which is obvious by $I$. $B)$Second player's strategy : Name table's columns as $c_1 , ... , c_{100}$ and rows $r_1 , ... , r_{100}$ , then as a strategy , whenever first player chooses row $r_i$ , second player can choose column $c_i$ and $r_i$ for $c_i$ similarly. Then if $a$ and $b$ are number of rows which are chosen twice and once during the game ( and by the way of game prosses , these numbers are same for columns too. ). So $2a+b \le 100$ and while in unit $(i,j)$ exist number one if and only if the number of times which $i$'th row and $j$'th column are chosen equals to $(2,2)$ or $(0,1)$ , for the number of one units and proving this part we have : $$a^2+2b(100-a-b)=a^2-2ab-2b^2+200b \le \frac{100^2}{2}$$So while $P(a)=a^2-2ab$ is a parabola and $0 \le a \le \frac{100-b}{2}$ , we just need to check this inequality in $a=0 , \frac{100-b}{2}$ and by $AM-GM$ we have : $$2b^2+\frac{100^2}{2} \ge 200b$$$$3b^2+100^2 \ge 200\sqrt{3}b \ge 200b$$So we're done.