Given $2015$ points, show that it is possible to separate them such that $1007$ of them lie inside the circle

Solution 1:

(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.)

Solution 2:

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.