|
|
Re: Dividing points equally in a plane
Posted:
May 20, 2006 5:58 AM
|
|
* Garrett Baird
> Hello all,
> I've been thinking about this problem for a few days now: say I have
> an even number (call it n) of points, no three colinear, scattered in
> the plane. How many ways are there to divide these points into two
> groups, each containing n/2 points, such that the groups can be
> separated by a line? I think the answer is n, but I can't prove it.
Draw a circle around all the points, and draw all dividing lines.
Given one of the lines and one of the points where the line crosses
the perimeter of the circle, call it P. Follow the perimeter until
you find the next dividing line, call the point Q. Look at only those
two lines, the circle and the points. You get four areas:
!Q
--+----
/ ! \
/ ! \
/ x ! X \
P / ! \
-+------+-------+--
\ ! /
\ Y ! y /
\ ! /
---+-----
!
!
Let x, X, y and Y denote the number of points inside the four areas.
A little reasoning should make it clear that:
(1) x+X = y+Y = n/2
(2) x=y and X=Y
If x=y=0, the two lines don't imply two different dividings and this
is of course thrown out.
Continue from here....
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 45 00 39 94
|
|
