Maths Olympiad Prep

Library / /26 of 28

Geometry Difficulty 8.9 Shortlist Prove it China

In a plane with cartesian coordinates, let PP and QQ be two regions of convex polygon (including boundary and interior) whose vertices are all integer points (i.e., their coordinates are all integers) and T=PQT = P \cap Q. Prove that if TT is not empty and does not contain integer point, then TT is a non-degenerate convex quadrilateral. (posed by Qu Zhenhua)

Solution

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

(1) TT is a point. Then TT must be the vertex of PP or QQ, contradicting the fact that TT contains no integer point.

(2) TT is a segment. Then TT must be the intersection of an edge of PP and an edge of QQ, which contains the vertex of PP or QQ, which is a contradiction.

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

Case 1. If k=0k=0, then PP is an element integer triangle, or a parallelogram with area 1. So, PP can be located between two parallel lines l1,l2l_1, l_2. And there is no integer point in the open domain Ω\Omega between l1l_1 and l2l_2. At least three edges of PP are the edges of TT, because TT has at least six edges.
(a) In case of PP being ABC\triangle ABC (See Fig. 6.1), DEDE, FGFG and HIHI are edges of QQ. D,GD, G and EE may coincide with F,HF, H and II, respectively. Lines FGFG, HIHI, l1l_1 and l2l_2 form a convex quadrilateral. Since line DEDE does not intersect segment BCBC, we see that the intersect point of line DEDE and FGFG or of line DEDE and HIHI is in Ω\Omega. Thus, QQ has integer vertex in Ω\Omega, a contradiction.
Figure 1

(b) In case of PP being a parallelogram ABCD\square ABCD. Let ADAD, ABAB and BCBC be three edges of PP (see Fig. 6.2). The intersection point of line EFEF and HGHG locates in Ω\Omega. Let ABAB, BCBC and CDCD be three edges of PP (see Fig. 6.3), and there is no edge of QQ on ADAD. Similar to the case of (a), we can see the intersection point of line EFEF and HGHG or of line EFEF and IJIJ locates in Ω\Omega, which is a contradiction.
Figure 2
Figure 3

Case 2. k1k \ge 1. Consider integer point XX on PP other than the vertices. Since XTX \notin T, there exists an edge MNMN of TT such that TT and XX are separated by line MNMN (denote by ll) (see Fig. 6.4). Thus, MNMN is a part of boundary of QQ. MM is on the edge ABAB of PP, NN is on the edge CDCD of PP. AA, CC and XX are on the same side of ll (AA and CC may coincide, but BB and DD do not by the hypothesis that TT has at least six edges). Thus, there is another vertex UU of TT on ABAB, and there is another vertex VV of TT on CDCD.
Figure 4

Denote the convex hull of points XX and vertices of PP below ll by PP'. Then PP' and PP coincide below BDBD, and the part of PP' up BDBD is BXD\triangle BXD. Comparing T=PQT' = P' \cap Q with TT, we see that TTT' \subset T, and the boundary of TT' is the boundary of TT with MNMN, MUMU and NVNV replaced by MNM'N', MUM'U' and NVN'V', respectively. That is, TT' and TT have the same number of edges, and the number of integer points of PP' other than vertices is less than that of PP. By a finite procedure like this, we can obtain a convex polygon with no interior integer point. By Case 1, it is impossible. ☐

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.