Romanian Master of Mathematics

Let $T$ be the extra vertex of a desired polygon $\Delta$; then $\Delta$ is the convex hull of $T$ and $\Gamma$. Thus, a point $T$ fits the bill if and only if this convex hull contains no vertices of $\Gamma$ in its interior.

Each segment $AB$ joining two lattice points is partitioned by lattice points into congruent elementary segments. Define the elementary length $\ell (AB)$ of $AB$ to be the length of any of those elementary segments. Take any three consecutive sides $AB$, $BC$, and $CD$ on the boundary of $\Gamma$. Consider the convex region bounded by the segment $BC$ and the rays complementary to the rays $BA$ and $CD$ (including the boundary). If this region is unbounded (see the left figure below), then it contains some lattice point $T$ (e.g., the point with $\overrightarrow{BT}=\overrightarrow{AB}$), and any such point $T$ satisfies the problem requirements. Thus, in what follows we assume that the two rays cross each other at some point $X$. Assume further that the triangle $BCX$ contains no lattice points outside the segment $BC$, as any other such point would satisfy the requirements.

Let $C_{\ast }$ be a lattice point on the segment $BC$ such that $B{C}_{\ast }=\ell (BC)$, let $X_{\ast }$ be the point on $BX$ such that $C_{\ast }{X}_{\ast }\parallel CX$, and let $D_{\ast }$ be the point such that $\overrightarrow{C_{\ast }{D}_{\ast }}=\overrightarrow{CD}$ (see the right figure below). Then the triangle $B{C}_{\ast }{X}_{\ast }$ contains no lattice points apart from $B$ and $C_{\ast }$. Consider the half-plane determined by the line $BC$ and containing no interior points of $\Gamma$. Let $\ell$ be the line in that half-plane parallel to $BC$, containing some lattice points, and nearest to $BC$ among such. Let the ray $AB$ meet $\ell$ at a point $A^{\prime }$ which belongs to the elementary segment $KL$ on $\ell$ (we assume that $\overrightarrow{KL}=\overrightarrow{B{C}_{\ast }}$; the point $A^{\prime }$ may coincide with $L$ but not with $K$). Then the ray $D_{\ast }{C}_{\ast }$ crosses the ray $LK$ (excluding $L$), otherwise $L$ lies in the triangle $B{C}_{\ast }{X}_{\ast }$. The only lattice points contained in the parallelogram $BKL{C}_{\ast }$ are its vertices. This yields that there are no lattice points strictly inside the strip defined by the parallel lines $BK$ and $C_{\ast }L$.



Let $M$ and $N$ be the meeting points of the rays $B{X}_{\ast },C_{\ast }L$ and $C_{\ast }{X}_{\ast },BK$, respectively. Then the segments $BM$ and $C_{\ast }N$ contain no lattice points except their endpoints, so $\ell (AB)\ge BM$ and $\ell (DC)=\ell (D_{\ast }{C}_{\ast })\ge C_{\ast }N$. Therefore, $$\frac{B{X}_{\ast }}{\ell (AB)}+\frac{C_{\ast }{X}_{\ast }}{\ell (CD)}\le \frac{B{X}_{\ast }}{BM}+\frac{C_{\ast }{X}_{\ast }}{C_{\ast }N}=\frac{B{X}_{\ast }}{BM}+\frac{M{X}_{\ast }}{BM}=1.(\ast )$$ Choose now $BC$ to be a side of largest elementary length. Then $$(1\ge )\frac{B{X}_{\ast }}{\ell (AB)}+\frac{C_{\ast }{X}_{\ast }}{\ell (CD)}\ge \frac{B{X}_{\ast }+C_{\ast }{X}_{\ast }}{\ell (BC)}=\frac{B{X}_{\ast }+C_{\ast }{X}_{\ast }}{B{C}_{\ast }},$$ which contradicts the triangle inequality.

REMARKS. (1) The usage of elementary length seems to be crucial. In particular, under the assumption that the triangle $BCX$ contains no lattice points outside $BC$, an inequality $$\frac{BX}{AB}+\frac{CX}{CD}\le 1$$ similar to () does not necessarily hold. (2) Any lattice parallelogram of unit area may be transformed into a unit square by an affine transform preserving the set of lattice points. If one applies such a transform to the parallelogram $BKL{C}_{\ast }$, inequality () may become more transparent.

---

Alternative solution.

We use the same notions of elementary segments and elementary lengths as in Solution 1. We say that a segment is sloped if it is neither horizontal nor vertical. If $\Gamma$ has no sloped sides, then $\Gamma$ is a rectangle, and the problem statement is trivial: one may choose any lattice point on the extension of any side. So, in what follows, we assume that $\Gamma$ has a sloped side.

Lemma 1. Let $BC$ be a sloped segment of the boundary of $\Gamma$ with no lattice points in its interior, and let $P$ be a lattice point such that the segments $PB$ and $PC$ are not sloped, and the triangle $PBC$ lies outside $\Gamma$. Then there exists a unique lattice point $X$ in the triangle $PBC$ such that the area of the triangle $XBC$ is $1/2$. Proof. Choose a lattice point $Q$ such that $PBQC$ is a rectangle. As in Solution 1, let $\ell$ denote the line through some lattice point parallel to $BC$, lying outside $\Gamma$, and nearest to the line $BC$ under these constraints (see the left figure below). The line $\ell$ crosses the interior of the angle $BQC$ along an interval of length $>BC$, so this interval should contain a lattice point $X$. The triangle $XBC$ contains no lattice points apart from the vertices, so its area is $1/2$ due to Pick's formula. Moreover, any such point $X$ should lie within the angle $BPC$, and $\ell$ crosses this angle along a segment of length $<BC$. Hence $X$ is the required unique lattice point. $\square$



Denote the point $X$ defined in Lemma 1 by $f(AB)$.

Lemma 2. Let $AB$ and $BC$ be two consecutive sides on the boundary of $\Gamma$, and let $B{A}_{\ast }$ and $B{C}_{\ast }$ be elementary segments on the sides $BA$ and $BC$, respectively. Assume that both coordinates of $\overrightarrow{BC}$ are positive, and that the line $AB$ strictly separates the points $C$ and $X=f(B{C}_{\ast })$. Then both coordinates of the vector $\overrightarrow{A_{\ast }B}$ are also positive, and $B{A}_{\ast }>B{C}_{\ast }$. Proof. Since $AB$ separates $X$ and $C$, the vector $\overrightarrow{A_{\ast }B}$ is a linear combination of $\overrightarrow{c}=\overrightarrow{B{C}_{\ast }}$ and $\overrightarrow{x}=\overrightarrow{BX}$ with positive coefficients; so the coordinates of $\overrightarrow{A_{\ast }B}$ are positive. Since the area of the triangle $BXC$ equals $1/2$, the vectors $\overrightarrow{c}$ and $\overrightarrow{x}$ span the whole lattice, so the coefficients of the linear combination are integers. Finally, the angle between $\overrightarrow{c}$ and $\overrightarrow{x}$ is acute, so $B{A}_{\ast }=|\overrightarrow{A_{\ast }B}|\ge \sqrt{|\overrightarrow{c}{|}^2+|\overrightarrow{x}{|}^2}>|\overrightarrow{c}|=B{C}_{\ast }$, as desired. $\square$

Now, choose a sloped side $BC$ of $\Gamma$ of a maximal elementary length, and let $ABCD$ be the corresponding part of the boundary of $\Gamma$. Let $C_{\ast }$ and $B_{\ast }$ be the points on the segment $BC$ such that $B{C}_{\ast }=B_{\ast }C=\ell (BC)$. Let $X=f(B{C}_{\ast })$ and $X^{\prime }=f(B_{\ast }C)$. Then, due to Lemma 2, the line $AB$ does not separate $X$ and $C$, and the line $CD$ does not separate $X^{\prime }$ and $B$. Therefore, the segment $X{X}^{\prime }$ lies in the same angle of the lines $AB$ and $CD$ as $\Gamma$, so $X$ may serve as a suitable vertex $T$ of $\Delta$.