Turkey TST 2014 Day 3 Problem 9 Worms that are allowed to move one way Turkey TST 2014 Day 3 Problem 9( I've read the official answer, and I find the official answer incorrect） 

At the bottom-left corner of a $2014\times 2014$ chessboard, there are some green worms and at the top-left corner of the same chessboard, there are some brown worms. Green worms can move only to right and up, and brown worms can move only to right and down. After a while, the worms make some moves and all of the unit squares of the chessboard become occupied at least once throughout this process. Find the minimum total number of the worms.

There in AOPS Some of these discussions, however, are just as problematic as the official answers：I found this somewrong:

In the final calculation of the green and Brown crawler through the grid, according to the inclusive-exclusive principle to subtract duplicate. The answer is that the repeated squares do not overlap by default when calculating repetitions. For example, the Green Reptilian AB has crossed C, and the Brown Reptilian D has crossed C, twice, in the manner of the answer, but actually it should have been once

The following is an official translation of the Chinese version

 A: The key to understanding why it takes less than $n$ worms to cover an nxn area is considering the case $n=3$.
let's display the best 3x3 solution by denoting each worm a number and labelling each cell with the worm(s) that visited it:
$$
    \begin{matrix}
    1 &  &  \\
    1 & 1 & 1 \\
     &  & 1 \\
    \end{matrix}
$$
$$
    \begin{matrix}
    1 & 2 & 2 \\
    1 & 12 & 1 \\
    2 & 2 & 1 \\
    \end{matrix}
$$
Let's try to make sense of what conclusions we can draw from the above and in general:


*

*We want to minimise the overlap of worms (or numbers in each matrix cell) both for same-color worms but also for different-color worms.

*We want each worm to visit as many cells as possible, and for as many of these as possible to be unvisited.

*Worm $i$ can visit $2n-i$ cells in the optimal solution, since it visits $2n-1$ cells and must cross the path of at least $i-1$ worms. (as a sidenote, clearly the chinese textbook uses this fact to sum the overlapped squares in its proof - and then factorises n^2 ).
Clearly overlap is unavoidable in the two right corners, and must occur between the green and brown worms, but should never do so between same-coloured worms outside of corners. The 9x9 solution illustrates this:
$$
    \begin{matrix}
    123 & 23 & 3 & 4 & 4 & 4 & 4 & 4 & 456 \\
    1 & 2 & 3 & 4 & 5 & 5 & 5 & 5 & 56 \\
    1 & 2 & 3 & 4 & 5 & 6 & 6 & 6 & 6 \\
    1 & 2 & 3 & 34 & 35 & 36 & 3 & 3 & 3 \\
    1 & 2 & 2 & 24 & 25 & 26 & 2 & 2 & 3 \\
    1 & 1 & 1 & 14 & 15 & 16 & 1 & 2 & 3 \\
    4 & 4 & 4 & 4 & 5 & 6 & 1 & 2 & 3 \\
    45 & 5 & 5 & 5 & 5 & 6 & 1 & 2 & 3 \\
    456 & 6 & 6 & 6 & 6 & 6 & 1 & 12 & 123 \\
    \end{matrix}
$$
A pattern that extends from this center-overlap strategy is that the central n/3-2n/3 squares only need require 2 numbers. i.e. The only need be brown-green worm overlaps. That is, $n^2/9$ squares will have 2 worms go through them. Noting that n/3 worms can certainly cover each other section as shown, we can conclude that we need 2*n/3 worms altogether.
In the case where n mod 3 is not 1, 1 extra worm can trace the outside to reduce the problem to a mod 3 = 0 case. If n mod 3 is 2, then we simply solve the board for the next integer case and have overlap in n/3 squares. That is, for instance n=11 and n=12 would have the same number of worms required (8).
for 2014, the remainder is 1 and the first worm reduces the board to a 2013x2013 board as described, which is then traversed by 2 sets of 2013/3 worms - or 671 worms. In total that is 671*2+1 which is 1343. 
A full proof to this problem would probably require discussing the analogy of perpendicular sets of parallel lines to the different-coloured worms. Clearly, each line must cross all of the perpendicular ones(here, each green worm must cross paths with each brown worm). Then discussing how (and why) if only one corner was originally occupied, it must take $n$ worms to traverse it with the same rules. This is important to justify how the two right corners (top and bottom third - so $n/3$ squares) can be traversed by $n/3$ worms. Justifying how n/3 worms can continue across to another n/3 set of squares on the centers of the board is a direct extension of this.
Alternatively, as is done in the textbook, a proof to show why 2n/3 is the best possible outcome via factorising and then demonstrating how 2n/3 can be achieved may be enough for Olympiad marking.
