Let $A,B,C$ be nodes of the lattice $Z\times Z$ such that inside the triangle $ABC$ lies a unique node $P$ of the lattice. Denote $E = AP \cap BC$. Determine max $\frac{AP}{PE}$ , over all such configurations.
Problem
Source: Stars O f Mathematics 2009 p3 - 1998 Moldova TST p11
Tags: lattice points, lattice, maximum, ratio, geometry
29.08.2019 05:13
We claim that the answer is $\boxed{5}$. This is achieved by letting $A = (0, 0), B = (3, 0), C = (2, 2).$ In this case, $P = (2, 1)$ and $\frac{AP}{PE} = 5.$ Let us now show that this is optimal. Let $x, y, z$ be the areas of $\triangle BPC, \triangle CPA, \triangle APB,$ respectively. Note that $\frac{AP}{PE} = \frac{y+z}{x}.$ Lemma 1. $x \le y+z, y \le x+z, z \le x+y$.
Lemma 2. $x, y, z \le 3.$
Furthermore, it's actually also true that segment $BC$ has three lattice points in its strict interior if and only if $x = 2y = 2z,$ and similarly for segments $CA$ and $AB$. In these cases, it's easy to check that $\frac{AP}{PE} \le 3.$ Hence, we may now suppose that each of segments $BC, CA, AB$ has at most two lattice points in their strict interiors. By Pick's Theorem, we now know that $x, y, z \le \frac{3}{2}.$ Together with $x, y, z \ge \frac12$, these results yield that $$\frac{AP}{PE} = \frac{y+z}{x} \le \frac{\frac32 + \frac32}{\frac12} = 6.$$To show that this cannot be achieved, we need only to show that it's impossible for segments $BC, CA, AB$ to have $0, 2, 2$ lattice points in their strict interiors, respectively. To see this, observe that in this case we'd have that both $\frac13 \cdot \overrightarrow{AB}, \frac13 \cdot \overrightarrow{AC}$ are vectors with both components integral, and so $A + \frac13 \cdot \overrightarrow{AB} + \frac23 \cdot \overrightarrow{AC}$ is an interior point of $BC$, contradiction. Hence, we've shown that the maximum value of $\frac{AP}{PE}$ is indeed $\boxed{5}$, as claimed. $\square$