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 $△O{A}_i{A}_{i+1}$ except its vertices. Therefore, if the slopes of $O{A}_i$ and $O{B}_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 $△O{D}_i{D}_{i+1}$, except the origin. $P$ is a convex polygon or segment $D_i{D}_{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{O{A}_0}+\overrightarrow{O{A}_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 $O{C}_i$ and $O{C}_{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 O{A}_{0}A{A}_1$ is $1$, $C_i$ locates outside of $\square O{A}_{0}A{A}_1$, $C_{i+1}$ locates outside of $\square O{A}_{0}A{A}_1$ or $C_{i+1}=A_1$. In any way, we take $B$ such that $\overrightarrow{OB}={\overrightarrow{OC}}_i+{\overrightarrow{OC}}_{i+1}$ and take $B^{\prime }$ such that $C_{i+1}{B}^{\prime }\parallel O{A}_0$, $C_i{B}^{\prime }\parallel A_{0}A$, then $A$ locates on $\square O{C}_{i+1}{B}^{\prime }{C}_i$. Thus, $A$ locates inside of $\square O{C}_{i}B{C}_{i+1}$, which contradicts the fact that the area of $\square O{C}_{i}B{C}_{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$