Problem 1973

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. \qquad \textcircled{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 = \emptyset$, 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 \neq 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{aligned} V_k &= (2k-2)(2k-1)\vec{j} + (2k-t)(-(2k-1)\vec{i} + t\vec{j}) + \\ &\quad 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{aligned}$$
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{aligned} \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{aligned}$$
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|. \qquad \textcircled{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}$