The answer is 233625.
Suppose that the centers of unit squares have coordinates (i,j), where i=1,2,…,2013; j=1,2,…,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≤k≤105, 0≤l≤105 and
u(m,19n), where 1≤m≤2013, 1≤n≤105.
Then it can be readily seen that the total number of marked unit squares is 233625, and any sub-square 19×19 has exactly 21 marked unit squares.
Let k≥2 be a positive integer. Now by the method of mathematical induction we show that if any 19×19 sub-square of the grid (19k−1)×(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×19 squares: the square consisting all u(k,l), where 1≤k≤19, 1≤l≤19 and the square consisting all u(k,l), where 19≤k≤37, 19≤l≤37. Each of these 19×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)×(19k−1)) grid A and consider a ((19(k+1)−1)×(19(k+1)−1)) grid B. Suppose that A consists of all unit squares u(i,j), where 1≤i≤19k+18, 1≤j≤19k+18 and B consists of all unit squares u(i,j), where 1≤i≤19k+18, 1≤j≤19k+18.
Let 19×19 squares Us, s=1,2,…,k; consist of all unit squares u(i,j), where 19k≤i≤19k+18, 19s−18≤j≤19s and 19×19 squares Vt, t=1,2,…,k; consist of all unit squares u(i,j), where 19t−18≤i≤19t, 19k≤j≤19k+18. Note that the squares Uk and Vk share a unit square u(19k−1,19k−1), all other pairs of Us and Vt squares do not share any unit square. Therefore, since the union of k Us and k Vt squares is a subset of the set B−A, the set B−A contains at least 21⋅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.