Team Selection Test for IMO

The answer is $233625$.

Suppose that the centers of unit squares have coordinates $(i,j)$, where $i=1,2,\dots ,2013$; $j=1,2,\dots ,2013$. The unit square with center at $(i,j)$ will be denoted by $u(i,j)$. Let the marked unit squares be: $u(19k,19l+1)$, $u(19k,19l+2)$, where $1\le k\le 105$, $0\le l\le 105$ and $u(m,19n)$, where $1\le m\le 2013$, $1\le n\le 105$. Then it can be readily seen that the total number of marked unit squares is $233625$, and any sub-square $19\times 19$ has exactly $21$ marked unit squares. Let $k\ge 2$ be a positive integer. Now by the method of mathematical induction we show that if any $19\times 19$ sub-square of the grid $(19k-1)\times (19k-1)$ has at least $21$ marked unit squares, then the total number of marked unit squares is at least $M(k)=(k-1)(21k-1)$.

$k=2$. $M(2)=41$. Consider two $19\times 19$ squares: the square consisting all $u(k,l)$, where $1\le k\le 19$, $1\le l\le 19$ and the square consisting all $u(k,l)$, where $19\le k\le 37$, $19\le l\le 37$. Each of these $19\times 19$ squares contains at least $21$ marked unit squares and their intersection is the unit square $u(19,19)$. Therefore the total number of marked unit squares is at least $21+21-1=41$. Done.

Suppose the statement is correct for a $((19k-1)\times (19k-1))$ grid $A$ and consider a $((19(k+1)-1)\times (19(k+1)-1))$ grid $B$. Suppose that $A$ consists of all unit squares $u(i,j)$, where $1\le i\le 19k+18$, $1\le j\le 19k+18$ and $B$ consists of all unit squares $u(i,j)$, where $1\le i\le 19k+18$, $1\le j\le 19k+18$. Let $19\times 19$ squares $U_s$, $s=1,2,\dots ,k$; consist of all unit squares $u(i,j)$, where $19k\le i\le 19k+18$, $19s-18\le j\le 19s$ and $19\times 19$ squares $V_t$, $t=1,2,\dots ,k$; consist of all unit squares $u(i,j)$, where $19t-18\le i\le 19t$, $19k\le j\le 19k+18$. Note that the squares $U_k$ and $V_k$ share a unit square $u(19k-1,19k-1)$, all other pairs of $U_s$ and $V_t$ squares do not share any unit square. Therefore, since the union of $k$ $U_s$ and $k$ $V_t$ squares is a subset of the set $B-A$, the set $B-A$ contains at least $21\cdot 2k-1=42k-1$ marked squares. Thus, by inductive hypothesis $B$ contains at least $=(k-1)(21k-1)+42k-1=((k+1)-1)(21(k+1)-1)$. Done. Since $M(106)=233625$ the solution is completed.