Page 106 - NUMINO Challenge_D2
P. 106
Basic Concepts Four Color Theorem
The Four Color Theorem states that no more than four colors are required to
color the regions of a map such that no adjacent regions have the same
color. This was first proposed when Francis Guthrie noticed that only four
different colors were needed to color the map of countries in England. Stan
Wagon disagreed with a joke Martin Gardner made on April Fool’s Day about
the problem of four colors.
Gardner: You need five colors Wagon: Four colors are enough
to distinguish the to distinguish the parts!
parts in this picture!
Example The adjacent circles connected by lines on the right need to be
colored differently. At least how many colors are needed?
Class Notes 1 D
2
Let 1, 2, and 3 be different colors of paint. Since the adjacent
circle to A is colored with paint 2, circle A needs to be colored A
with a paint other than paint 1. Since circle A is not adjacent to
the circle colored with paint 1, color it with paint .
BC
Write the paint colors for circles B, C, and D in order such that the least number of paints is
used by following the method above. , circle D - paint .
circle B - paint , circle C - paint
Since the adjacent circles to circle E are colored with paint 1 and paint , you need to
color it with paint 3.
Therefore, you need at least colors to paint all the adjacent circles with different
colors.
103Number of Outcomes
The Four Color Theorem states that no more than four colors are required to
color the regions of a map such that no adjacent regions have the same
color. This was first proposed when Francis Guthrie noticed that only four
different colors were needed to color the map of countries in England. Stan
Wagon disagreed with a joke Martin Gardner made on April Fool’s Day about
the problem of four colors.
Gardner: You need five colors Wagon: Four colors are enough
to distinguish the to distinguish the parts!
parts in this picture!
Example The adjacent circles connected by lines on the right need to be
colored differently. At least how many colors are needed?
Class Notes 1 D
2
Let 1, 2, and 3 be different colors of paint. Since the adjacent
circle to A is colored with paint 2, circle A needs to be colored A
with a paint other than paint 1. Since circle A is not adjacent to
the circle colored with paint 1, color it with paint .
BC
Write the paint colors for circles B, C, and D in order such that the least number of paints is
used by following the method above. , circle D - paint .
circle B - paint , circle C - paint
Since the adjacent circles to circle E are colored with paint 1 and paint , you need to
color it with paint 3.
Therefore, you need at least colors to paint all the adjacent circles with different
colors.
103Number of Outcomes
