For each point $X$ in the plane, a real number $r_X > 0$ is assigned such that $2|r_X - r_Y | \le |XY |$, for any two points $X, Y$ . (Here $|XY |$ denotes the distance between $X$ and $Y$) A frog can jump from $X$ to $Y$ if $r_X = |XY |$. Show that for any two points $X$ and $Y$ , the frog can jump from $X$ to $Y$ in a finite number of steps.
Problem
Source: India Postals 2015 Set 1
Tags: combinatorics
13.01.2016 11:51
Bump! Any solution?
15.01.2016 15:17
First, note that $r(X): \mathbb{R}^2\to \mathbb{R}^+$ is a continuous function. Fix $X_0\in\mathbb{R}^2 $. Then, the frog can jump to any point on the circle $C(X_0,r_0)$, with centre $X_0$ and radius $r_0$, where $r_0=r(X_0)$. For every $X\in C(X_0, r_0) $ we have $r(X)\in [r_0/2, 3r_0/2]$. When we drive $X$ through $C(X_0,r_0)$, the circles $C(X,r(X))$ will sweep all the area between $C(X_0,r_0/2)$ and $C(X_0,r_0)$, which follows from the continuity of $r(X)$. That's the frog can jump to any point of this ring within two jumps. For any $X\in C(X_0, r_0/2) $ it holds $r(X)\in [3r_0/4, 5r_0/4]$. Applying the above claim to $X$, it follows the frog can jump from $X$ to any point on $C(X,5r_0/8)$. Since $C(X,5r_0/8)$ will sweep a certain area around $X_0$ when $X$ runs through $C(X_0, r_0/2)$ we conclude the frog could jump from $X_0$ to any point between $C(X_0,r_0/8)$ and $C(X_0,r_0)$ within $4$ jumps. Applying again this argument to every point on $X\in C(X_0, r_0/2) $, this time we get the frog can reach from $X_0$ to any point inside the circle $X\in C(X_0, r_0/4) $ within no more than $8$ jumps. Now, we are ready to proceed. Consider some points $X_0, Y_0\in \mathbb{R}^2$. Let $D$ be the closed disk $\{X : |X-X_0|\leq |X_0Y_0|\}$. Then $r(X)$ reaches its minimal value $r_0>0$ on $D$. It means the frog can reach out from any $X\in D$ to all point within the distance of $r_0/4$, that's starting from $X_0$ it will reach $Y_0$.