Solve 2n Red and Blue Points on a Plane Problem

[Dragonfall]

There are 2n red and 2n blue points on a plane. I have to show that there's a line bisecting them. No idea how. Not homework.

 

[HallsofIvy]

What do you mean by "bisecting them"? Do you want a line such that n red points and n blue points are on either side of it?

 

[Dragonfall]

Yes.

EDIT: One more condition, no 3 of them of any color lie on a line.

 

[srijithju]

You can look at the following link :

http://books.google.co.in/books?id=...=proof of pancake theorem for points&f=false

Here the theorem is proved , assuming the question is that we have 2 bounded regions in a plane and that we wish to find a line that bisects the areas of both .

But you can extend the proof for the case when we are interested in bisecting a collection of points rather than areas .

By the way it doesn't seem to require that no three points of the same colour are on a line

 

[slider142]

First show that there exists a line on which none of the points lie. Then create 2 functions, one tells you how many dots are left of the line as a function of the angle t that the line makes with the positive x-axis and the other how many are right of it, where the pivot point is not in the smallest circle containing the points. Show that the function that is the difference of these functions must be 0 for some t. This part may be difficult, or there may be a better approach. The fixed point method above works great for continuous functions, but these functions are not.

However, if the goal is to separate the 2n red dots from the 2n blue dots for every possible configuration, this cannot be done, by a simple counterexample.

 

[Dragonfall]

The goal is to separate n red points and b blue points on one side, and the same on the other. The proof, or at least the simplest proof, should not be analytic. A combinatorial argument should suffice.

 

[srijithju]

First show that there exists a line on which none of the points lie. Then create 2 functions, one tells you how many dots are left of the line as a function of the angle t that the line makes with the positive x-axis and the other how many are right of it, where the pivot point is not in the smallest circle containing the points. Show that the function that is the difference of these functions must be 0 for some t. This part may be difficult, or there may be a better approach. The fixed point method above works great for continuous functions, but these functions are not.
.

Yes agreed that the function in this case is not continuous , but it is easy to see that the function ( the function I am talking about is the difference of no. of points on one side of the line to the other) shall take integer values between -2n and +2n . It is also seen that the function has to take all integer values between -2n and 2n ( unless the line that cuts the plane , intersects some of the points ( in which case you can assume that the intersected points shall lie on both or none of the sides of the line) , so the function most certainly has to take the value 0 somewhere in the interval . Is this not sufficient for the proof ?


As regards to "analytic proof " as mentioned by dragonfall , I am not very good in mathematics , so I don't understand what is an analytic proof is and what is not ( I checked the definition - "Using or subjected to a methodology using algebra and calculus" - I am not sure if we are using any calculus or algebra here by the way) . Is it not sufficient to prove something using any method whatsoever , why do we need a special kind of proof ?