Let $0<\alpha<1$ be a fixed number. On a lake shaped like a convex polygon, at some point there is a duck and at another point a water lily grows. If the duck is at point $X{}$, then in one move it can swim towards one of the vertices $Y$ of the polygon a distance equal to a $\alpha\cdot XY$. Find all $\alpha{}$ for which, regardless of the shape of the lake and the initial positions of the duck and the lily, after a sequence of adequate moves, the distance between the duck and the lily will be at most one meter.
Problem
Source: Russian TST 2015, Day 7 P3
Tags: combinatorics, geometry
21.04.2023 21:17
We claim that only $\alpha\leq 1/3$ works. To prove that no greater $\alpha$ works, consider any triangle. Since any move restricts us to a zone formed by the union of three scaled triangles (with scale factor $1-\alpha<2/3$, with omothety centers in the vertices), we can never go in a small triangle around the barycenter. Therefore, if we start outside of this small triangle and we make sure this is big enough wrt $1m$, we can never get close to the barycenter. To prove that all $\alpha\leq 1/3$ work, we first prove the following lemma: Given any convex polygon, $beta\leq 1/2$ and a point $P$ inside it, there is a vertex $V$ such that $V'=P-\beta(V-P)$ still belongs to the polygon. To see this, it suffices to prove it in the case of a triangle (after triangulating the polygon, consider the triangle inside of which we can find $P$). In the case of a triangle $A_1A_2A_3$, consider the vertex (wlog $A_1$) such that $[PA_{i-1}A_{i+1}]$ is maximal. Its area must be at least one third of $[A_1A_2A_3]$; so, if $P'=A_1P\cap A_2A_3$, we must have $PP'/A_1P'\geq 1/3$, from which follows that $A_1'$ lies on the segment $PP'$ and thus inside the triangle. Returning to our problem, consider the lily $L=L_0$ and a circle $C_0$ of radius $1$ and center $L_0$. Now define inductively the circles $C_i$ in the following way: let $V_{i+1}$ be the vertex which satisfies the lemma (note that $\alpha\leq 1/3$ corresponds to $\beta=\alpha/(1-\alpha)<1/2$) with respect to the point $L_i$, and let $L_{i+1}=L_i-\beta(V_{i+1}-L_i)$; now, let $C_{i+1}$ be the circle with center $L_{i+1}$ and radius $1/(1-\alpha)$ times the radius of $C_i$. Now, it is clear by induction that if the duck is inside the circle $C_{i+1}$ it can go inside the circle $C_i$ by using the vertex $L_{i+1}$. So, since we want the duck to arrive inside $C_0$, it suffices to show that the radius of $C_n$ goes to infinity as $n\rightarrow\infty$, so that eventually the polygon is always contained in $C_n$ (we are using that the centers $L_n$ are all inside the polygon and that the polygon has bounded diameter). But this is trivial, since the $n$th radius is $r_n=(1/(1-\alpha))^n$, which clearly goes to infinity.