A point $(x,y)$ is a lattice point if $x,y\in\Bbb Z$. Let $E=\{(x,y):x,y\in\Bbb Z\}$. In the coordinate plane, $P$ and $Q$ are both sets of points in and on the boundary of a convex polygon with vertices on lattice points. Let $T=P\cap Q$. Prove that if $T\ne\emptyset$ and $T\cap E=\emptyset$, then $T$ is a non-degenerate convex quadrilateral region.
Problem
Source: 25 Mar 2013
Tags: analytic geometry, geometry, combinatorics proposed, combinatorics
04.04.2013 12:11
If I'm not wrong, this question can be done quite nicely, and although difficult to approach (characteristic of China combinatorial problems), turns out to be quite okay. - Going along the boundary of $T$, we see that we have to alternate between sides of P and Q, otherwise we will have a vertex of $P$ or $Q$ in $T$, thus attaining a contradiction. Thus let $T$ have $2k$ sides. - If $k=2$, we are done, as the intersection of 2 convex sets must be convex, thus $T$ is a convex quadrilateral (and of course non-degenerate). - So suppose $k\geq 2$. Assuming there exists a configuration that satisfies the question, then there must be one where $[P]+[Q]$ is minimal. (Square brackets denote area). - Let the polygon which defines $P$ be $P_1P_2...P_m$ and let the polygon which defines $Q$ be $Q_1Q_2...Q_n$. - If $P_iP_{i+1}$ does not intersect $Q$ at all, we may throw away either one of $P_i$ or $P_{i+1}$ to achieve a smaller $[P]$. Thus we may shrink $m$ and $n$ both to $k$ - Now assume that the labelling is such that $P_1P_2$ intersects $Q_kQ_1$ and $Q_1Q_2$ and so on. Consider the triangle bounded by lines $P_1P_2,Q_kQ_1,Q_1Q_2$. If there exists a lattice point in this triangle (or on the boundary, except the vertices), we can shift $Q_1$ there to attain a smaller $[Q]$. -Thus due to the initial minimality assumptions, there must be no lattice points on the interior of $P$ and $Q$. By Pick's theorem: \[[P]=\frac{k}{2}-1,[Q]=\frac{k}{2}-1\] -However, also due the Pick's theorem, we know that if a triangle has its vertices on lattice points, then its area is at least $\frac{1}{2}$. Thus equality always holds. -Now we go back to the abovementioned triangle. We know that $Q_1$ has the minimal distance of all points in $E$ from line $Q_kQ_2$, since $[Q_kQ_1Q_2]=\frac{1}{2}$, which means that $P_1,P_2$ are both at least that distance away from line $Q_kQ_2$. However, we realise that segment $P_1P_2$ has to intersect both segments $Q_kQ_1,Q_1Q_2$. This is not possible, so contradiction.
11.04.2015 23:52
is immediate consequence of following wellknown lemma: in convex lattice pentagon P let P* be the pentagon formed by the diagonals. Then there is lattice point in P* To prove lemma assume contradiction, take the smallest-area P=ABCDE that works. If P has no lattice points then by Pick theorem, ABC, ABD, ABE have area 1/2 so its not convex. Then P has a lattice point and is easy to see it must be outside 5-vertex star formed by P. Now if ACQ is triangle of smallest area formed by a diagonal and a point that is inside the triangle formed by the diagonal, then is easy to see P=BQEDC also satisfies the conditions and has area less than original P. So done.