A lattice point in the Cartesian plane is a point whose coordinates are both integers. A lattice polygon is a polygon all of whose vertices are lattice points. Let $\Gamma$ be a convex lattice polygon. Prove that $\Gamma$ is contained in a convex lattice polygon $\Omega$ such that the vertices of $\Gamma$ all lie on the boundary of $\Omega$, and exactly one vertex of $\Omega$ is not a vertex of $\Gamma$.
Problem
Source: Romanian Masters in Mathematics 2020, Problem 5
Tags: analytic geometry, combinatorics, RMM, RMM 2020
01.03.2020 14:11
Just one vertex of $\Omega$ is not a vertex of $\Gamma$? You mean only two edges are different? Seems right but really weird...
02.03.2020 03:57
Through some logistics, we can assume the top side is horizontal, right side is verticle, now we only focus on the top right of the sides. Let the ith side be traveling $x_i$ downwards and $y_i$ to the right.(I know, I messed up the coordinate system) Thus, by convexity, we have $0<\frac{x_1}{y_1}<\frac{x_2}{y_2}<...<\frac{x_n}{y_n}<\infty$. Now we do an induction: Suppose $1<y_1<y_2<...<y_i$ and for all $k \le i$, we have $x_iy_{i-1}-x_{i-1}y_i=1$ (Adjacent Farey Fractions) then the next side must still satisfy the conditions. Ok, this is not quite true, but note that if there exists a,b s.t. $\frac{x_{i-1}}{y_{i-1}}<\frac{a}{b}<\frac{x_i}{y_i}$ and $b<y_i$, then we can insert the side $a/b$ inbetween those 2 sides and everything will be fine. Thus, we will insert every such side that we can. Now by this assumption, our only restraints on the next side is $\frac{x_i}{y_i}<\frac{x_{i+1}}{y_{i+1}}<\frac{x_i-x_{i-1}}{y_i-y_{i-1}}$ and if we dont want an $a/b$ to exist, the next side msut also be an adjacent Farey Fraction. Also, obviously $y_{i+1}>y_i$ in this case. Thus, $y_i$ is always increasing which is bad/
03.03.2020 22:33
For every side of $\Gamma$ take a lattice point with the minimal nonzero distance to this side, and chose the minimal of all such distances. Let this side with minimal distance be $AB$. By reflecting about the midpoint of $AB$ and translating by the vector $AB$, if necessary, we may assume that the closest point $X$ lies outside $\Gamma$ and that its projection onto $AB$ lies between $A$ and $B$. We claim that $\Gamma \cup X$ works. Indeed, suppose that the vertex $C$ adjacent to $B$ and that $B$ lies inside $\triangle ACX$. Then $\text{dist}(X,BC)=BX\cos(180^\circ-\angle XBC)<BX\cos(\angle XBA)=\text{dist}(X,AB)$, which is a contradiction.
05.03.2020 08:27
The result is same as proof above, but I will post my proof with detailed intuitions. So if you only want the final result, please see mindstormer's proof right above.
06.03.2020 09:32
Let $\Gamma$ have vertices $A_1,A_2,\ldots,A_n$. Let $T_i$ denote the region bounded by the line $A_iA_{i+1}$ and the rays $\overrightarrow{A_{i-1}A_i}$ and $\overrightarrow{A_{i+1}A_{i+2}}$. Here we take the segment $A_iA_{i+1}$ to be open in $T_i$, but the rays to be closed. The problem is clearly equivalent to showing that some $T_i$ contains a lattice point. Firstly, note that if any $T_i$ is infinite, then it clearly contains a lattice point, so we may assume that all the $T_i$ are finite. To this end, define $B_i=A_{i-1}A_i\cap A_{i+1}A_{i+2}$, so $T_i$ is $\triangle A_iB_iA_{i+1}$. We now make the following very useful definition. Definition: For $q=a/b>0$ with $\gcd(a,b)=1$, define the weight of $q$ to be $w(q)=\max\{a,b\}$. We extend this definition to $\mathbb{Q}\cup\{\infty\}$ by $w(-q)=w(q)$ and $w(0)=w(\infty)=1$. Furthermore, for any line $\ell$, let $w(\ell)$ denote $w(m(\ell))$, where $m(\ell)\in\mathbb{Q}\cup\{\infty\}$ is the slope of $\ell$. This definition is useful because we have the following killer lemma. Claim: Suppose we have lattice points $X$ and $Y$ such that $XY$ is not axis-aligned, and suppose we have $P$ such that $\triangle PXY$ has no lattice points, except possibly on $XY$. Then, \[\max\{w(XP),w(YP)\}>w(XY).\] Let's first see how this claim finishes, and then we'll prove the claim. Pick side $A_iA_{i+1}$ with maximal weight, and pick it to not be axis aligned (note that axis aligned sides have weight $1$, so the only bad case is when $\Gamma$ is an axis-aligned rectangle, which is already covered since the regions $T_i$ are infinite). Apply the claim to $X=A_i$, $Y=A_{i+1}$, and $P=B_i$, which yields a contradiction to maximality of weight. It suffices now to prove the claim. Proof: [Proof of Claim] Without loss of generality, we may assume that $X=(0,0)$, $Y=(p,q)$ where $p,q>0$, and that $P$ is above $XY$. In fact, we may further assume that $\gcd(p,q)=1$ by restricting our attention to the sublattice of points with coordinates divisible by $\gcd(p,q)$. The key idea is to pick $m,n\ge 0$ such that $pn-qm=1$ and $m\le p$, $n\le q$ (this clearly exists by the Euclidean algorithm and some boring size argument). The point $Q=(m,n)$ is above $XY$, so the triangle $PXY$ does not contain it. This implies that either \[m(XP)\in(m(XY),m(XQ))\]or \[m(YP)\in(m(YQ),m(XY)).\]Without loss of generality, assume we are working in the first case - the second case is similar. It suffices then to prove the following intuitive lemma. Lemma: For positive integers $x$ and $y$, if we have \[\frac{q}{p}<\frac{y}{x}<\frac{n}{m}\]with $pn-qm=1$, then $\max\{x,y\}>\max\{p,q\}$. We present several proofs below. Proof: [Proof by Farey Sequences] The condition $pn-qm=1$ implies that $q/p$ and $n/m$ are adjacent in some Farey sequence. This means that $x/y$ appears in a later Farey sequence, which implies the claim. $\blacksquare$ Proof: [Proof by algebraic manipulation, by yayups and Luke Robitaille] Note that \[\frac{n}{m}-\frac{y}{x}<\frac{n}{m}-\frac{q}{p},\]so \[\frac{nx-my}{mx}<\frac{pn-qm}{mp}=\frac{1}{mp}.\]We also have $nx-my>0$ as $y/x<n/m$, so $nx-my\ge 1$. This implies \[\frac{1}{mp}>\frac{1}{mx},\]so $x>p$. By considering the inequality \[\frac{x}{y}-\frac{m}{n}<\frac{p}{q}-\frac{m}{n},\]we may prove $y>q$ in a similar fashion. This completes the proof. $\blacksquare$ Proof: [Proof by clever algebraic manipulation, by Luke Robitaille] We have \begin{align*} x&=x(pn-qm)\\ &=xpn-mpy+mpy-mqx\\ &=p(xn-my)+m(py-qx)\\ &\ge p+m \end{align*}and \begin{align*} y&=y(pn-qm)\\ &=ypn-nqx+nqx-yqm\\ &=n(yp-qx)+q(nx-ym)\\ &\ge n+q, \end{align*}so the lemma is proved. $\blacksquare$ Remark: Technically the proof of the claim does not work if one of $p$ or $q$ is $1$, since then one of $m$ or $n$ is $0$. However, this case is trivial to verify by hand, so there is no issue. $\blacksquare$ This completes the solution. Remark: [Story] I somewhat solved this problem in contest, with a solution that is similar to the one presented above. Unfortunately, I only got the idea in the last half hour or so, so I frantically wrote 25+ pages with all my ideas and proofs and such. I did not walk out with a complete solution, but with something I thought that could be coordinated to a high score. Big shout out to Luke Robitaille and Brandon Wang for spending their precious time and effort looking through my many badly written pages, and trying to sort them out to get a complete solution. In particular, Brandon helped with organizing my ideas into a coherent solution with a clear flow, and Luke helped with ironing out many technical details.
07.03.2020 06:14
Another proof!! [Case0] for the concrete local picture Denote $\Gamma$ as $P_1 P_2 ... P_n$. If there exists an $i$ such that $\angle P_{i-1} P_i P_{i+1}+\angle P_{i} P_{i+1} P_{i+2} \le \pi$. Let $X$ be the $P_i + \overrightarrow{P_{i-1} P_i}$. Then convex hull of $X \cup \Gamma$ satisfies the problem. Therefore, assume every $\overrightarrow{P_{i-1}P_i}, \overrightarrow{P_{i+2} P_{i+1}}$ and segment $P_i P_{i+1}$ form a triangle. [Case 1] Every segment has lattice points on it For each segment $P_i P_i+1$, let $d_i$ be the number of integer points on segment minus one. By assumption every $d_i$ is at least 2. Assume $P_i P_{i+1}$ is the segment of maximal length. Next, let $X_1, X_2$ be the points $P_i + \overrightarrow{P_{i-1} P_i} / d_{i-1}, P_{i+1} + \overrightarrow{P_{i+2} P_{i+1} }/ d_{i+1}$. If $X_1$ and $\Gamma$ are in the same side with respect to line $P_{i+1}P_{i+2}$, the convex hull of $X_1 \cup \Gamma$ satisfies the problem. Same for $X_2$. If both events do not take place, $P_{i} X_1 \cap P_{i+1}X_2=X_3$ must exist. Since $d_{\pm 1}>1$, contradiction came form triangle inequality for $P_i X_3 P_{i+1}$. [Case 2] There exists a segment $P_i P_{i+1}$ with no lattice points on it.
24.05.2020 13:00
Select a point \(P\) not on the perimeter of \(\Gamma\) and a side \(BC\) of \(\Gamma\) such that the distance from \(P\) to \(\overline{BC}\) is minimal over all choices of \(P\), \(B\), \(C\). Translating by the vector \(\vec{BC}\), we may assume the projection of \(P\) onto \(\overline{BC}\) lies on segment \(BC\), and by reflecting through the midpoint of \(\overline{BC}\), we may assume \(P\) lies outside of \(\Gamma\). [asy][asy] size(5cm); defaultpen(fontsize(10pt)); pair A,B,C,D,P,X,I,IX; A=(-1,0); B=(0,0); C=(1,1); D=(.3,2); P=(.8,.5); X=extension(A,B,C,D); I=incenter(X,B,C); IX=2*circumcenter(I,B,C)-I; fill(B--I--C--IX--cycle,cyan+white+white+white+white); draw(A--B--C--D); draw(B--X--C); draw(B--P--C,dashed); draw( (2B-I)--I--(2C-I),gray); draw(extension(B,IX,2B-I,2B-I+(1,0))--IX--(1.5C-.5IX),gray); dot("\(A\)",A,W); dot("\(B\)",B,dir(245)); dot("\(C\)",C,NE); dot("\(D\)",D,N); dot("\(P\)",P,W); dot("\(X\)",X,SE); dot("\(I\)",I,SE); dot("\(J\)",IX,NW); [/asy][/asy] Let \(A\) be the vertex on \(\Gamma\) adjacent to \(B\) and opposite \(C\), and let \(D\) be the vertex on \(\Gamma\) adjacent to \(C\) and opposite \(B\). Without loss of generality \(A\), \(B\), \(C\), \(D\) are oriented counterclockwise on \(\Gamma\). If \(X\) lies on the opposite side of line \(BC\) as \(P\), then there is a lattice point \(Q\) in the infinite set of points in the interior of \(\angle AXB\) and on the opposite side of \(\overline{AB}\) as \(X\). The polygon \(\Gamma\cup Q\) is clearly valid. $~$ Otherwise assume \(P\), \(X\) are on the same side of line \(BC\). Let \(I\), \(J\) be the incenter and \(X\)-excenter of \(\triangle XBC\). Since \(P\) is closer to \(\overline{BC}\) than \(\overline{AB}\), we know \(P\) is either in the interior of the angle \(\angle IBJ\) or its vertical angle. Similarly \(P\) is either in the interior of the angle \(\angle ICJ\) or its vertical angle. Combining these two conditions along with the constraint that \(P\) lies outside \(\Gamma\), we know \(P\) is in the interior of \(\triangle IBC\). Then \(\angle ABP\), \(\angle PCD\) are oriented counterclockwise, so \(\Gamma\cup P\) works. This completes the proof.
11.09.2020 07:11
Here is my solution. Unfortunately, I know which side to choose in the last 30 minutes of the mock, hence didn't have enough time to force algebra to work. Assign a weight to each side the number $\frac{|\Delta x| + |\Delta y|}{\gcd(\Delta x, \Delta y)}$, where $\Delta x$ and $\Delta y$ are the changes in the $x$ and $y$ coordinate of that side, respectively. The main claim is that we can create a lattice triangle on the side with maximum weight, while retaining convexity. Suppose that that side is $A=(0,0)$, and $B=(da,db)$ where $d,a,b$ are positive integers which $\gcd(a,b)=1$. WLOG, assume that the interior of $\Gamma$ is contained in the upper halfplane of $AB$. By Bezout identity, we can find integers $x,y$ such that $bx-ay=1$. Upon transforming $(x,y)\to (x\pm a, y\pm b)$, one can assume that $0\leq x+y < a+b$. If $x+y=0$, then $a+b=1$. Thus, all sides have the weight of $1$, or they are all parallel to either $x$ or $y$ axis. This means that $\Gamma$ must be a rectangle, which is easy to see that one can pick $\Omega$ that works (say by reflecting one vertex across another). Otherwise, $0<x+y<a+b$. We claim that selecting $P=(dx, dy)$ and $\Omega=\Gamma\cup P$ works. To see why, assume that $CA, BD$ are the sides of $\Gamma$ adjacent to $AB$. Assume that $(-p,-q)$ is the lattice point on $AC$ closest to $C$, and $(-r,-s)$ is the lattice point on $BD$ closest to $B$. Either $(p,q)$ lie in the interior of the angle $\angle PAB$ or $(r,s)$ lie in the interior of the angle $\angle PBA$. Case 1: $(p,q)$ lie in the angle $\angle PAB$. Then $(0,0)$, $(x,y)$, $(p,q)$ are in counterclockwise order. By Shoelace's formula, this means $qx-py\geq 1$. Similarly, $(0,0)$, $(p,q)$, $(a,b)$ are in clockwise order, thus $bp - aq\geq 1$. However, \begin{align*} x+y+a+b &\leq (x+y)(bp-aq) + (a+b)(qx-py) \\ &= (bpx + bpy - aqx -aqy) + (aqx + bqx - bpy - apy) \\ &= bpx - aqy + bqx - apy \\ &= (p+q)(bx-ay) = p+q\end{align*}Hence $p+q > a+b$, contradiction to maximality. Case 2: $(r,s)$ lie in the interior of the angle $\angle PBA$. We reflect the entire polygon across the midpoint of $AB$, then reflect the entire polygon across the line $y=x$. Clearly, the transformation maps lattice point to lattice point. Moreover, this will give the same configuration as in the Case 1, hence contradiction.
04.10.2023 20:56
Over all triples $(P, A, B)$ of lattice points where $AB$ is a side of $\Gamma$, let $S$ be the set of triples $(P, A, B)$ such that the distance from $P$ to $AB$ is minimal. Realize that no matter how much we translate $\Gamma$, the problem statement remains the same. Claim: There exists a translation of $\Gamma$ with the property that there is a triple $(P, A, B) \in S$ such that $P$ is outside $\Gamma$ and the projection of $P$ lies on segment $AB$. Proof. Note that if a point $P$ with minimal distance is inside $\Gamma$, consider $A+B-P$, which has the same distance from $\overline{AB}$, and otherwise consider $P$. If the projection of the resulting point $P'$ is not on segment $AB$, then it clear that we can take an appropriate translation of $\Gamma$ such that the projection of $P'$ onto $AB$ is on segment $AB$. Consider a triple $(X, A, B)$ as in the above claim. Claim: Appending $X$ to the vertex set of $\Gamma$ maintains convexity. Proof. WLOG suppose the intersection of the two sides adjacent to $AB$ when extended is on the same side of $\overline{AB}$ as $X$, or else we are done. Consider a side $BC$ with $C \neq A$ and $\angle ABC$ obtuse. Assume for contradiction that appending $X$ results in nonconvexity. Then it is clear that $d(X, AB)>d(X, BC)$, a contradiction, so we are done. Remark: Actually, this is a very tricky problem: the trick is to have wishful thinking in that you take the most extreme case possible. Additionally, the final claim was rather weak, so food for thought: can we look at an ideal stronger than convexity such that the problem remains true?
15.01.2024 11:08
Another fun extremal problem! Consider the set of points $(T,A,B)$ where $A,B$ are consecutive vertices in $\Gamma$ such that $d(T,AB)$ is minimized. ALso note that any translation does not effect the statement of problem. Firstly, we claim that there exists a translation so that $T$ lies outside and its projection on the segment $AB$, else if consider the "parallelogram point" it also has same distance and is outside. We claim that if we add $T$, the resulting polygon will also be convex; indeed assume not then $d(T,AB) \geq d(T,BC)$ for consecutive $C$ yielding a contradiction as desired. $\blacksquare$