Conference rusure::math

I think the equichordal problem can be disposed of by the following argument:

Assume there exist two equichordal points P and Q in a convex plane region.
The perpindicular bisector of PQ intersects the curve at two points R, R'.
For either R or R', construct two sequences of chords: R-P-P1, P1-Q-Q2, Q2-P-P3,
... Pm-Q-Qm', Qm'-P-Pm'' and R-Q-Q1, Q1-P-P2, ..., Qm-P-Pm', Pm'-Q-Qm''
where m and m'' are even and m' is odd. These two sequences converge to the
chord through PQ; but in one sequence the p-segments are getting shorter
while in the other the q-segments are getting shorter - in other words, they
are converging to a discontinuity. This contradicts the assumption of convexity
and proves that only one such point can exist.

This argument is not at all rigorous and may have to be shored up a bit.
Additional strength may be added to the argument by showing that even if,
for one R the sequences converged nicely to the same place on both sides
of P and Q, the convergence would fail for R'. I haven't worked out the details.

Lynn Yarbrough

There are two errors in your proof:

(i) The sequence of chords so sonstructed may not converge.
     Or if they do converge, they may not converge on the line
     through PQ.

(ii) The two lengths (chords through P and chords through Q) are
     the same; so even if the sequences both converge to line PQ,
     there is no discontinuity.

-----------------------
I should point out again that this problem is a well-known long-standing
unsolved problem in geometry.  Many famous geometers have worked on it
for many years.  While it may be possible for amateurs, such as us,
to crack the problem, it will certainly not be via a trivial sort of
proof.

Lest I sound too cynical, let me state that I believe there \are/
unsolved problems that we "amateurs" can solve; especially since
we have a lot more compute power available to us than the old masters had.

But I doubt if we'll solve the equichordal problem - it's just too
famous and has been worked on by too many giants.

Anyhow, here is a thought on one of the other problems which I hope
might interest someone out there who has access to a VAXSTATION or
microvax with a good display:

Consider the problem about the n circles.  One could write a program
that lets you draw n circles on your screen.  Then the lines joining
the centers are drawn in; they represent inelastics bands preventing
any two circles from moving further apart.   Then, the user, with
a light pen or a mouse sits and strategically moves the circles around
(with the program preventing him from stretching the bands).  As you
move a circle around, the program will report on the area of the union
of the circles.  You can keep moving the circles and hope to come
up with a counterexample, i.e. a case where the area increases from
its original value.  [Note that the theorem has been proven for 2 and
3 circles, so you will need at least 4.]

The hard part will be writing an algorithm for quickly finding the
area of the union of the circles.  I can't think of a good method
at the moment.  Perhaps if the hardware lets you shade in the circles,
you could then (somehow) count the total number of pixels that got
turned on; this would be a close approximation to the desired area.
Or some sort of approximatin technique involving inscribed squares.
Or for the case of 4 circles, you could use an exact formula for
the area.

	Anyone interested in writing this program?

re .2;
(i) Assume PQ is horizontal with R below (without loss of generality).
Consider R-P-P1 and P1-Q-Q2; Clearly Q2 is nearer PQ than is R, and the same
is true of succeeding points in this sequence (and, by symmetry, in the
other sequence as well). So P1-Q-Q2 is more nearly horizontal than R-P-P1,
and all succeeding lines in this sequence are more nearly horizontal. Since
all go through either P or Q, they converge to the chord through PQ.

(ii) Is harder to deal with. Next installment...

> Assume PQ is horizontal with R below (without loss of generality).
> Consider R-P-P1 and P1-Q-Q2; Clearly Q2 is nearer PQ than is R.

It's not clear to me.  If you have such a diagram (with Q2 nearer PQ than
is R), relabel the points: Q2 <=> R, P <=> Q, and you'll find that the
above construction is still valid, but that R is now nearer PQ than is Q2.
Somehow the generality was lost.

No, the relabeling is not possible because R was defined as being on the
perpindicular bisector of PQ (and on the circumference).

I agree with Peter.

The sequence of chords you are drawing do NOT necessarily
converge to PQ.  They may in fact get in to a loop.
They certainly need not get closer to PQ as you claim.
If you want to claim that, give a proof (which you won't be
able to do since I have a picture of a case where the chord
moves further away from PQ).

Here are my thoughts on the union-of-circles problem.  I'm assuming the Pj
are disjoint and the problem as stated seems to imply that the disks are all
of the same radius, r, as opposed to being just pairwise congruent.

To try to find a counterexample one could be less ambitious than Stan suggested 
and define a plane, say 200 x 200, and place maybe 5 points there (more than r
units from any edge).  Then for every x := 1 to 200 for every y := 1 to 200 
if the distance from any Pj to (x,y) is less than r, we count the point as
part of the "area".  This is essentially the algorithm Stan described in .3
except it requires no special hardware to implement, and isn't terribly fast.

My suspicion is that interactive tweaking isn't going to get you anywhere --
there are maybe 4 or 5 boundary cases where one might see an area increase.
Perhaps it would be less effort to check things out in a simpler manner.

All of which is my way of saying I think the conjecture is true.  One way
to attempt a direct proof is to take the Pj and Qj as given and note that
for "small enough r" the theorem is clearly true, there being no overlap.
Then, ahhhh, show that as r increases the Q-disks overlap more than the
P-disks ... easy to see, hard to prove rigorously.

  John

Yes, the disks are all of the same radius.  That is exactly
the same thing as saying they are pairwise congruent.

I think most mathematicians believe the conjecture to be true.

On the other hand, to attempt to find a counterexample, the
computer could try moving one circle a small distance epsilon
in each of 360 degrees and then pick the one move that
seems most likely in some sense (like decreases the area the least)
and then reiterate.  One might converge on a counterexample!

>If all the points of the plane are painted so that no two points
>at unit distance apart receive the same color, what is the
>minimum number, c, of colors that can be used?
>
>	It is known that 3 < c < 8.

Doesn't this depend on what shape we assume for points ?  Given a
chosen shape, I assume the definition of "unit distance" is whatever
distance any two points that are as close as possible are.

Here's a possible close-up of some of the points on a plane:

--- --- --- --- --- ---
\1/ \1/ \1/ \1/ \1/ \1/
2V 2 V 2 V 2 V 2 V 2 V
- --- --- --- --- --- -
/ \1/ \1/ \1/ \1/ \1/ \1/
 2 V 2 V 2 V 2 V 2 V 2 V
--- --- --- --- --- ---

As this closeup clearly shows, points are triangular, and arranged in the
plane such that only two colors, labeled "1" and "2" are needed to paint
the plane.

/Eric

These are mathematical points.  According to Euclid, who knew them well,
they have no length or thickness.

If they have no length or thickness, how the heck are we going to "paint"
them ?  I'm not trying to be difficult, but all painting and coloring problems
I've ever seen involve non-zero areas with defined shapes, or at least defined
adjacencies.  So what does it mean to paint a no-length no-thickness point?

/Eric

[This is not a map coloring problem.]

Let n be a positive integer.
Assign to each point in the plane a number in the range {1,2,...,n}.
Make sure that no two points in the plane that are a unit distance apart
get assigned the same number.

What is the smallest value of n for which this is possible?

It has been proven possible for n=7.

It is not possible for n=2:

Proof: Consider an equilateral triangle ABC of unit side.
Let A be colored with color 1 (red).  Then since B and C are
both a unit distance from A, they must be colored with the other
color, color 2 (blue).  Thus B and C are both colored with the same
color, a contradiction.

Is it possible for such a coloring to exist with n=3?
(The answer is no. This has been proven.)

It is not known if such a coloring is possible for n=4.

[This is a problem in combinatorial geometry.]

Maybe this will help with the point-coloring problem:

	Let S be a set of colors.

	Let f be a function from the points on the plane to the set S, i.e.,
		for every point A, f(A) is some element of S.

	Further, let f be defined so that

		if AB (the length of line AB) is equal to 1, then
			f(A) <> f(B).

	If the cardinality of S is n, what is the smallest n for which such a
		function exists?

This is how I interpreted the problem, is it correct?


				-- edp

>Let n be a positive integer.
>Assign to each point in the plane a number in the range {1,2,...,n}.
>Make sure that no two points in the plane that are a unit distance apart
>get assigned the same number.
>
>What is the smallest value of n for which this is possible?

I'm starting to feel that my problem is with "unit distance".  I was envisioning
points on the plane as being "next to each other" and that any two points
that are "next to each other" are a "unit distance" apart.

Hence I was concerned with whether points were triangular-shaped, or
square or whatever.  If square, then we could obviously checkerboard the
plane with just two colors.

Now I'm starting to believe you mean some actual longer distance.  For instance,
for your triangle example, unit distance might be three inches.  I can easily
see that if the "ABC" in triangle ABC represent the straight edges, not the
sharp corners, then we need three colors to paint them so that we can tell
exactly where the corner is.

Certainly, no more than three points in a plane can be equidistant from
each other (is this easily provable?).  So the original problem is to
do something with this.  (gee, if I only knew what VNOTES command would
allow me to view the original problem in the "other" window, instead
of the specific text to which I'm replying)

I'll think about all of this some more.  The first thing I need to think
about is the fact that you are talking somehow about painting the three
CORNERS of triangle ABC, not the three striaght edges, and what that means.

Also, I need to think about whether just considering all positioning of
three-inch triangles is enough, or if I need to consider two-inch ones
and one-inch ones and . . .

thanks for listening (sure am glad we're not wasting real live trees with
this dribble)

/eric

How about this:

	Consider the plane with x and y axes.  The points to be colored are
	all the points in the form (a, b), where a and b are real numbers.
	Thus, you must color (3, 4), and (3.2, 9.6) and (pi+3, 1/3), and all
	of the other points.

	There are infinitely many points in a finite area.

	Points (a, b) and (c, d) are a unit distance apart iff

		(a-c)^2 + (b-d)^2 = 1^2.

	This is an arbitrary unit.  If you wish, you can label it an inch, or
	a meter, or whatever.

	It is not possible to actually color a plane like this; mathematicians
	call it a coloring because it is like other things that they have
	colored.  Imagine pixels in a color monitor, only infinitely smaller.

As for having more than three points at equal distance apart, just put the
center of a compass on one point, put the pencil on another part, and draw a
circle.  Repeat this for the other two points.  If all three circles were to
intersect at a point, this point would be the same distance from each of the
other points as they are from each other.  However, no such intersection
exists.  But this does not solve the problem, because there are infinitely
many chains of points a unit distance apart.  For example, you could go from
A to B to C to D to E to A, which each of the adjacent points are a unit
distance apart, but A is not necessarily one unit away from C.  This chain
requires three colors (try it), even though there does not have to be
an equilateral triangle made up from points in it.


				-- edp

Two points A and B in the plane are said to be a unit distance apart
if the distance from A to B is 1.  That is, d(AB)=1.

For example, the point (5,7) is one unit away from (5,8).

Eric: You keep thinking of this as a map coloring problem. It is not.

Perhaps it would help you if we express the problem in terms of
graph theory.

Construct an infinite graph, G, as follows:

The nodes of G are just the points in the Euclidean plane.  That is,
the set of all ordered pairs, (x,y), with x and y real numbers.

The arcs of G are defined as follows: Two nodes of G, A and B are
connected by an arc if and only if the distance between the
two corresponding points in the plane is exactly 1.
We are now asking for the chromatic number of this graph.

This means: we want to find the smallest value of n such that
the nodes of the graph can be colored with n colors such that
two nodes of the same color are never adjacent.  [Two nodes
are said to be adjacent if they have an arc joining them.]

We are "coloring" nodes in a graph, not figures in the plane.

Having rephrased the problem from geometry to graph theory, we can now
once again rephrase the problem into Analysis using no geometry at all.

     2
Let R  be the set of all ordered pairs of real numbers.
Let I[n] be the set of integers {1,2,3,...,n} where n is some integer.

Find the smallest positive integer n such that there exists a function, f,

         2
mapping R  into I[n] with the property that

                    2	           2
	   (x  - x )   +  (y  - y )  = 1
	     2    1	    2    1

implies that f(x ,y ) is not equal to f(x ,y ).
                1  1                     2  2

THERE ARE NO DOTS, TRIANGLES, LINE SEGMENTS, or PAINT INVOLVED.

O.K.  I believe I see it now.  The term "unit distance" really seems to mean
the number 1 !  It doesn't mean "next to each other".  Nor does it mean
"any set of three equidistant points" are of different colors.

As a slightly different phrasing:  "Assign a color to every point of the
plane such that a 1-1-1 equilateral triangle's corners always touch points
of three different colors no matter where we position the triangle".  right?

Once a plane is so colored, we will probably not be able to slide around
other-sized triangles and still guarantee different colors at the corners,
so the number "1" seems critical.

No.

... so that if slide around a unit line segment, the endpoints
always touch points of a different color.

Actually, I believe the equilateral triangle statement is equivalent to
the line segment statement.


				-- edp

I'm still a bit worried about "unit distance".  On one hand, it sounds like
the properly colored plane would guarantee that a "unit distance" line segment
would always have its endpoints on different-colored points, but that other
lengths of line segment might be positionable such that their endpoints are
on identical colors.

On the other hand, since we haven't defined what units we're working in,
"unit distance" could mean ANY length of segment.  This second hand suggests
that an infinite number of colors are needed, lest some jokester find two
points of the same color, measure their distance, call that a "unit distance",
and suddenly the plane is improperly colored.

hmmm . . .

/eric

Unit distance means 1.  The first natural number.  The successor to 0.
The predecessor to 2.  There is only one number 1.

Re .22:

Actually, I was wondering whether one case implied the other, but
was NOT equivalent (one statement was stronger than the other).

The answer would seem to be easy, but I haven't taken the time to think it out.

Re .24:

Since the distances in this problem are reals, not integers, your
remark hath lost its sting.
				/AHM

For a coloring of the points in a plane, the following properties are
equivalent:

P1: Any two points with unit distance have different colors.
P2: The vertices of any unit equilateral triangle are of 3 different colors.

P2 implies P1, just by omitting one vertex of the triangle.  P1 implies P2,
by construction of any unit equilateral triangle from unit segments.

re: .0

"Is every polygonal plane region illuminable from at least one of its points?"

To understand what is being asked, consider the edges of the polygon to be
mirrors.  Then, the question is whether a point source of light somewhere
in the polygon can illuminate all points in the polygon.  

In the case of closed curves in the plane, the answer is "no".  It seems
reasonable to suppose that the answer for polygons is also "no".

There is a major difference between a polygonal boundary and an arbitrary
closed curve: a polygon always disperses light by reflection, while a curved
boundary may focus it. That is what makes the 'illumination' problem so 
difficult - to demonstrate the existence of a polygon with 'dark corners'
one has to ray-trace the infinity of lines emanating from the source. With
a curved boundary one can argue that all the rays in some region have a
common focus, but that argument fails for polygonal boundaries.

Re: .23

You are using "unit" in two different ways. We regard the plane as
dimensionless in the physical sense.

In fact, it does not matter which unit you pick as long as it remains
fixed. If you pick length = a^2, say, a coloring which is valid for
length = 1 will work for a^2 under the mapping:

	x->ax
	y->ay

If the unit is allowed to vary, clearly you need an infinite number
of colors. (Question: Are there an infinite number of colors or only
a discrete set of physically realizable wavelengths?)

-cjc

I was wondering...

When old college budies get together and imbibe libations, the wierdest
discussions come about.

Isn't there an old unsolvable problem about trisecting an angle?  I remember
something about:

	"with nothing more than a straight edge and a compass, 
	try to divide an angle into three equal angles."

Well, last night the answer seemed trivial.  ( draw a line accross two points
on the angle equidistant from where the angle begins, then trisect the line )

Do I have the question wrong? or do I have the answer wrong?

James N. Friedman
          c
        /
     d1/                    angle cab
      / \
     /   \                  d1 & d2 are found by drawing an arc and
    /     \                 intersecting line ac and line ab
   /       \
  /         \
 /           \
/-------------\------------
a            d2           b

    ... now all you have to do is prove that the ANGLE is trisected by this
    methodology.  It's up to YOU to make the demonstration, using Euclid's
    postulates and derived theorems.

    The best way I've seen this put is that trying to trisect a general
    angle with straightedge and compass is like trying to prove that 2+2 = 5...
 
    It was only in the 19'th century that this old problem was finally
    settled though.  (It and some others like squaring the circle, duplicating
    the cube, etc have been subsumed under the subject of Galois theory.)

    - Jim

    Re .30:
    
    When you trisect the line to make three angles, the angle in the center
    is slightly larger than the other two angles. 
    
    
    				-- edp

    RE .30
    
    .33 is correct about the angle in the middle being greater.  The
    best example of this is to try your method on an angle of exactly
    180 degrees.  This show the resulting difference obviously, you'll
    come up with three angles of 0, 180, and 0 degrees.
    
    -Joe
    
    

For what it's worth, the proof of the bounds cited is easy.

To show 7 colors suffice, tesselate the plane with hexagons whose size is just
less than the size of a hexagon inscribed in a unit circle.  Color them with
numbers in 0..6 such that moving east adds +1 mod 7, northwestish +2, and
therefore northeastish +3.  (The point is that no hexagon only two hops away is
the same color as the hexagon you start from.)

To show 3 colors don't suffice, assume the contrary.  Now in any equilateral
triangle with unit edge, the vertices are 3 different colors; so if we join two
such triangles to make a diamond, the two furthest-apart points of the diamond
are the same color:

                   ---- Q
                  /\  /
                 /  \/
                 ----
                P

So any two points a distance sqrt(3) apart are the same color; considering a
circle of radius sqrt(3) we now find two points a distance 1 apart of the same
color, a contradiction.