3

Suppose there are four points inside a unit square.The problem is to prove there is a pair of points with distance less than or equal to one.

Asinomás
  • 105,651
  • 2
    i think the idea is to partition the square in 3 equal parts and to apply the pigeonhole principle. Then see what the maximum distance between two points in that part of aria is. – sigmatau Jul 03 '13 at 14:13
  • How can I partition a square into three areas, each of which should fit inside a circle of diameter 1? – Asinomás Jul 03 '13 at 14:16
  • 2
    What have you learnt from your previous question that you can apply here? (The answer could be "nothing", but I'm just curious.) – Calvin Lin Jul 03 '13 at 14:22
  • @AmireBendjeddou I believe it is harder than that. Note that at least 2 corners will lie in the same part (equal or not), and hence it is possible for the 2 points to be at distance >1 apart. – Calvin Lin Jul 03 '13 at 14:24
  • @CalvinLin Yes.It was just a first attempt. – sigmatau Jul 03 '13 at 14:28
  • In the other problem it wasn't possible to partition into three section either.But since there are infinite ways to partition the points into 4 equal sectors in the case of the circle it seemed to be able to guarantee that at least two of them where in the same sector. – Asinomás Jul 03 '13 at 14:33
  • I'm not being very clear. every point is going to be the head of a vector coming from the origin with norm less than or equal to 1 and that comes out at an angle between 0 and 2 pi. In the other problem it was guaranteed that there would be two points which where the endpoints of vectors that came out at angles with differences less than or equal to pi/2. Therefore guaranteeing they are in the same sector of the partition that the two axes give use when we rotate the circle phi degrees. Where phi is the angle of one of the two vectors. Hope this makes sense. – Asinomás Jul 03 '13 at 14:38
  • I don't see how we can do the same for the square.( in other words: nothing)@CalvinLin – Asinomás Jul 03 '13 at 14:38
  • @Omnitic The "infinite ways" wasn't important. What was important was that there existed 1 way, and the proof holds for that particularly chosen way. – Calvin Lin Jul 03 '13 at 14:52

1 Answers1

3

From your previous question, if we have 4 points in a circle of radius $\frac{1}{ \sqrt{2} } = \frac{\sqrt{2} } {2} $, then there must be 2 points distance less than or equal to $\frac{ \sqrt{2} } { \sqrt{2} } = 1$.

Now, completely cover the unit square with a circle of radius $\frac { \sqrt{2}}{2}$, and apply the previous question. Hence, we are done.

Of course, we could have simply applied DonAntonio's proof to the 4 regions are the triangles cut out by the main diagonals, but that takes unnecessary work.

Morale of the story: Always resolve a problem to a previous seen state (Just kidding).

Community
  • 1
Calvin Lin
  • 68,864