Let 0<α<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 α⋅XY. Find all α 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 α≤1/3 works. To prove that no greater α works, consider any triangle. Since any move restricts us to a zone formed by the union of three scaled triangles (with scale factor 1−α<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 α≤1/3 work, we first prove the following lemma: Given any convex polygon, beta≤1/2 and a point P inside it, there is a vertex V such that V′=P−β(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 A1A2A3, consider the vertex (wlog A1) such that [PAi−1Ai+1] is maximal. Its area must be at least one third of [A1A2A3]; so, if P′=A1P∩A2A3, we must have PP′/A1P′≥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=L0 and a circle C0 of radius 1 and center L0. Now define inductively the circles Ci in the following way: let Vi+1 be the vertex which satisfies the lemma (note that α≤1/3 corresponds to β=α/(1−α)<1/2) with respect to the point Li, and let Li+1=Li−β(Vi+1−Li); now, let Ci+1 be the circle with center Li+1 and radius 1/(1−α) times the radius of Ci. Now, it is clear by induction that if the duck is inside the circle Ci+1 it can go inside the circle Ci by using the vertex Li+1. So, since we want the duck to arrive inside C0, it suffices to show that the radius of Cn goes to infinity as n→∞, so that eventually the polygon is always contained in Cn (we are using that the centers Ln are all inside the polygon and that the polygon has bounded diameter). But this is trivial, since the nth radius is rn=(1/(1−α))n, which clearly goes to infinity.