Kvant Math Problem 181
The wire must be bent into the full frame of a cube of side $10$, which is the 1-skeleton of a cube graph with $8$ vertices and $12$ edges, each of length $10$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m18s
Source on kvant.digital
Problem
What is the minimum length a piece of wire must have in order to bend it into the frame of a cube with side length 10 cm? (The wire may run along a single edge twice, be bent at $90^\circ$ and $180^\circ$, but it cannot be broken.)
Exploration
The wire must be bent into the full frame of a cube of side $10$, which is the 1-skeleton of a cube graph with $8$ vertices and $12$ edges, each of length $10$. Any valid configuration corresponds to a connected walk along edges of this graph that traverses every edge at least once, possibly repeating edges, since the wire cannot be broken but may be reused along an edge.
Thus the problem becomes a shortest walk in a graph that covers all edges, allowing repeated traversal. This is the classical edge-traversal optimization problem on a graph, where extra length arises only from repeated edges introduced to allow a continuous path.
The key difficulty is that the cube graph has all $8$ vertices of degree $3$, hence all vertices are odd. This prevents an Euler trail or circuit without repetition. Therefore some edge duplication is unavoidable, and the task is to minimize the total added length.
The central issue is how to choose repetitions optimally: either enforce a closed trail (all vertices even), or allow an open trail (exactly two vertices odd). The second option might reduce the required duplication.
Problem Understanding
This is a Type C problem, since we must find a minimum length configuration.
We model the cube frame as a graph whose edges have length $10$. We seek the shortest trail that traverses every edge at least once. The difficulty lies in choosing which edges must be retraced so that the resulting multigraph admits an Euler trail.
The total length of all edges is $12 \cdot 10 = 120$. Additional length is caused by duplicating edges along shortest paths between selected vertices. The structure of the cube suggests strong symmetry, so optimality should come from a symmetric pairing of vertices.
The final answer will be $\boxed{150\text{ cm}}$.
Proof Architecture
The argument proceeds by reducing the problem to an Euler trail augmentation problem on the cube graph.
A first lemma characterizes the problem as finding a minimum-length augmentation that produces an Euler trail, allowing either zero or two odd vertices.
A second lemma expresses the required additional length in terms of a minimum-weight matching on vertices whose parity must be corrected using shortest-path distances in the cube graph.
A third lemma identifies the cube graph as a graph where shortest-path distances coincide with Hamming distances on ${0,1}^3$ scaled by $10$.
A fourth lemma shows that allowing an open trail reduces the matching problem from $8$ vertices to an optimal choice of $6$ vertices, minimizing the cost of pairing.
A fifth lemma constructs a perfect matching of size $3$ among an optimal $6$-vertex subset using only edges of the cube.
The hardest step is proving that the $6$-vertex induced subgraph obtained by removing antipodal vertices still admits a perfect matching using only unit edges.
Solution
The cube frame is a connected graph with $8$ vertices and $12$ edges, each of length $10$. Any way of laying a single wire along all edges corresponds to a connected trail that traverses every edge at least once. If an edge is traversed more than once, its length is counted with multiplicity.
The total length of all edges is
$$12 \cdot 10 = 120.$$
The only reason to exceed this length is the necessity of repeating some edges to allow a single continuous trail. This is a classical Euler-trail obstruction problem. A trail exists without repetition if and only if the graph has exactly $0$ or $2$ vertices of odd degree. In the cube graph every vertex has degree $3$, hence all $8$ vertices are odd.
To correct this, some vertices must have their parity changed by duplicating paths between them. Each duplication along a shortest path adds length equal to the graph distance between the chosen vertices.
The cube graph can be identified with the graph on binary strings of length $3$, where edges connect vertices differing in exactly one coordinate. Thus the shortest-path distance between two vertices is the Hamming distance multiplied by $10$.
To obtain an Euler trail, it is sufficient to choose two vertices to remain odd (the endpoints of the trail) and pair the remaining $6$ vertices so that each pair is connected by duplicated paths. Each pair contributes a cost equal to the shortest-path distance between its endpoints.
Let the two chosen endpoints be opposite vertices of the cube, for instance $000$ and $111$. The remaining vertices are
$$001,010,011,100,101,110.$$
We now show that these six vertices admit a perfect matching using only edges of the cube, hence each pair contributes cost $10$.
The following pairing satisfies adjacency in the cube graph:
$$(011,010), \quad (001,101), \quad (100,110).$$
Each pair differs in exactly one coordinate, hence corresponds to a cube edge. This produces a perfect matching of the six vertices using three edges.
Each matched pair contributes an additional length $10$, so the total added length is
$$3 \cdot 10 = 30.$$
Therefore the total length of the wire in this configuration is
$$120 + 30 = 150.$$
It remains to show optimality. Any Euler trail on a graph uses a set of duplicated paths that pair exactly $6$ vertices when two endpoints are fixed. Such a pairing consists of $3$ pairs, and each pair has length at least $10$ because any two distinct vertices in the cube are at distance at least $10$. Hence no configuration can require less than $3 \cdot 10 = 30$ additional length once only two vertices are allowed to remain odd.
Thus $150$ is minimal.
This completes the proof.
∎
Verification of Key Steps
The critical step is the existence of a perfect matching on the six-vertex subgraph obtained by removing $000$ and $111$. This is verified explicitly by checking adjacency: $011$ is adjacent to $010$, $001$ is adjacent to $101$, and $100$ is adjacent to $110$, so all vertices are covered exactly once by valid cube edges.
The second delicate point is the lower bound on additional length. Since any valid augmentation with two endpoints must pair the remaining six vertices, exactly three pairs are required. Each pair corresponds to a path of length at least $10$, since the cube graph has edge length $10$ and all pairs consist of distinct vertices. Therefore no configuration can reduce the additional cost below $30$.
The final structural check is that choosing opposite vertices as endpoints is consistent with the Euler-trail condition after duplication, since exactly two vertices remain of odd degree.
Alternative Approaches
A different approach is to consider the full Chinese postman problem on the cube graph and compute a minimum-weight perfect matching on all $8$ vertices. This yields $4$ pairs and cost $40$, giving $160$, but this corresponds to forcing a closed trail.
Allowing an open trail reduces the matching problem by selecting optimal endpoints in advance, effectively removing one pair from the parity correction. This refinement is what reduces the cost from $160$ to $150$, and it makes the open-trail formulation strictly better than the closed one.