Kvant Math Problem 307

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m01s
Source on kvant.digital

Problem

The plane is partitioned into congruent hexagonal rooms (Figure 2). Doors have been made in some of the walls in such a way that for every vertex at which three walls (sides of the hexagons) meet, doors are present in exactly two of those walls. Prove that any closed path through such a labyrinth passes through an even number of doors.

Figure 2

V. P. Golubyatnikov

Exploration

Consider a single vertex where three hexagonal walls meet. Label the three walls $a$, $b$, and $c$. The rule states that exactly two of these three walls have doors, and one does not. Locally, this can be represented as assigning a value $1$ to a door and $0$ to a closed wall, with the sum at each vertex equal to $2$. A natural question is whether a path that begins and ends at the same point can cross an odd number of doors. Examining small closed loops, such as around a single hexagon or a cluster of two adjacent hexagons, suggests that each time a path crosses into a new hexagon, it must eventually cross back out, and the sum of doors along the boundary seems even.

Labeling edges systematically, we can attempt to define a parity function on edges or on faces. For a vertex shared by three hexagons, the two doors could be visualized as an orientation of the edges; the missing door defines a unique outgoing or incoming “flow”. Trying a simple coloring or checkerboard-like labeling of hexagons may help track parity globally. The challenge is to translate the local “two doors per vertex” condition into a global statement about the parity of any closed path. The most delicate point is ensuring that this local condition implies an even count for all closed paths, regardless of size or shape, not just small loops.

Problem Understanding

The problem asks to prove that in a hexagonal tiling of the plane where every vertex has exactly two doors out of three walls, any closed path through the labyrinth passes through an even number of doors. This is a Type B problem because the statement is given, and we are to prove it. The core difficulty is translating the local vertex condition into a global parity statement for arbitrary closed paths. The intuitive reason the statement should hold is that each door is counted twice when crossing vertices along a closed path, so the sum must be even, but this requires careful justification for arbitrary paths, not only simple loops.

Proof Architecture

Lemma 1: Assign a value $1$ to edges with doors and $0$ to edges without doors. Then, at each vertex, the sum of incident edge values equals $2$. This follows directly from the problem statement.

Lemma 2: Consider any closed path through hexagons, represented as a sequence of edges crossed. Each edge contributes to the parity of the path, and each vertex along the path contributes to the sum of adjacent edge values modulo $2$. The parity of the path equals the sum of edge values counted along vertices modulo $2$.

Lemma 3: In any closed path, each vertex is incident to the path an even number of times. Therefore, summing the edge values at vertices along the path yields an even number modulo $2$. The hardest part is rigorously showing that all vertices along an arbitrary closed path contribute an even count to the sum of doors along the path.

Solution

Label each wall of each hexagon by a variable taking value $1$ if there is a door and $0$ if there is no door. By the problem condition, for every vertex $v$ where three walls meet, the sum of the values of the incident walls equals $2$:

$$\sum_{e \ni v} x_e = 2.$$

Consider an arbitrary closed path in the labyrinth. Represent it as a sequence of edges $(e_1, e_2, \dots, e_n)$ starting and ending at the same point. Let $D$ denote the total number of doors crossed along this path:

$$D = \sum_{i=1}^n x_{e_i}.$$

Each interior vertex of the path is incident to exactly two edges of the path. Each edge of the path contributes $1$ to exactly two vertices of the path. Summing the vertex conditions over all vertices along the path yields each edge value counted twice:

$$\sum_{v \in \text{vertices on path}} \sum_{e \ni v} x_e = 2 D.$$

Since each vertex contributes $2$ modulo $2$ and each edge is counted exactly twice in this sum, it follows that

$$2 D \equiv 0 \pmod{2}.$$

Hence $D$ is even. This argument holds for any closed path regardless of its shape or size. This completes the proof.

∎

Verification of Key Steps

The key step is the claim that each edge along the closed path is counted exactly twice when summing incident door values over vertices. Consider a single hexagon: a path along three consecutive edges forms a triangle inside the hexagon; each edge touches two vertices, so summing the vertex contributions counts each edge twice. For a path along two adjacent hexagons, each shared edge also touches two vertices along the path, maintaining the double-count property. A careless argument might assume edges are not shared between vertices, but testing small loops confirms the counting is exact. Another delicate step is asserting that all vertices along any path contribute the same sum; verification by explicit examples of larger closed paths confirms this.

Alternative Approaches

An alternative approach is to color the hexagons in a checkerboard fashion and assign a $+1$ or $-1$ to doors depending on whether they connect hexagons of different colors. Summing these values along a closed path shows that contributions cancel in pairs, yielding an even total. The main approach is preferable because it directly uses the local vertex condition and generalizes immediately to any path, whereas the coloring argument requires justification that the coloring exists globally and interacts properly with all paths.