Given an integer $n\ge 3$, a real number $\alpha>0$, and a set of real
numbers with finitely many elements $ S= \{ k_1,k_2,…,k_r\}$, show that
there exists a convex polygon with $n$ lattice vertices (that is,
whose every vertex belongs to $\mathbb{Z}^2$), such that for any segment
inside this polygon, if its slope is in $S$, its length will not exceed
$\alpha$.(Proposed by 虫仙).
I don't know if I understood the problem well, I think we could just get a very small regular $ n$-gon (with main diagonal less than $a$).
Since the vertices are lattice points, a diagonal measures at least $\sqrt{2}$, which is larger than $a$ if for example $a=0.1$.
This problem is from the NGC Girls MO.
Best Answer
EDIT: After talking with a friend about this problem, I realized that I actually just solved the case $n=3$. The general case, however, follows directly: we can take a triangle satisfying the problem's conditions for the length $\frac\alpha n$, and scale it up by a factor of $n$. By extending its long side, we can create $n-1$ rows of points in the triangle's interior. This is more than enough to build a convex lattice $n$-gon, which will satisfy the problem's constraints, being in the interior of a triangle that does.
The problem essentially asks us to prove that, for every set of directions, there exists a convex lattice polygon as “thin” as we want it to in every of those directions. To prove this, we’ll construct a lattice triangle satisfying our constraints, for every choice of $S$, $\alpha$.
To do this, we’ll need two lemmas.
Lemma $\mathbf1$:
For every segment $\ell$ of slope $\frac pq$ connecting two lattice points, with $p$, $q$ coprime integers, there exists a lattice point $A$ at a distance of no more than $\frac 1q$ of $\ell$.
Proof:
Consider the leftmost extreme of $\ell$, with coordinates $(x,y)$. If $\frac pq=\frac01$, then $A=(x+1,y)$ suffices. Otherwise, let $0\leq a<q$ be a multiplicative inverse of $p\bmod q$. The lattice point $A=\left(x+a,y+\frac{ap-1}q\right)$ is at a distance of $\frac 1q$ from the point $\left(x+a,y+\frac{ap}q\right)\in\ell$, so that the distance from $A$ to $\ell$ does not exceed our desired amount. $\square$
Lemma $\mathbf2$:
For every $\bigtriangleup ABC$ and every $m$, if the cevian $AX$ with slope $m$ is contained in $\bigtriangleup ABC$, it is the longest segment with such slope inside of the triangle.
Proof:
Take a segment $PQ$ of slope $m$ inside $\bigtriangleup ABC$. We can extend it to a segment $P’Q’$ whose endpoints are in the perimeter of the triangle. This segment will either be contained in $\bigtriangleup ABX$ or in $\bigtriangleup ACX$. Either way, it will be smaller than $AX$, by Thales. $\square$
We’re now ready to begin our construction.
For every $m\in S$, we can create an associated angle $0\leq m_a<\pi$, that represents the (directed) angle of a line with slope $m$ with respect to the horizontal. We’ll call the set of all of these angles $S_a$.
Now, we can consider an arbitrary $\theta\not\in S_a$. Let $2\varepsilon$ be the smallest distance ($\text{mod }\pi$) from $\theta$ to any element of $S_a$. Since $\mathbb Q$ is dense in $\mathbb R$, we can take a line $\ell$ through two lattice points with slope $\frac pq$, with $p$, $q$ coprime integers, such that $\ell$ makes a (directed) angle with the horizontal between $\theta-\varepsilon$ and $\theta+\varepsilon$ ($\text{mod }\pi$), and such that $$q\geq\frac1{\sin(\varepsilon)\alpha}.$$ By lemma $\mathbf1$, we can take a lattice point $A$ at a distance of $d\leq\frac 1q$ from $\ell$. Then, we can take lattice points $B$ and $C$ in $\ell$ “far enough”, so that the resulting $\bigtriangleup ABC$ contains cevians from $A$ with all slopes in $S$. Finally, by lemma $\mathbf2$, the length of any segment in $\bigtriangleup ABC$ with a slope $m\in S$ will not exceed the length of the corresponding cevian $AX$, which measures $$\frac d{\sin(\angle AXB)}\leq\frac d{\sin(\varepsilon)}\leq\frac1{q\sin(\varepsilon)}\leq\alpha,$$ just as we wanted. $\blacksquare$