Given a convex polygon with vertices at lattice points on a plane containing origin $O$. Let $V_1$ be the set of vectors going from $O$ to the vertices of the polygon, and $V_2$ be the set of vectors going from $O$ to the lattice points that lie inside or on the boundary of the polygon (thus, $V_1$ is contained in $V_2$.) Two grasshoppers jump on the whole plane: each jump of the first grasshopper shift its position by a vector from the set $V_1$, and the second by the set $V_2$. Prove that there exists positive integer $c$ that the following statement is true: if both grasshoppers can jump from $O$ to some point $A$ and the second grasshopper needs $n$ jumps to do it, then the first grasshopper can use at most $n+c$ jumps to do so.
Problem
Source: St. Petersburg MO 2017 Grade 11 P7
Tags: combinatorics, number theory
dgrozev
07.05.2018 18:18
Since the polygon is convex, for any $v\in V_2$ we have $$(1)\,\,\,\,\,\,\,\,\,\,v=\alpha v' +\beta v'' $$where $v', v''\in V_1$ , $\alpha, \beta $ are non-negative reals and $\alpha+ \beta \leq 1$. Moreover, $\alpha,\beta$ are rational numbers, and since $V_2$ is a finite set, we can assume the denominator of all that coefficients is some natural number $N$. Suppose we have a lattice point $w$ (imagine it as a vector), which can be attained by both grasshoppers. Let the second grasshopper has made $n$ jumps to get to $w$, i.e. $w=\sum_{v\in V_2} a_v\cdot v$, where $a_v$ are non-negative integers with $\sum_{v\in V_2} a_v=n$. Representing each $v\in V_2$ as in $(1)$ we obtain: $$w=\sum_{v\in V_1} \alpha_v v $$where $\alpha_v$ are non-negative rationals with denominator $N$ and $\sum_{v\in V_1}\alpha_v\leq n$. Let $b_v := \lfloor \alpha_v\rfloor, c_v := \{\alpha_v\}\,,\, v\in V_1$. Denote: $$w_1 := \sum_{v\in V_1} b_v v \,,\, w_2 := \sum_{v\in V_1} c_v v$$It's clear the first grasshopper can reach $w_1$ by no more than $n$ jumps. We will show it can reach also $w_2$. Claim: Let $w,w_1$ are lattice points reachable by the first grasshopper. Then $w-w_1$ is also reachable by that grasshopper. Proof: We have: $$(2)\,\,\,\,\,\,\,\,\,\,w-w_1 = \sum_{v\in V_1} a_v v$$where $a_v$ are integers (not necessary positive). Since $0$ is inside the given polygon, it can be represented as: $$(3)\,\,\,\,\,\,\,\,\,0=\sum_{v\in V_1} \alpha_v v$$where $\alpha_v$ are positive rationals (yes, we can make all of them positive). Multiplying that equality by some integer, we can assume $\alpha_v$ are positive integers. Now, if we add $(3)$ to both sides of $(2)$ as many times as needed, we would get a representation of $w-w_1$ as in $(2)$ but with all coefficients positive. $\blacksquare$ Thus using the above claim we see $w_2$ is also attainable by the first grasshopper. Since all possible values of $w_2$ are finite (its coefficients are small rational numbers with denominator $N$) there is a constant $c$ (depending only on $V_2$) such that the first grasshopper can reach $w_2$ with at most $c$ hops. From $w=w_1+w_2$ , it follows $w$ is attainable by at most $n+c$ jumps.