The Best Coloring
25 is the right answer!
Figure 34:
Consider the 31 points in the middle of the figure on the right.
of them are shown as yellow diamonds; the remainder are shown as red stars.
Proposition 1:
The distance between any two diamonds is less than 35.
|
Proposition 2:
The distance between any diamond and any star is less than 35.
|
Corollaries:
-
For any coloring of
, the 19 diamonds use 19 distinct colors.
-
For any coloring of
, the 19 diamonds use colors different from those used for the
stars.
-
If
is the number of colors needed to color the 12 stars,
the number of colors needed for coloring is at least
Equation
15
Figure 35:
The three green stars are the only points at a distance
greater than 35 from the red star. Hence, only these
points can be colored the same color as the red star. The
distance between any two of the green stars is less than
35, however. Thus any coloring of the twelve diamonds
uses any color at most twice, implying that
Therefore, the chromatic number of is 25.
|
We now know that the coloring just given is indeed a best coloring.
Using this scheme, we can drill the workpiece in only 25 passes.
Furthermore, we need only 3 different configurations of the gang drill's
bits, corresponding to each of the groups of color classes.
|