5
$\begingroup$

Six points are to be chosen in a unit disk ($x^2 +y^2 \leq 1$) , such that distance between any two points is greater than 1? I am unable to, I think I want to prove formally that no matter how the six points are chosen, there are two points with distance at most 1 from each other.

For seven points, I think pigeonhole principle could be used to prove there is no such arrangement. We can easily choose seven points such that maximum distance between any two points is equal to 1. Something like this in the figure. Now you can't increase the distance between the points(orange) chosen on the circle as the side length itself is one.enter image description here

$\endgroup$
  • 1
    $\begingroup$ For seven points you don't need induction. Your figure divides the disk into six sectors. If you put seven points in the disk there must be two in the same sector, but there is no pair of points within a sector at a distance greater than $1$. $\endgroup$ – Ross Millikan Aug 1 '18 at 0:30
  • $\begingroup$ Yup, Sorry I was thinking of pigeon hole principle. $\endgroup$ – T.Harish Aug 1 '18 at 1:24
  • $\begingroup$ Could you prove that any two points from the same sector(including boundary) are atmost $1$ distance from each other? $\endgroup$ – T.Harish Aug 1 '18 at 2:21
  • $\begingroup$ Yes, but that doesn't do what we need. If we could cut into five sectors with no points in a sector more than $1$ apart we would be home, but the sectors are larger than that. You can't have more than five on the circumference that are more than $1$ apart. We need to show that putting a point in the middle will be within $1$ of one of them. $\endgroup$ – Ross Millikan Aug 1 '18 at 2:35
  • $\begingroup$ Could you provide the proof of that previous statement then? Also the statement " You can't have more than five on the circumference that are more than 1 apart", is intuitive, but not trivial. Consider the unit circle which is a circumcircle of a regular hexagon. So we can get six points at a distance of 1 apart on a unit circle. $\endgroup$ – T.Harish Aug 1 '18 at 3:04
2
$\begingroup$

Apply the same argument as for 7 points (from the question statement and Ross Millikan comment), except make sure to draw the 6 sectors such that one of the 3 boundary diameters contains one of the 6 points. That is, draw the 6 sectors after you know the points, such that one of the points, say $P_1$, lies on one of the boundaries.

If any points are in either of the two neighboring sectors to $P_1$, they are at distance $\le 1$ from $P_1$. If not, by the pigeonhole principle, one of the 4 other sectors contains 2 of the 5 other points. And those two points are a distance of at most 1 from each other. So we're done.

Note: I am not sure how to cleanly prove the fact that two points in a $\pi/3$-sector are a distance of at most 1 apart. I have a way that I think works using law of cosines, but it seems peripheral to the question & a pretty inelegant argument, so not including it for now.


EDIT: Re:your comment OP, yeah I also don't have a nice way to make fully convincing/clean the intuition that no 2 points in a sector have distance $> 1$.

Here's the inelegant law of cosines way mentioned above which shows that two points in a sector have distance $\le 1$:

We're given two points $P_1$ and $P_2$ in one $\pi/3$-sector. Say the two points are at a distance $r_1$ and $r_2$, respectively, from the center. Let the central angle between them be $\theta \le \pi/3$.

By the law of cosines, the square of the distance between $P_1$ and $P_2$ is $$d(P_1, P_2)^2 = r_1^2 + r_2^2 - 2r_1r_2\cos\theta \le r_1^2 + r_2^2 - 2r_1r_2(\frac{1}{2}) = r_1^2 + r_2^2 - r_1r_2$$

because $r_1, r_2 \ge 0$ and $0 \le \theta \le \pi/3$.

Now we have to show $r_1^2 + r_2^2 - r_1r_2 \le 1$ for $0 \le r_1, r_2, \le 1$.

There's probably be a nicer way to proceed here too, but here's one argument: we have $r_1^2 + r_2^2 - r_1r_2 = (r_1 - \frac{1}{2}r_2)^2 + \frac{3}{4}r_2^2$. With $0 \le r_1, r_2, \le 1$, for fixed $r_2$, this expression is maximized when $r_1 = 1$ (since $r_1=1$ maximizes $|r_1 - \frac{1}{2}r_2|$ for every $0 \le r_2 \le 1$, uniquely except at $r_2=1$ when $r_1=0$ is also a maximizer).

So, for $0 \le r_1, r_2, \le 1$,

$$r_1^2 + r_2^2 - r_1r_2 = \left(r_1 - \frac{1}{2}r_2\right)^2 + \frac{3}{4}r_2^2 \le \left(1 - \frac{1}{2}r_2\right)^2 + \frac{3}{4}r_2^2 \\= 1 - r_2 + r_2^2 = \left(r_2 - \frac{1}{2}\right)^2 + \frac{3}{4} \le \frac{1}{4} + \frac{3}{4} = 1$$

(maximum achieved at $r_2 = 0$ or $r_2=1$ when $r_1 = 1$).

$\endgroup$
  • $\begingroup$ Even though it feels, but I am not entirely convinced that "there is no pair of points within a sector at a distance greater than 1" $\endgroup$ – T.Harish Aug 1 '18 at 2:18
  • 2
    $\begingroup$ @T.Harish Suppose points P,Q in the sector attain the maximum possible distance, the diameter of the sector. (The maximum is attained by compactness.) Clearly, both points must lie on the boundary. The boundary consists of two straight line segments and a circle arc. If one of the points lies on a straight line segments, then by elementary geometry, since the distance is maximized, the point must be an endpoint of the segment. Thus each of the two points must lie on the circular arc or at the origin. The only nontrivial case is P,Q on the circular arc. $\endgroup$ – bof Aug 1 '18 at 5:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.