China National Team Selection Test

Set up a coordinate system with origin at the center of chessboard $O$ and the grid line as the coordinate line. Denote the set of the centers of squares by $S$, and the set where the beetles initially stand on by $M_1\subseteq S$, and the set that the beetles land on by $M_2\subseteq S$. Let $f:M_1\to M_2$ be the one-to-one mapping defined by a beetle's position $v$ at the beginning to the position $u=f(v)$ of first landing. Thus, the total displacement vector is given by $$V=\sum _{v\in M_1}(f(v)-v)=\sum _{u\in M_2}u-\sum _{v\in M_1}v.\stackrel{◯}{1}$$ Note that the right-hand side of ① is independent of $f$. We need only to find the maximum of $|V|=|{\sum }_{u\in M_2}u-{\sum }_{v\in M_1}v|$ for all $M_1,M_2\subseteq S$, $|M_1|=|M_2|$. We may suppose that $M_1\cap M_2=\varnothing$, since element of $M_1\cap M_2$ does not change $|V|$. Suppose that $|V|$ attains its maximum at $(M_1,M_2)$, obviously $V\ne 0$. Let line $l\perp V$ be at point $O$.

Lemma 1. Line $l$ does not pass any point of $S$. $M_1$ is the set of $S$ on one side of $l$, and $M_2$ is the set of $S$ on the other side of $l$.

Proof of Lemma 1. First, $M_1\cup M_2=S$. Otherwise, since $|S|$ is even, there are at least two points $a$ and $b$ which are not in $M_1\cup M_2$. Suppose that the angle between $a-b$ and $V$ does not exceed $90^{\circ }$, then $|V+(a-b)|>|V|$. So add $a$ into $M_2$, add $b$ into $M_1$, then $|V|$ will increase, which is a contradiction.

Second, $M_2=-M_1$. Otherwise, there exist $a,b\in S$, such that $a,-a\in M_1$ and $b,-b\in M_2$. Suppose that the angle between $a-b$ and $V$ does not exceed $90^{\circ }$. Put $a$ into $M_2$, and $b$ into $M_1$, $V$ changes to $V+2(a-b)$, and $|V+2(a-b)|>|V|$, which is a contradiction.

Third, $l$ does not pass any point of $S$. Otherwise, let $l$ pass $a,a\in M_1,-a\in M_2$, then change $a$ into $M_2,-a$ into $M_1$, $V$ changes to $V+4a$. Notice that $a\perp V$, so $|V+4a|>|V|$, which is a contradiction.

Fourth, we show that $M_2$ is the set of $S$ on one side of $l$ (the side that $V$ is pointing to), and $M_1$ is the set of $S$ on the other side of $l$. Otherwise, there is $a\in M_1$ at the side that $V$ is pointing to. And there is a $b\in M_2$ on the other side. Then the angle between $a-b$ and $V$ is less than $90^{\circ }$. Change $a$ into $M_2$ and $b$ into $M_1$, then $V$ changes into $V+2(a-b)$, the length of which is greater, which is a contradiction. Lemma 1 is now proved.

Lemma 2. Let $S_k=\{(x,y)\in S\mid |x|=k-\frac{1}{2}\text{ or }|y|=k-\frac{1}{2}\},k=1,2,\dots ,1006,l$ be a line passing $O$ and does not pass points of $S_k$. Denote all points of $S_k$ on one side of $l$ by $A_k$, all points of $S_k$ on the other side by $B_k$. Denote $V_k={\sum }_{u\in A_k}u-{\sum }_{v\in B_k}v$, then the maximum of $|V_k|$ is obtained when $l$ is horizontal (or vertical), and $V_k$ is vertical (or horizontal).

Proof of Lemma 2. $S_k$ is located at the boundary of a square with $2k$ points on each side. Let the four vertices of the square be $A(k-\frac{1}{2},k-\frac{1}{2})$, $B(-k+\frac{1}{2},k-\frac{1}{2})$, $C(-k+\frac{1}{2},-k+\frac{1}{2})$ and $D(k-\frac{1}{2},-k+\frac{1}{2})$. By Fig. 6.1 symmetricity, we may suppose that $l$ intersects $AD$ at point $P$ with non-negative slope. Let $P$ be located between the $t$ ($1\le t\le k$)th (from top to bottom) of $S_k$ on $AD$ and the $(t+1)$th of $S_k$ on $AD$ (see Fig. 6.1, in case of $k=6,t=3$). Thus, $$\begin{array}{rl}{V}_k& =(2k-2)(2k-1)\vec{j}+(2k-t)(-(2k-1)\vec{i}+t\vec{j})+\\ & t((2k-1)\vec{i}+(2k-t)\vec{j})\\ & =-2(2k-1)(k-t)\vec{i}+2(-(k-t{)}^2+3k^2-3k+1)\vec{j},\end{array}$$ where $\vec{i}$ and $\vec{j}$ are horizontal and vertical unit vectors, respectively. Denote $(k-t{)}^2=u$, $0\le u\le (k-1{)}^2$, then $$\begin{array}{rl}\frac{1}{4}|V_k{|}^2& =(2k-1{)}^{2}u+u^2-2(3k^2-3k+1)u+(3k^2-3k+1{)}^2\\ & =u^2-(2k^2-2k+1)u+(3k^2-3k+1{)}^2.\end{array}$$ As a quadratic function of $u$, $u=k^2-k+\frac{1}{2}$ is the symmetric axis. It is easy to know that $|V_k{|}^2$ takes its maximum at $u=0$. So $t=k$, that is, $l$ is horizontal, so $V_k$ is vertical. Lemma 2 is proved.

Turn to the original problem. By symmetricity, we need to only consider that the slope of $l$ is non-negative and less than 1. Let $M_1,M_2$ be located on two sides of $l$. Denote $M_2\cap S_k=A_k,M_1\cap S_k=B_k,V_k={\sum }_{u\in A_k}u-{\sum }_{v\in B_k}v$, then $$|V|=\left|\sum _{k=1}^{1006}{V}_k\right|\le \sum _{k=1}^{1006}|V_k|.\stackrel{◯}{2}$$ So, $|V{|}_{\max }\le {\sum }_{k=1}^{1006}|V_k{|}_{\max }$. If $l$ is horizontal, $M_2$ is all the points of $S$ on the upper half-plane, $M_1$ is all points of $S$ on the lower half-plane; each $|V_k|$ takes its maximum, and all $V_k$ point upward. And the equality of ② holds. So $|V|$ indeed takes the maximum $|V{|}_{\max }=2\times 1006^3$.

$\boxed{2\times 1006^3}$