Maths Olympiad Prep

Library / /97 of 128

Combinatorics Difficulty 6.1 National Olympiad Prove it Philippines

Problem:

The chromatic number of the (infinite) plane, denoted by χ\chi, is the smallest number of colors with which we can color the points on the plane in such a way that no two points of the same color are one unit apart.
Prove that 4χ74 \leq \chi \leq 7.

Solution

Solution:

Suppose χ3\chi \leq 3. Consider the following configuration, where each segment has unit length. Then the points A,BA, B, and GG must receive different colors, and so are the points A,EA, E, and FF. This will force points CC and DD to receive the same color as AA, which is a contradiction. Thus, we obtain χ4\chi \geq 4.
Figure 1

On the other hand, we will exhibit a coloring of the points on the plane using 7 colors in such a way that points one unit apart have different colors. We first tile the plane by regular hexagons with unit sides. Now, we color one hexagon with color 1, and its six neighbors with colors 2,3,,72,3, \ldots, 7, as highlighted in the following diagram.
Figure 2

The union of the seven highlighted hexagons forms a symmetric polygon PP of 18 sides. Translates of PP also tile the plane and determine how we color the plane using 7 colors.

It is easy to compute that each color does not have monochromatic segments of any length dd, where 2<d<72<d<\sqrt{7}. Thus, if we proportionally shrink the configuration by a factor of, say, 2.1, we will get 7-coloring that has no monochromatic segments of unit length, which implies that χ7\chi \leq 7.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.