Japan Mathematical Olympiad

Let us call a good point on $x = 1$ or $x = 2000$ excluding $(1, 1)$ a special point. Consider Z-shaped polyline $ABCD$ and let $A(x_1, y_1)$, $B(x_2, y_2)$, $C(x_3, y_3)$, $D(x_4, y_4)$. Since $1 \le x_1 < x_2 \le 2000$, $1 \le x_3 < x_2 \le 2000$ and $1 \le x_3 < x_4 \le 2000$, any special point on Z-shaped polyline $ABCD$ coincides with either $A$, $B$, $C$ or $D$. Assume that both $B$ and $C$ are special points. Then $x_2 = 2000$, $y_2 \le 2000$, $x_3 = 1$ and $y_3 \ge 2$ holds. Therefore we have $y_2 - x_2 \le 2000 - 2000 < 2 - 1 \le y_3 - x_3$, which contradicts the condition $y_2 - x_2 = y_3 - x_3$. Therefore at most three special points lie on a Z-shaped polylines, hence we must select at least $\frac{3999}{3} = 1333$ Z-shaped polylines to meet the condition.

Denote polyline $ABCD$ with $A(x_1, y_1)$, $B(x_2, y_2)$, $C(x_3, y_3)$, $D(x_4, y_4)$ by $(x_1, y_1) - (x_2, y_2) - (x_3, y_3) - (x_4, y_4)$. Define Z-shaped polylines $X_1, X_2, \dots, X_{666}$, $Y_1, Y_2, \dots, Y_{666}$, $Z$ as following:
* For $k = 1, \dots, 666$, let $X_k$ be $(1, 1334-k) - (1334-2k, 1334-k) - (1, 1+k) - (2000, 1+k)$.
* For $k = 1, \dots, 666$, let $Y_k$ be $(1, 2000-k) - (2000, 2000-k) - (667+2k, 667+k) - (2000, 667+k)$.
* Let $Z$ be $(1, 2000) - (2000, 2000) - (1, 1) - (2000, 1)$.

Note that any good point on $y = 1, 2000$ lies on $Z$. For $2 \le k \le 667$, any good point on $y = k$ lies on $X_{k-1}$. For $1334 \le k \le 1999$, any good point on $y = k$ lies on $Y_{2000-k}$. Let $668 \le k \le 1333$ and consider good points on $y = k$.
* When $1 \le x < 2k - 1333$, $(x, k)$ lies on $X_{1334-k}$.
* When $2k - 1333 \le x < k$, $(x, k)$ lies on $X_{k-x}$.

* When $x = k$, $(x, k)$ lies on $Z$.
* When $k < x \le 2k - 668$, $(x, k)$ lies on $Y_{x-k}$.
* When $2k - 668 < x \le 2000$, $(x, k)$ lies on $Y_{k-667}$.

We have shown that any good point lies on any of $X_1, X_2, \dots, X_{666}$, $Y_1, Y_2, \dots, Y_{666}$ and $Z$.
Therefore the smallest possible number of Z-shaped polylines is $1333$.