Arash and Babak play the following game, taking turns alternatively, on a $1400\times 1401$ table. Arash starts and in his turns he colors $k$, $L$-corners (any three cell of a square). Babak in his turn colors one $2\times 2$ square. Neither player is allowed to recolor any cell. Find all positive integers $k$ for which Arash has a winning strategy.
Problem
Source: Iran MO Third Round 2021 F4
Tags: combinatorics
26.09.2021 18:38
kinda hard to write we prove that for all $k\leq \frac{1400\cdot 1401}{3}$ Arash wins and Babak wins for the rest. first if $k$ is more than said amount, Arash clearly loses as he can not fit that many $L$ s in the grid thus can't even make the first move. suppose our grid has $1401$ rows and $1400$ columns. divide the board into $\frac{1400\cdot 1401}{6}$ vertical $2$x$3$ tiles. call these "houses" if $\frac{1400\cdot 1401}{6}\leq k \leq \frac{1400\cdot 1401}{3}$ then by filling the top left corners of each house and for what's left of his tiles, completing the necessary houses, Babak can't even make his first move so Arash wins. XX XY YY ^ putting the tile on the X's is"filling the top left corner" and putting a tile in Y means "completing the house" now if $K\leq \frac{1400\cdot 1401}{6}$: for the first move, Arash marks $k$ houses this way: starting from the bottom right house, each time he marks the bottom house which has not been marked of the left most column of houses (these are 2 columns stuck together) that has at least 1 unmarked house. he marks these until he has marked $k$ houses. now, he fills the top left corner of every marked house. for example, this is the order that would mark a 8x6 board with 4x2 houses: 8 6 4 2 7 5 3 1 now he puts an x in all of the cells of the $k$ houses he has marked in the start. it is clear that Babak can't put a 2x2 that also contains one of these cells that contain x. from now on Arash plays as such: as long as there is an empty 2x2 space in the board that doesn't contain an x, he puts his corner there. if at a point there is no such space, suppose he has to still put $r\leq k $ corners, he will complete $r$ of the $k$ marked houses. after this turn, Babak has no move thus Arash wins. so arash wins either way