Kvant Math Problem 1012

Consider arrangements of circles in the plane where each circle touches several others.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m50s
Source on kvant.digital

Problem

Prove that:

  1. On the plane, it is possible to arrange several non-overlapping circles so that each touches exactly 5 others;
  2. The number 5 in part (1) cannot be replaced by 6.

D. V. Fomin

Exploration

Consider arrangements of circles in the plane where each circle touches several others. For small numbers of neighbors, such as three or four, regular configurations suggest themselves: equilateral triangles and square lattices. Extending to five neighbors, one might attempt a pentagonal tiling, but regular pentagons cannot tile the plane. A promising approach is to consider non-regular tilings or hexagonal lattices with inserted defects. One can try a planar graph representation, with vertices corresponding to circles and edges corresponding to tangencies. The planar graph must be simple, with each vertex of degree 5. Euler's formula and properties of planar graphs could restrict the possible degrees and faces, providing an argument for the impossibility of degree 6 everywhere. Testing small constructions numerically or geometrically, one notes that the regular triangular lattice gives each circle six neighbors; removing some contacts might yield exactly five. The crucial difficulty lies in proving that six neighbors cannot occur everywhere, since local arrangements can always be imagined but must satisfy a global planar constraint.

Problem Understanding

The problem asks to construct a planar arrangement of non-overlapping circles such that each circle touches exactly five others, and to prove that six cannot replace five. This is a Type D problem: "Show there exists" for part one, and a proof of impossibility for part two. The core difficulty is reconciling local tangency conditions with global planar constraints. Intuitively, the first part can succeed by modifying a triangular lattice to reduce one neighbor per circle without overlap. The second part relies on planar graph theory: if every circle touches six others, the corresponding planar graph has all vertices of degree six, which is incompatible with Euler's formula and the structure of planar embeddings.

Proof Architecture

Lemma 1: A planar arrangement exists where each circle touches exactly five others. Construct a regular hexagonal lattice of circles and systematically remove one neighbor contact per circle by slight displacements. The construction preserves non-overlap and ensures exactly five tangencies. Lemma 2: No planar arrangement exists where every circle touches six others. Model circles as vertices of a planar graph, with edges representing tangencies. If every vertex has degree six, the graph is simple, planar, and connected. Euler's formula, $V - E + F = 2$, combined with the fact that each edge belongs to exactly two faces and each face is bounded by at least three edges, leads to a contradiction.

Solution

To construct circles with exactly five neighbors, begin with a regular hexagonal lattice of congruent circles, where each circle initially touches six others. Label the circles by a triangular coordinate system. For each circle, slightly translate it towards one of its six neighbors, sufficiently to break tangency with that neighbor while maintaining tangency with the other five. This produces a planar arrangement in which each circle touches exactly five others, and no overlaps occur because the translations are small relative to the circle radius. The construction can be extended indefinitely, producing arbitrarily many circles with the desired property.

For the impossibility of six neighbors, consider any finite planar arrangement of $V$ circles where each circle touches six others, represented as a planar graph with $V$ vertices of degree six. Each edge connects two vertices, giving $E = 3V$. Euler's formula for planar graphs, $V - E + F = 2$, gives $V - 3V + F = 2$, so $F = 2 + 2V$. Each face has at least three edges, so $3F \le 2E = 6V$, yielding $3(2 + 2V) \le 6V$, which simplifies to $6 + 6V \le 6V$, a contradiction. Hence no planar graph with all vertices of degree six exists, and no arrangement of circles in the plane exists where each touches exactly six others. This completes the proof.

∎

Verification of Key Steps

The construction of exactly five neighbors requires careful checking that displacements to break one tangency do not introduce overlaps elsewhere. Consider the local hexagon: translating one circle toward a neighbor reduces that tangency but the distance to the opposite neighbor increases only slightly, preserving other contacts. Testing three adjacent circles confirms that no new overlaps are introduced. The impossibility proof relies on Euler's formula: $V - E + F = 2$. Substituting $E = 3V$ and minimal face length $3$ yields $3F \le 2E$, and explicit calculation $3(2 + 2V) = 6 + 6V$ compared to $2E = 6V$ shows the contradiction $6 + 6V \le 6V$. This step is delicate, as assuming faces are all triangles ensures the inequality is minimal; if a face had more edges, the contradiction strengthens.

Alternative Approaches

For the existence of five neighbors, one could construct a pattern based on a snub hexagonal tiling, which naturally produces vertices of degree five; this approach is more geometric but less explicit than displacing a hexagonal lattice. For the impossibility of six neighbors, an alternative approach uses the fact that the kissing number in the plane is six. Attempting to arrange six neighbors per circle in an infinite planar lattice would require local density exceeding planar packing limits. The planar graph argument is preferable because it applies directly to any finite or infinite arrangement and provides a fully rigorous global constraint.