Inspired by the four color problem


As you know, the problem of four colors is solved as a result of enumeration of options on the computer. But not all mathematicians agree with this solution, since there are difficulties with checking the absence of errors.

For the uninitiated… The four-color problem is formulated very simply: “To color any card on plane four colors are enough.

In this case, if the regions (countries) “touch” only at one point, then it is considered that they do not border and they can be painted in the same color. So, for example, two colors are enough to color the cells of a chessboard.

Moreover, Martin Gardner in the book “Mathematical Puzzles and Entertainment” mentions that the “two-color map theorem” has been proved, which states that “any map on the plane can be colored in two colors if and only if all its vertices are even” ( here, the “top” is called dotwhere the borders of more than two countries meet).

* * *

Created a very uninteresting game inspired by this Problem.

Field of play

The areas are formed from squares (cells) of the original grid (56×55), from which some links have been removed, i.e. the boundaries of the regions are closed broken lines, each link of which is rotated relative to the neighboring one by an angle multiple of 90°.

If the areas have a single common point (grid node), then they are considered not bordering each other and can be painted in the same color. Since the grid is initially square, four areas can converge at one point, and then (if other borders with other areas allow) these four areas can be painted in two colors like checkerboard cells (see Fig. 1a).

It is also easy to imitate the convergence of three regions at one point, due to the fact that, in this case, each of these regions necessarily borders on two others (see Fig. 1b). Therefore, three colors are required here for proper coloring.

a) b) Fig.1
a) b) Fig.1

a) b) Fig.1

Rules of the game

  1. It is necessary to color a map in 4 colors, in which the division into regions (countries) is made randomly using a standard random number generator.

  2. The suggested colors are: red, yellow, green and cream (clCreamwhich looks almost pure white on my monitor).

  3. There is a condition that the area bordering the map is painted in cream color and, accordingly, all areas bordering the edges of the map (the perimeter of the map) must be painted strictly in three other colors.

  4. There is a timer that stops when the “Finish” button is “pressed”. After that, the correctness of the coloring is checked and if there is an error, its coordinates are indicated. Upon confirmation by the player of reading this message, the timer is turned on to continue counting the elapsed time.

  5. A list of the eleven best results is formed and stored.

*

Nuances of the Program implementation

For the existence of a solution (a method of coloring the map), the game field is formed as follows (secretly from the player).

The field is marked with a grid with square cells. Then, the color of each cell is randomly played out.

In the next step, cells of the same color that have a common border are merged by removing this common border. As a result, areas are obtained, bounded by closed broken lines and painted in 4 colors.

To ensure paragraph 3 of the Rules of the Game, first the cells around the perimeter of the map are colored in three colors and only then the inner cells are painted in four colors.

And finally, all areas are recolored clCream and the card is presented to the player.

*

The program has two modes: “Game” and “NOT Game”.

The first mode is described above. The second mode provides some opportunities for experimentation. So, you can choose the number of colors for the original coloring in the range from 2 to 18. However, the task remains the same – color in 4 colors (or fewer colors if a two-color or three-color map is selected).

A report is issued on the parameters of the created map.

There is no countdown.

The original coloring of the map is shown.

*

My observations in the “NOT Game” mode

  1. An increase in the number of coloring colors leads to a simplification of the shape of the regions, since cells of the same color are less likely to be next to each other and, accordingly, the average number of cells in the regions decreases. There are more “chessboards” that are painted in two colors.

  2. There were no problems with coloring the “five-color” card in four colors (especially if there are even more colors, then the card is easier to color).

  3. In case of erroneous coloring of any area, repainting of two or three nearby areas is usually enough to correct.

  4. Erroneous coloring that requires corrections is rare, more often there are missed “single-cell” areas (due to the large area of ​​​​the playing field).

  5. It is very common to have a choice of two colors for a particular area. That is, the probability that your coloring will coincide with the original one is practically equal to zero (except, of course, coloring in two colors, when the condition of 3 Rules of the game uniquely determines the colors of the coloring).

More about two-tone coloring

In order for the condition of parity of all vertices in the “two-color map theorem” to be satisfied, it is necessary that the map occupies the entire plane. Otherwise, it is necessary to stipulate that the color of the area “bordering” the map does not participate in the task (with its “participation”, the condition of “evenness of all vertices” is impossible). That is, it turns out that we are not considering the entire infinite plane, but only its certain finite section.

Isn’t this the difficulty of proving the Four Color Theorem?

For example, for the surface of a torus, they were able to prove that seven colors are enough to color any map. And the surface of a torus is finite…

By the way, is the assertion that “the surface of a sphere with one punctured point is topologically equivalent to a plane” justified enough? On the one hand, “pricking out” a point violates the integrity of the sphere surface, which, it seems, is unacceptable in topology. On the other hand, the surface of a sphere is finite, unlike a plane…

Accounting for the area that “surrounds” the map immediately imposes a restriction. Even if all the vertices in the map are even, then the bordering area can only be painted in the third color. And for a map whose all vertices are odd, the bordering area can only be colored in the fourth color. This can be seen in our figures (Fig. 1a and b).

*

For those who wish, I can send the source code to Delphi. Write in private.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *