Problem 1852

The answer is $1343$. We denote the lowest leftmost, the highest leftmost, the highest rightmost and the lowest rightmost unit squares by $A$, $B$, $C$, $D$, respectively. Example: Let us $672$ green crawlers to $A$ and $671$ brown crawlers to $B$. One green crawler from $A$ makes $2013$ up moves and after that makes $2013$ right moves and visits all unit squares of the leftmost column and the highest row. All green crawlers start by making one up and one right move, all brown crawlers start by making one down and one right move. Thus, it is sufficient to give an example when $671$ green and $671$ brown crawlers visit all unit squares of $2013 \times 2013$ grid. Let us label crawlers by $g_1, \dots, g_{671}$ and $b_1, \dots, b_{671}$. Each $g_i$, $i = 1, \dots, 671$ makes $i-1$ right moves, after that $2 \cdot 671 - i$ up moves, after that $2 \cdot 671$ right moves and finally $671 + i - 1$ up moves. Each $b_i$, $i = 1, \dots, 671$ makes $i-1$ down moves, after that $2 \cdot 671 - i$ right moves, after that $2 \cdot 671$ down moves and finally $671 + i - 1$ right moves. It can be readily seen that all unit squares are visited at least once by some crawler.

Now we show that the total number of crawlers is at least $\frac{2n}{3}$ for a grid $n \times n$. Suppose that there are $a$ green and $b$ brown crawlers. Let us define diagonals $T_1, T_2, \dots, T_n$ that are parallel to the main diagonal connecting $B$ and $D$ so that $T_1$ consists of only one unit square $A$, $T_2$ consists of two unit squares neighboring $A$, ..., $T_n$ consists of $n$ unit squares of the main diagonal $BD$, $\dots$, $T_{2n-1}$ consists of only one unit square $C$. Similarly let us define diagonals $S_1, S_2, \dots, S_n$ that are parallel to the main diagonal connecting $A$ and $C$ so that $S_1$ consists of only one unit square $B$, $S_2$ consists of two unit squares neighboring $B$, ..., $S_n$ consists of $n$ unit squares of the main diagonal $AC$, $\dots$, $S_{2n-1}$ consists of only one unit square $D$. Obviously we can assume that each green crawler ends its trip at $C$ and each brown crawler ends its trip at $D$. Each $g_i$ will visit exactly one unit square of each diagonal $T_i$. Then green crawlers will visit $1$ square in $T_1$, at most $2$ squares in $T_2$, ..., at most $a-1$ squares in $T_{a-1}$, at most $a$ squares in each of the diagonals $T_a, T_{a+1}, \dots, T_{2n-a-1}, T_{2n-a}$, at most $a-1$ squares in $T_{2n-a+1}, \dots$, at most $2$ squares in $T_{2n-2}$, $1$ square in $T_{2n-1}$. Then green squares had visited at most $1+2+\dots+(a-1)+a(2n-1-2(a-1))+(a-1)+\dots+2+1=2an-a^2$. Similarly, $b$ brown crawlers also had visited at most $2bn-b^2$ unit squares. The trajectories of two distinctly colored crawlers will intersect in exactly one square. Therefore, the crawlers in total will visit at most $2an-a^2+2bn-b^2-ab$ squares which should be not less than $n^2$: $n(2a+2b) \ge n^2+(a^2+ab+b^2) \ge n^2+\frac{3}{4}(a+b)^2$. Put $a+b=x$: $2nx \ge n^2+\frac{3}{4}x^2$ or $(3x-2n)(2n-x) \ge 0$. Readily $x \le 2n$ since $n$ green or and $n$ brown crawlers can easily visit all squares. Finally we get $a+b \ge \frac{2n}{3}$. Thus, $a+b \ge 1343$. Done.