5

There is a unit circle and 4 points inside the circle. The problem is to prove at least two are at distance less than or equal to $\sqrt2$

Asinomás
  • 105,651
  • 2
    Without loss of generality you can take the points to lie on the circle. Now show that the quadrilateral defined by the four points has an edge length at most the edge lengths of the square whose diagonals are diameters of the circle. This square has edge lengths $\sqrt{2}$. – tharris Jul 03 '13 at 10:29
  • I cant see all of that. Why is it with loss of generality that the points is on the circle and the other part I can't see rightaway either. – Asinomás Jul 03 '13 at 10:46
  • I think Tom Harris is trying to say that we can use the maximum principle to reduce things to the boundary. On the boundary, at least two points have an arc-difference $\le \pi/2$, because the sum of the four differences is $2\pi$, so that their distance is at most $\sqrt2$. Hope this helps. – awllower Jul 03 '13 at 10:50
  • the second part does help actually. But what is the maximum principle? – Asinomás Jul 03 '13 at 10:53
  • I think (IIRC, for my analysis is not good.) that it says that a convex function must achieve its maximum on the boundary. So you just have to examine the bundary case. Since our distance funciton is convex(the second derivative is $2>0$), this principle seems to be applicable. Yes, it has to be convex. And I shall suggest Tom Harris to write an answer then. – awllower Jul 03 '13 at 10:56
  • And we can try to prove the ùaxiùuù principle this way: if $f\ge0$, and if $f$ has a maximum at an interior point $c\in(a,b)$, then $f'(c)=0$ and $\begin{cases}f'(x)>0&x<c\f'(x)<0&x>c\end{cases}$. But this contradicts the hypothesis that $f"\ge0$. – awllower Jul 03 '13 at 11:10
  • 2
    @TomHarris You need to be careful about the wlog assumption because the best position for seven points has one at the centre of the circle - so this does need a proper justification. – Mark Bennet Jul 03 '13 at 11:29

3 Answers3

4

An idea: taking the circle $\,S^1:=\{(x,y)\in\Bbb R^2\;;\;x^2+y^2=1\}\,$ in order to use some analytic geometry/linear algebra in case of need, we can argue as follows:

If two points $\,w_i:=(x_i,y_i)\;,\;i=1,2\;$ , lay on the same quadrant (including the respective parts of both axis in the quadrant), then their maximal distance is $\,\sqrt2\;$ , because

$$||w_1-w_2||^2=||w_1||^2+||w_2||^2-2\langle w_1\,,\,w_2\rangle$$

But

$$\min_{w_i\in S^1}|\langle w_1\,,\,w_2\rangle|=\min_{w_i\in S^1}||w_1||\,||w_2||\cos\theta=0\iff \theta=\frac\pi2\implies$$

$$||w_1-w_2||^2\le ||w_1||^2+||w_2||^2\le2$$

After the above one can see that the maximal possible distance between four points on the unit circle or within the unit disk is attained when they are on the intersection of the circle with the axis, i.e. on the points $\,(-1,0)\,,\,(1,0)\,,\,(0,-1)\,,\,(0,1)\,$ , and then the distance between any two consecutive (clock or anticlockwise) points is precisely $\,\sqrt2\,$ (between antipode points it is, of course, $\,2\,$ ...)

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
1

Suppose $O$ is the center of the circle. Now take $4$ points $A_1,A_2,A_3$ and $A_4$ on the circumference of the circle such that $OA_1$ passes through one of the $4$ points inside the circle and $\angle A_iOA_{i+1}=\pi /2$ for each $i$. Now consider the sector $A_1OA_2$; note that $|A_1O|=|A_2O|=1\leq\sqrt{2}$ and $|A_1A_2|=\sqrt{2}$. Hence any two points in the sector $A_1OA_2$ must have distance less than or equal to $\sqrt{2}$ and the same holds for all other sectors. Now since one point is on the boundary of two sectors, after you choose other three points at least two must be inside or on the boundary of the same sector.

pritam
  • 10,157
1

here is a geometry way to prove the max distance is $\sqrt{2}$ is a quadrant area:

enter image description here

$A,B$ are the two points in area $FOG$, WLOG, let $AO \ge BO$,draw a circle with $r=AO$, cross $OB$ at $C$.

look at $\angle CBA$, there are 2 cases:

case I: if $\angle CBA< \dfrac{\pi}{2}$, in $\triangle ABO, \angle ABO > \dfrac{\pi}{2} \implies AB < AO \le 1 $,

case II: if $\angle CBA \ge \dfrac{\pi}{2} $, in $\triangle ABC,\angle CBA$ is max, $\implies AC \ge AB$,(when $B=C, AC=BC$)

it is trivial that $\triangle DOE \sim \triangle AOC ,DO\ge AO \implies DE \ge AC \implies AB \le DE $

in $\widehat { FG}, \widehat { FG} \ge \widehat {DE} \implies FG \ge DE \implies AB \le FG=\sqrt{2}$

To summary above 2 cases, $AB_{max}=\sqrt{2}$ when and only when $A=F$ and $B=G$

The rest induction is same as DonAntonio's post.

chenbai
  • 7,581