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$.