14
$\begingroup$

Suppose there are $2015$ points on a plane, no three collinear. Show that you can draw a circle such that exactly $1007$ lie inside the circle.

Here is my solution:

First draw a line that divides the plane into two parts, one containing $1007$ points and the other containing $1008$ points. Now draw a circle tangent to this line, such that the centre of the circle is on the side containing $1007$ points. Note that $1007$ points cover only a finite amount of area. But we can make this circle as big as we like, and thus make sure that the points are inside the circle.

I have two questions:

1) Where are we using the "... no three collinear" part of the statement? I think that since a point has no size, we can always divide the plane into two parts, one having $1007$ points and the other having $1008$ points.

2)How rigorous is my solution?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I think "no three collinear" means you cannot consider diameter. So essentially, there "might" exist a circle, and except for 2 points the center and radius end point, rest 1005 points lie inside the circle more like a heap, or marbles in a sack. $\endgroup$ – MonK Mar 26 '15 at 13:01
  • 6
    $\begingroup$ The assumption of "no three collinear" isn't needed. For each pair of points draw their perpendicular bisector. This produces a finite set of lines. Pick some new point not on any of these lines, and consider a growing circle centred on this point. The points will pass into it one at a time, so at some time it will contain $1007$ of them. $\endgroup$ – Oscar Cunningham Mar 26 '15 at 13:26
  • 2
    $\begingroup$ @OscarCunningham What a great method man! It solves all the problems of the question extremely simply: your circle will never "hit" 2 points at once, as for that to happen you would have to be along a perpendicular bisector; much less about hitting more than 2 dots simultaneously (e.g. 3 dots), as that wold only occur if your new point were on the intersection of 2 or more bisectors. You just keep growing untill you hit 1007 :). OP, this guy has fully answered your question, and only in three lines! $\endgroup$ – Just_a_fool Mar 26 '15 at 15:16
  • 1
    $\begingroup$ @OscarCunningham, please add that as an answer. This type of (excellent) idea is not meant to be left buried in the comments (or at least I hope not). $\endgroup$ – rah4927 Mar 26 '15 at 15:26
7
$\begingroup$

(I originally left this as a comment, since it doesn't really answer the questions 1) and 2) that rah4927 asked. But due to popular demand I'm posting it as an answer.)

The assumption of "no three collinear" isn't needed. For each pair of points draw their perpendicular bisector. This produces a finite set of lines. Pick some new point not on any of these lines (nor any of the original points), and consider a growing circle centred on this point. The points will pass into it one at a time, so at some time it will contain 1007 of them.

(Note that we do use the unstated assumption that the original 2015 points are all distinct. Otherwise they could all just be the same point and we wouldn't be able to separate any of them.)

| cite | improve this answer | | | | |
$\endgroup$
4
$\begingroup$

2) I think your solution is correct. However, by making the argument somewhat more constructive, we can make the solution feel more rigorous (and see why the no three conlinear thing applies) IMO. This applies for especially when you choose your initial line.

Choose an outermost point from the 2015 points. Now choose a line that goes through this point, hence divides the plain to one side containing 2014 dots and one side containing none. If this can't be done because the chosen line runs through a second point such that the dot-holding side ends up with 2013 dots, then slightly rotate your line such that the second dot falls within the dot-holding half. Now if there were three point co-linear to our chosen line, we would to come up with something else, but the question explicitly prohibits the possibility of such a situation.

Now, start turning our line, we will along our turn, sweep across dots. Never will we sweep across 2 dots at once as no three dots are colinear. Keep sweeping untill we have crossed 1006 points. Now we will always be able to slightly move our line from our outermost initial point such that it falls into one half. This follows from considering the fact there is no smallest real number.

Now the rest of your argument applies.

1) You may be wondering why I brought up all this. Well, you could have many dots be colinear, and many sets of 3 dots be colinear; and I pretty sure you would always still be able to divide the dots into 1008/1007, but the algorithm/process of dividing the plane becomes more tricky and arduous. In the algorithm we formed above having 3 points be conlinear would potentially create some problems. Essentially, since we are being so abstract about the process of line creation, we would have to provide arguments for what happens if our partially arbitrarily chosen point and line ends up creating a problematic case.

So the condition with no three conlinear poitns makes the task simply easier, its not necessary for the division of the plane.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ You don't actually need the "rotate slightly" step, since you already have 1007 points on one side of the line. Just draw a circle tangental to the line in a different point than the initial point, then the initial point will never be inside the circle. $\endgroup$ – SBareS Mar 26 '15 at 13:37
0
$\begingroup$

To make it rigorous, imagine a line sweeping (this, as usual, is not my original idea) from outside in a direction not through any two points. As it passes through the swarm, it will divide into two regions where any desired number of points is on one side of the line. You can then construct your circle.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ If all the points lie on the same straight line, then doesn't it become easier to construct our line? Please tell me what I am missing. $\endgroup$ – rah4927 Mar 26 '15 at 13:13
  • $\begingroup$ Oops. You are right. My mistake. $\endgroup$ – marty cohen Mar 26 '15 at 13:31

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.