Interesting new problems in combinatorial geometry
Steve Gray
I thought of these problems yesterday, 11/29/04.
1. There are n labeled points in the plane in general position, no 3 on a line. Draw a
directed line from the lower numbered point Pi to the higher numbered point Pj, j>i. Some of the
other points lie strictly to the left of the line, some strictly to its right. Let Eij be the # of
points on the left minus the # of points on the right. Let E = Sum(n >= j > i >= 1)Eij. How should
the points be arranged and labeled to maximize or minimize E (or make it exactly zero, if possible)?
Can E=0 for any odd n? (No for n=3.) There are papers on the number of lines which cut a point set
in half but this is different.
2. There are n points in the plane in general position: no 3 on a line, no 4 on a circle.
There are n(n-1)(n-2)/6 circles through all triplets of points. Each circle Ci, 1 <= i <=
n(n-1)(n-2)/6, strictly excludes Ti points and strictly encloses n-3-Ti. How should the n points be
arranged to maximize or minimize Sum(i) of Ti, and what are the maximum and minimum? For about 6
quick trials with 5 points, I get exclusion totals over all 10 circles of only 10, 11, and 12. Is it
always true that the total number of excluded points is at least equal to the number of circles?
3. Put n points are on a sphere and disallow any two being polar opposites, and define the
exteriors of all circles as larger than their interiors, and ask the same question.
4. Are there arrangements where some points are always enclosed or excluded? What is the
distribution of points enclosed or excluded, over all circles, and what property of the arrangement
does this depend on?
5. The same question can be asked of plane squares and ellipses through the appropriate
number of points.
Conjectures? Proofs?
Steve Gray
dove...@yahoo.com
> I thought of these problems yesterday, 11/29/04.
>
> 1. There are n labeled points in the plane in general position, no 3
on a line. Draw a
> directed line from the lower numbered point Pi to the higher numbered
point Pj, j>i. Some of the
> other points lie strictly to the left of the line, some strictly to
its right. Let Eij be the # of
> points on the left minus the # of points on the right. Let E = Sum(n
>= j > i >= 1)Eij. How should
> the points be arranged and labeled to maximize or minimize E (or make
it exactly zero, if possible)?
> Can E=0 for any odd n? (No for n=3.) There are papers on the number
of lines which cut a point set
> in half but this is different.
Writing Eij as sum_{k \neq i,j} {1, if Pk is left of Pi->Pj; else, -1},
we can rewrite E as sum_{i<j, k \neq i,j} {1, if Pk is left of Pi->Pj;
else -1}. In this formulation, each 3-element subset {a,b,c} of {1..n},
with a < b < c, contributes exactly three times to this sum: i = a, j =
b, k = c; i = a, j = c, k = b; and i = b, j = c, k = a.
If Pc is left of Pa->Pb, then this triplet contributes +1 to the sum
for E, getting +1 contributions when i = a, j = b, k = c, and i = b, j
= c, k = a, and a -1 for i = a, j = c, k = b. Call such a triplet
{a,b,c} positively oriented. Similarly if Pc is right of Pa->Pb, the
contribution of this triplet is -1 to the sum for E, and we can call
such a triplet negatively oriented.
With this in hand, we can write E as
E = sum_{{a,b,c} \in S(n,3)} {+1, if {a,b,c} is positively oriented
{-1, if {a,b,c} is negatively oriented
Thus it is clear that the maximum possible value for E is n choose 3,
which occurs when all triplets {a,b,c} are positively oriented, and
similarly that the minimum is the negative of n choose 3. These values
are both realizable... evenly distribute the n points along the
semicircle x^2+y^2=1, x>=0. Labelling the points 1 through n,
increasing in a counterclockwise fashion from the bottom yields a
labelled point-set where all triplets are positively oriented, and
reversing this labelling produces the opposite.
As far as E=0, since E is a sum of n choose 3 +/- 1's, it can only
yield a zero sum when n choose 3 is even, which requires n \neq 3 (mod
4). Don't know about the other cases.
Good luck with your investigations!
dove...@yahoo.com
It is becoming a scientific technique for controlling the child's
development. Sylvan Learning Centers, for example, have had great
success in motivating children to study, and psychological techniques
are also used with more or less success in many conventional schools.
"Parenting" techniques that are taught to parents are designed to make
children accept fundamental values of the system and behave in ways
that the system finds desirable. "Mental health" programs,
"intervention" techniques, psychotherapy and so forth are ostensibly
designed to benefit individuals, but in practice they usually serve as
methods for inducing individuals to think and behave as the system
requires. (There is no contradiction here; an individual whose
attitudes or behavior bring him into conflict with the system is up
against a force that is too powerful for him to conquer or escape
from, hence he is likely to suffer from stress, frustration, defeat.
His path will be mu