Iranian Mathematical Olympiad

We claim that Arash has a winning strategy if and only if $k\le \frac{1400\times 1401}{3}=1400\times 467$.

First of all, it is obvious if $k>1400\times 467$, then Arash can not color $k$ trominos in his first turn and he will lose. Indeed, there are not $k$ disjoint trominos in the table.

Next, we shall prove that for every $k\le 1400\times 467$, Arash has a winning strategy. We can partition the table into $700\times 467$ number of $2\times 3$ rectangles (intersection of two consecutive columns and three consecutive rows). We count the rectangles in such a way that the rectangles filling the left columns have numbers $1,2,\dots ,467$ (from top to bottom), then the rectangles filling the third and fourth column have numbers $468,469,\dots ,934$, etc. We consider two different trominos in each $2\times 3$ table, as in the figure below.



Now if $k\ge 700\times 467$, Arash will color the trominos of type 1 in all the rectangles and then $k^{\prime }=k-700\times 467$ trominos of type 2 in rectangles of numbers $1,2,\dots ,k^{\prime }$. It is easy to find that after Arash's turn, every $2\times 2$ square has a colored cell. So, Babak can not color any $2\times 2$ square in his turn and Arash will win.

If $k\le 700\times 467$, Arash in his first turn colors the trominos of type 1 in rectangles $1,2,\dots ,k$. For the next turns, suppose that Babak has filled some square and now this is Arash's turn. If he can find $k$ disjoint trominos not intersecting rectangles $1,2,\dots ,k$, he will color them. In the case that there is not $k$ disjoint trominos, let $k^{\prime }$ be the maximal number such trominos ($k^{\prime }<k$). Now, he will color $k^{\prime }$ trominos without intersection with rectangles $1,2,\dots ,k$, and also color $k-k^{\prime }$ trominos in rectangles $1,2,\dots ,k-k^{\prime }$. After this step, there would be no uncolored $2\times 2$ square left in the table and so Babak will lose the game. ■