China National Team Selection Test

We see that by the condition of the problem, an expansion of an interesting sequence is still interesting.

First, we construct the interesting sequence $(C_0, C_1, \dots, C_k)$ containing all points of sequences $(A_0, A_1, \dots, A_n)$ and $(B_0, B_1, \dots, B_m)$, and $C_0 = A_0 = B_0$, $C_k = A_n = B_m$.

By the Pick Theorem, we know that the area of triangle equals $1/2$ if and only if there is no grid point on the triangle except triangle vertices. Hence there is no grid point on $\triangle OA_iA_{i+1}$ except its vertices. Therefore, if the slopes of $OA_i$ and $OB_j$ are equal, then $A_i = B_j$.

Denote the slopes of segments from points of $\{A_i\}$ and $\{B_j\}$ to the origin in strictly increasing order by $D_0, D_1, \dots, D_l$, where $D_0 = C_0 = A_0 = B_0$ and $D_l = C_k = A_n = B_m$. If a sequence ($D_i, D_{i+1}$) is not interesting, then we can insert several points $E_1, \dots, E_s$ such that the sequence ($D_i, E_1, \dots, E_s, D_{i+1}$) is interesting. In fact, consider the convex hull $P$ of the grid points on $\triangle OD_iD_{i+1}$, except the origin. $P$ is a convex polygon or segment $D_iD_{i+1}$ (a degenerated polygon). Then the sequence of vertices of $P$ is interesting. Thus, we have constructed the interesting sequence $(C_0, C_1, \dots, C_k)$.

Finally, it suffices to show that the interesting sequence $(A_0, A_1, \dots, A_n)$ can be expanded to $(C_0, C_1, \dots, C_k)$, and the same is true for $(B_0, B_1, \dots, B_m)$. We only need to prove this for the case of $n=1$, since we can apply the conclusion for $n=1$ to $(A_i, A_{i+1})$, $i=0, 1, \dots, n-1$ successively. Let $C_0 = A_0$ and $C_k = A_1$. By induction on $k$, for $k=1$, we need no expansion. Suppose that the conclusion is true for all positive integers less than $k$.

Then denote the grid point $A$ satisfying $\overrightarrow{OA} = \overrightarrow{OA_0} + \overrightarrow{OA_1}$, and we see that $A$ must be a point of $C_1, \dots, C_{k-1}$. Since if not, there is no grid point on interior of segment $OA$, and there exists $i, 0 \le i < k$, such that $A$ locates in the angle made by rays $OC_i$ and $OC_{i+1}$. We may suppose that $i > 0$, otherwise take the graph symmetric over the line $x = y$. Since the area of the parallelogram $\square OA_0AA_1$ is $1$, $C_i$ locates outside of $\square OA_0AA_1$, $C_{i+1}$ locates outside of $\square OA_0AA_1$ or $C_{i+1} = A_1$. In any way, we take $B$ such that $\vec{OB} = \vec{OC}_i + \vec{OC}_{i+1}$ and take $B'$ such that $C_{i+1}B' \parallel OA_0$, $C_iB' \parallel A_0A$, then $A$ locates on $\square OC_{i+1}B'C_i$. Thus, $A$ locates inside of $\square OC_iBC_{i+1}$, which contradicts the fact that the area of $\square OC_iBC_{i+1}$ is $1$. Therefore the inserted point $A$ to $(A_0, A_1)$ for expansion is some $C_i$. Then we use the induction hypotheses to $(A_0, A)$ and $(A, A_1)$, respectively. $\square$