Assume there are $ n\ge3$ points in the plane, Prove that there exist three points $ A,B,C$ satisfying $ 1\le\frac{AB}{AC}\le\frac{n+1}{n-1}.$
Problem
Source: Chinese TST 2007 2nd quiz P3
Tags: inequalities, combinatorial geometry, analytic geometry, geometry
18.08.2009 17:12
Could you help me please?Although I have tried for many days,I still cannot solve this problem.
30.05.2011 20:57
Bump. Such a nice problem, yet remain unsolved for 2 years. I've got some raw idea. Take a point $O$ on the convex hull, and place them on the cartesian plane such that $O$ is the origin and each point has a nonnegative abscissa. Label the other $n-1$ points $A_1,A_2,\ldots,A_{n-1}$ such that the distances from $O$ is increasing. In my imagination, $A_{n-1}$ is so far away from the other points, so something like $\frac{A_{n-1}A_0}{A_{n-1}A_1}$ could work. Unfortunately, $\left(\frac{n+1}{n-1}\right)^n$ isn't that large, in fact it converges to $e^2$. Fortunately, we now know that the points shouldn't be so far away apart.
17.02.2013 01:58
jgnr wrote: Label the other $n-1$ points $A_1,A_2,\ldots,A_{n-1}$ such that the distances from $O$ is increasing. In my imagination, $A_{n-1}$ is so far away from the other points, so something like $\frac{A_{n-1}A_0}{A_{n-1}A_1}$ could work. I think this is a good approach, but it might be cleaner to take $A_0A_{n-1}$ as the overall maximal distance (i.e. without restricting $A_0$ to be a point on the convex hull). Let $k=\frac{n+1}{n-1}$ and $M=A_0A_{n-1}$. To gain intuition, it helps a lot to find a clean solution when all the points are collinear. In particular, for odd $n$, simply considering $A_iA_{i+1}$ minimal works, but this is messy for even $n$ and rather ineffective/nonrestrictive for the original problem. Another natural approach is to go by contradiction; then $\frac{A_0A_{i+1}}{A_0A_i}\ge k\implies \frac{A_iA_{i+1}}{A_0A_i}\ge k-1 = \frac{2}{n-1}$. If we WLOG assume $A_0A_m\ge A_0A_{n-1}/2$ where $m=\lceil{(n-1)/2}\rceil$, then $\frac{A_0A_m}{A_{n-1}A_m} \ge k\implies A_0A_m\ge M\frac{k}{k+1} = M\frac{n+1}{2n}$. Summing up $A_iA_{i+1} \ge (k-1)A_0A_i\ge (k-1)A_0A_m$ for $i\ge m$ in addition to $A_0A_m\ge A_0A_m$ yields \[ M \ge [1+(n-1-m)(k-1)]A_0A_m \ge [1+\lfloor{\frac{n-1}{2}}\rfloor \frac{2}{n-1}] M\frac{n+1}{2n} > M, \]which is absurd. For the original problem, the same thing works, except we WLOG $A_0A_m\ge A_mA_{n-1}$ (i.e. $A_m$ to the right of the perpendicular bisector of $A_0A_{n-1}$), use $\frac{A_0A_m}{M-A_0A_m} \ge \frac{A_0A_m}{A_{n-1}A_m} \ge k$ (from the triangle inequality) to get a lower bound on $A_0A_m$, and multiply the $\frac{A_0A_{i+1}}{A_0A_i} \ge k$ to get $\frac{M}{A_0A_m} \ge k^{n-1-m} \ge 1+(k-1)(n-1-m)$ to get the final inequality. Of course, we can replace $\frac{n+1}{n-1}$ with the unique positive solution to $k^{\lfloor{(n+1)/2}\rfloor} = k+1$.
24.06.2018 12:52
Suppose not. Consider two points $X$ and $Y$ such that $XY=\max$ and WLOG $XY=1$. Label the remaining points in two ways: $A_1,A_2,\dots,A_{n-2}$ and $B_1,B_2,\dots,B_{n-2}$ such that $XA_1 \geq XA_2 \geq \dots \geq XA_{n-2}$ and $YB_1 \geq YB_2 \geq \dots \geq YB_{n-2}$. Obviously, $XA_k,YB_k<\left(\dfrac{n-1}{n+1}\right)^k$ Claim: there is point $Z=A_i=B_j$ such that $i \geq \left\lfloor \dfrac{n}{2} \right\rfloor$ and $j \geq \left\lfloor \dfrac{n-1}{2} \right\rfloor$. Proof: since $\left\lfloor \dfrac{n}{2} \right\rfloor+\left\lfloor \dfrac{n-1}{2} \right\rfloor=n-1$, points $A_i$, where $i \in \left[\left\lfloor \dfrac{n}{2} \right\rfloor,n-2\right]$ cannot be covered by points $B_j$, where $j \in \left[1,\left\lfloor \dfrac{n-1}{2} \right\rfloor-1\right]$. $\square$ Then by triangle inequality $1=XY \leq ZX+ZY<\left(\dfrac{n-1}{n+1}\right)^{\left\lfloor \frac{n}{2} \right\rfloor}+\left(\dfrac{n-1}{n+1}\right)^{\left\lfloor \frac{n-1}{2} \right\rfloor}$, which doesn’t hold for $n\geq 3$ (for small $n$, check by hands; for larger $n$, replace $\left\lfloor\dfrac{k}{2}\right\rfloor$ with $\dfrac{k-1}{2}$ and check by derivative that RHS is decreasing). $\blacksquare$
12.08.2021 23:10
Beautiful result. Suppose we have a set of $n$ points not satisfying the condition. Take the longest segment, $P_1P_2,$ assume WLOG it is $1.$ Let the distances from the other $n-2$ points to $P_1$ be $a_1 > a_2 > \dots >a_{n-2}.$ Let the distances from the other $n-2$ points to $P_2$ be $b_1 > b_2 > \dots > b_{n-2}.$ We have the property $a_k, b_k < \left( \frac{n-1}{n+1} \right)^{k}.$ Case 1, $n = 2m$ for an integer $m > 1.$ We must have a point $P$ whose distances to $P_1$ and $P_2$ are strictly less than $\left( \frac{n-1}{n+1} \right)^{m}$ and $\left( \frac{n-1}{n+1} \right)^{m-1}$ respectively. Otherwise, the points with distances $a_m, a_{m-1}, \dots a_{2m-2}$ from $P_1$ must also be points with distances $b_1, b_2, \dots b_{m-2}$ to $P_2,$ but this is impossible since $m-1 > m-2.$ It's not hard to see $\left( \frac{n-1}{n+1} \right)^{m} + \left( \frac{n-1}{n+1} \right)^{m-1} \le 1$ for $m \ge 2$ through calculus techniques violating the Triangle Inequality. Case 2, $n = 2m+1$ for an integer $m \ge 1.$ We must have a point $P$ whose distances to $P_1$ and $P_2$ are both strictly less than $\left( \frac{n-1}{n+1} \right)^{m}.$ Otherwise, the points with distances $a_m, a_{m-1}, \dots a_{2m-1}$ from $P_1$ must also be points with distances $b_1, b_2, \dots b_{m-1}$ to $P_2,$ but this is impossible since $m > m-1.$ It's not hard to see $2 \left( \frac{n-1}{n+1} \right)^{m} \le 1$ for $m \ge 1$ through calculus techniques violating the Triangle Inequality.