Color every point of the plane with one of N colors so that no two points at distance 1 from one another have the same color.

1.  The easy ones
-----------------

It is not possible with N = 3.  Take a point A, assume it is red.
Take a point B at distance sqrt(3) from A.  Build two equilateral
triangles with side 1 between A and B:

         A
         .
       /   \
    C .-----. D
       \   /
         .
         B

Because A and C are 1 unit apart, they must have different colors.
Assume C is blue.  Then D is at distance 1 from A and from C.  It must
be green.

C is blue and D is green and B is at distance 1 from each.  Thus B
must be red.

We have just proved that all points at distance sqrt(3) from A must be
red.  This is a red circle.  Take two points on this circle at
distance 1 from one another.  They are both red.

It is easy with N = 9.

Let us number the colors from 1 to 9 because I don't want to come up
with names.  We cover the plane with squares of side 0.7.  The
diagonal of these squares is just under 1, so we can color each square
with one color.  Color the squares with this scheme:

   1 2 3 1 2 3 ...
   4 5 6 4 5 6 ...
   7 8 9 7 8 9 ...
   1 2 3 1 2 3 ...

Two squares of the same color are at least 1.4 unit apart.  Two points
of the same color are either in the same square, thus at distance < 1,
or in different squares, thus at distance > 1.

2.  Solution with N = 8
-----------------------

We cover the plane with squares of side sqrt(2).  We have to be
careful with the corners because they are exactly 1 unit apart.  Our
square will contain its southwest corner but no other.  This way, we
can color a square with one color.  Use this scheme:

   1 2 3 4 1 2 3 4 ...
   5 6 7 8 5 6 7 8 ...
   3 4 1 2 3 4 1 2 ...
   7 8 5 6 7 8 5 6 ...
   1 2 3 4 1 2 3 4 ...

Here, the minimum distance between two squares of the same color is
exactly 1 unit, but only one of the squares contains the corresponding
corner.

[ Editor: as written this cannot work: a square of side sqrt(2) has
diagonal 2, so two points of one square can be 1 apart.  The side
was presumably meant to be sqrt(2)/2, whose diagonal is exactly 1. ]

3.  Solution with N = 7
-----------------------

Let us use hexagons for a change.  Hexagons with side just under 0.5.
For example, 0.49.  The maximum distance between two points of an
hexagon is 0.98.  We can cover the plane with such hexagons,
coloring them with the following pattern, assuming the hexagons have
this orientation:

     / \
    |   |
     \ /

This is the pattern:

  1 2 3 4 5 6 7 1 2 3 4 5 6 7
       1 2 3 4 5 6 7 1 2 3 4 5 6 7
  3 4 5 6 7 1 2 3 4 5 6 7
   1 2 3 4 5 6 7 1 2 3 4 5 6 7

Here, the distance between two hexagons of the same color is a little
bit more than 0.98 * (sqrt(7) - 1).  This is comfortably more than 1.

We can use the same pattern with squares (of side 0.7, for example),
by shifting half of the rows of squares by sqrt(2)/2.  The distance is
a bit smaller than for hexagons, but it is still more than 1.

4.  Future work
---------------

The problem is still open for N = 4, 5, and 6.

Maybe it would be a good idea to look into fractal partitions of the
plane.

How about n-dimensional space, with n > 2 ?

-- Damien Doligez <Damien.Doligez@inria.fr>  (April 1995)

[ Editor: later in 1995, in a thread that confused this problem with
the four color map problem: ]

Sorry if this has been pointed out already.  The problem of coloring
the points in the real plane is not the same as "The Four Color
Problem."

Coloring points in the real plane:  Assign a color to each point in
the plane so that no two points that are distance one apart get the
same color.  How many colors do you need?  The minimum number of
colors needed is at least four and at most seven.  These bounds are
credited to Edward Nelson and John Isbell, respectively.  Nelson is
credited with inventing the problem (see Alexander Soifer's
"Chromatic Number of the Plane: A Historical Essay" in GEOMBINATORICS,
Volume I, Issue 3 (1991)).  This is not the same as coloring planar
graphs, the following is.

The Four Color Problem:  This is the famous problem of coloring maps
with four colors.  As others have mentioned, this has been solved, but
all proofs use a computer to check a large number of cases.

-- Paul O'Donnell <odonnell@math.rutgers.edu>