Kvant Math Problem 1471
The problem asks whether a skier who has passed through each of $n$ villages twice and returned to the starting point can traverse his ski track in such a way as to visit each village exactly once.
Verified: no
Verdicts: FAIL + FAIL
Solve time: 34m39s
Source on kvant.digital
Problem
A skier passed through each of the $n$ villages twice and returned to the starting point. Is it always possible to travel along his ski track in such a way as to visit each of these $n$ villages exactly once (it is not necessary to return to the starting point)?
M. L. Gerver
Corrected Solution to Kvant M1471
The problem asks whether a skier who has passed through each of $n$ villages twice and returned to the starting point can traverse his ski track in such a way as to visit each village exactly once. The skier’s route forms a closed path with every village appearing exactly twice on this path. This can be modeled combinatorially by considering the villages as vertices and the path segments between consecutive visits as edges of a graph. Each village has degree 4 if counted as undirected edges between consecutive visits because each village is entered twice and left twice along the track. The task is equivalent to finding a sequence along the edges of this 4-regular graph that passes through each vertex exactly once.
The crucial observation is that the skier’s track is a closed trail that passes through each village exactly twice, meaning that the underlying multigraph is Eulerian. The skier's path can therefore be represented as a cycle where each village appears twice. Each edge in this cycle connects consecutive appearances of villages, possibly with repeated villages in between. The problem reduces to finding a Hamiltonian path through the vertices, visiting each village once, which can be extracted from the Eulerian cycle by selecting one of the two appearances of each village and skipping the second.
Let the skier’s closed path be represented as a sequence $v_1, v_2, \dots, v_{2n}$ of village visits with $v_{2n+1} = v_1$. Each village occurs exactly twice in this sequence. Construct a new sequence $u_1, u_2, \dots, u_n$ by scanning the original path from the start and including a village the first time it appears, skipping it the second time. Because every village appears exactly twice, this procedure selects one appearance of each village without repetition, producing a sequence of length $n$. The consecutive villages in this new sequence are connected by segments of the original ski path, possibly passing through other villages temporarily, but these intermediate villages are not included in the sequence because they have already been visited. Therefore, traveling along the original ski track and following this selection yields a path that visits each village exactly once.
This construction works for any number of villages $n \ge 1$. For $n = 1$ the path is trivial, and for $n = 2$ or larger, the same selection process produces a valid Hamiltonian path along the skier’s track. The skier does not need to return to the starting point because the task only requires visiting each village once. The existence of the closed path with each village appearing twice guarantees that every village is reachable along the sequence, and the selection procedure avoids repetition. This provides an explicit construction of a traversal visiting each village exactly once along the skier’s track.
The final conclusion is that it is always possible to travel along the skier’s path in such a way as to visit each village exactly once. The selection procedure provides a deterministic and constructive method for obtaining this traversal from the original track.