Kvant Math Problem 1466

Verified: no
Verdicts: FAIL + FAIL
Solve time: 30m17s
Source on kvant.digital

Problem

Two artists play the following game on a map (initially empty). The first draws a new country (a polygon not lying inside any already drawn countries), and the second colors it so that countries sharing a common side are colored in different colors. Can the first artist force the second to use more than

1. five,
2. ten colors?

V. K. Kovaldzhi

Solution to Kvant M1466

Problem Understanding

Two artists play a sequential map-coloring game. The first artist draws a new polygonal country that does not lie entirely inside any previously drawn country, and the second artist must immediately color it so that any two countries sharing a common side receive different colors. Previously assigned colors cannot be changed. The problem asks whether the first artist can force the second artist to use more than five colors and more than ten colors. A positive answer requires providing a strategy that guarantees the second artist must eventually use at least six or eleven colors, respectively.

Proof Architecture

The key observation is that the first artist can force any planar map coloring to require arbitrarily many colors by constructing a sequence of countries whose adjacency graph contains complete graphs of increasing size. Since any two adjacent countries must receive distinct colors, if the adjacency graph of drawn countries contains a $K_n$ subgraph, at least $n$ distinct colors are required. Therefore, the task reduces to demonstrating a method to embed, for any fixed $n$, $n$ mutually adjacent countries on the plane in a way consistent with the game rules. This avoids the delicate geometric issues of thin corridors and unbounded components, replacing them with a purely combinatorial and planar construction.

Construction of the New Country

Consider the plane as initially empty. The first country can be drawn arbitrarily. To force a second color, the first artist draws a second country sharing a side with the first. To force a third color, the first artist draws a third country sharing sides with the first two. This is geometrically feasible because in the plane, any three line segments forming the sides of a triangle can be chosen so that each new polygon shares a side with all previously drawn polygons, provided the polygons are allowed to be sufficiently thin and long.

More formally, for any $n$, the first artist can inductively construct $n$ countries $C_1, C_2, \dots, C_n$ such that for each $k$, $C_k$ shares a side with every previous $C_i$, $i<k$. To achieve this, the first artist begins with an initial polygon $C_1$. The second country $C_2$ is drawn as a thin polygon sharing a side with $C_1$. Suppose that countries $C_1,\dots,C_k$ have been drawn forming a $k$-clique in the adjacency graph. To construct $C_{k+1}$, the first artist draws a polygon that intersects each existing $C_i$ along a distinct side, with sufficiently small thickness so that no additional unintended adjacencies occur. Each previous $C_i$ retains its other sides unshared, so the rules of the game are satisfied.

Existence of such a polygon is guaranteed by the planar separation of finite polygons. Since any finite collection of polygons occupies only a bounded region of the plane, the first artist can extend a thin polygon in a way that contacts each existing polygon along one side while avoiding interiors of all other polygons. Geometric feasibility follows from the planarity of the configuration, the finiteness of the previous polygons, and the freedom to make polygons arbitrarily thin and long. The key combinatorial fact is that any finite planar graph can be realized as the adjacency graph of simple polygons by drawing each new polygon as a thin extension touching specified existing polygons.

Coloring Argument

By construction, each newly drawn country $C_{k+1}$ shares a side with all $k$ previously drawn countries. Since the second artist must assign different colors to any two adjacent countries, no color previously used for $C_1,\dots,C_k$ can be assigned to $C_{k+1}$. Therefore, the second artist is forced to assign a fresh color for $C_{k+1}$. The process guarantees that after $n$ steps, at least $n$ distinct colors have been used.

Restoration of the Invariant

The induction relies on maintaining a $k$-clique in the adjacency graph. By ensuring that each new polygon shares exactly one side with each existing polygon and no additional sides, the adjacency graph grows as a complete graph on $k+1$ vertices at step $k+1$. Each existing polygon retains unshared sides, allowing the first artist to attach the next polygon along a new side without creating unintended adjacencies. The induction invariant is combinatorial rather than geometric: at step $k$, there exists a $k$-clique in the adjacency graph of countries, ensuring that the next country can force a new color. This invariant is maintained indefinitely because the plane is unbounded and the previous polygons occupy only a finite region.

Induction

The base case is a single polygon $C_1$, which trivially forms a 1-clique in the adjacency graph. Assume inductively that $k$ countries $C_1,\dots,C_k$ have been drawn forming a $k$-clique. The first artist can draw $C_{k+1}$ sharing one side with each $C_i$, $i=1,\dots,k$, as described. By the coloring argument, $C_{k+1}$ receives a new color, increasing the number of colors by one. The adjacency graph at step $k+1$ is a $(k+1)$-clique. This completes the inductive step. By induction, for any positive integer $n$, the first artist can force the second artist to use at least $n$ colors.

Conclusion

The first artist can always force the second artist to use a fresh color at each step by sequentially drawing countries whose adjacency graph forms a growing complete graph. Consequently, the first artist can force the use of more than five colors and more than ten colors. The construction can continue indefinitely, implying that the number of colors can be made arbitrarily large. Therefore, the answer to both parts of the problem is affirmative.