China National Team Selection Test

Since the non-empty intersection $T$ of two convex closed polygons is a closed convex polygon or degenerated polygon, there are three possible cases.

(1) $T$ is a point. Then $T$ must be the vertex of $P$ or $Q$, contradicting the fact that $T$ contains no integer point.

(2) $T$ is a segment. Then $T$ must be the intersection of an edge of $P$ and an edge of $Q$, which contains the vertex of $P$ or $Q$, which is a contradiction.

(3) $T$ is a closed convex polygon. So, it remains to be shown that $T$ is a quadrilateral. First, we note that if $T$ has two adjacent edges on the edges of $P$ (or $Q$), then the common vertex of these two edges must be the vertex of $P$ (or $Q$), which is a contradiction. Thus, the boundary of $T$ is formed alternately by a part of an edge of $P$ and then a part of an edge of $Q$, and each vertex of $T$ is the intersect point of edges of $P$ and $Q$. Thus, the number of edges of $T$ is even. We see that if an edge $e$ of $P$ intersects an edge $f$ of $Q$, then $e$ must intersect another edge of $Q$, otherwise $T$ will contain an integer point. In the following, we show by contradiction that the number of edges of $T$ can be 6 or more. If $T$ has edges no less than 6, then suppose $P$ contains $k$ integer points except the vertices of $P$.

Case 1. If $k=0$, then $P$ is an element integer triangle, or a parallelogram with area 1. So, $P$ can be located between two parallel lines $l_1,l_2$. And there is no integer point in the open domain $\Omega$ between $l_1$ and $l_2$. At least three edges of $P$ are the edges of $T$, because $T$ has at least six edges. (a) In case of $P$ being $△ABC$ (See Fig. 6.1), $DE$, $FG$ and $HI$ are edges of $Q$. $D,G$ and $E$ may coincide with $F,H$ and $I$, respectively. Lines $FG$, $HI$, $l_1$ and $l_2$ form a convex quadrilateral. Since line $DE$ does not intersect segment $BC$, we see that the intersect point of line $DE$ and $FG$ or of line $DE$ and $HI$ is in $\Omega$. Thus, $Q$ has integer vertex in $\Omega$, a contradiction.

(b) In case of $P$ being a parallelogram $\square ABCD$. Let $AD$, $AB$ and $BC$ be three edges of $P$ (see Fig. 6.2). The intersection point of line $EF$ and $HG$ locates in $\Omega$. Let $AB$, $BC$ and $CD$ be three edges of $P$ (see Fig. 6.3), and there is no edge of $Q$ on $AD$. Similar to the case of (a), we can see the intersection point of line $EF$ and $HG$ or of line $EF$ and $IJ$ locates in $\Omega$, which is a contradiction.

Case 2. $k\ge 1$. Consider integer point $X$ on $P$ other than the vertices. Since $X\notin T$, there exists an edge $MN$ of $T$ such that $T$ and $X$ are separated by line $MN$ (denote by $l$) (see Fig. 6.4). Thus, $MN$ is a part of boundary of $Q$. $M$ is on the edge $AB$ of $P$, $N$ is on the edge $CD$ of $P$. $A$, $C$ and $X$ are on the same side of $l$ ($A$ and $C$ may coincide, but $B$ and $D$ do not by the hypothesis that $T$ has at least six edges). Thus, there is another vertex $U$ of $T$ on $AB$, and there is another vertex $V$ of $T$ on $CD$.

Denote the convex hull of points $X$ and vertices of $P$ below $l$ by $P^{\prime }$. Then $P^{\prime }$ and $P$ coincide below $BD$, and the part of $P^{\prime }$ up $BD$ is $△BXD$. Comparing $T^{\prime }=P^{\prime }\cap Q$ with $T$, we see that $T^{\prime }\subset T$, and the boundary of $T^{\prime }$ is the boundary of $T$ with $MN$, $MU$ and $NV$ replaced by $M^{\prime }{N}^{\prime }$, $M^{\prime }{U}^{\prime }$ and $N^{\prime }{V}^{\prime }$, respectively. That is, $T^{\prime }$ and $T$ have the same number of edges, and the number of integer points of $P^{\prime }$ other than vertices is less than that of $P$. By a finite procedure like this, we can obtain a convex polygon with no interior integer point. By Case 1, it is impossible. ☐