Maths Olympiad Prep

Library / /187 of 196

Combinatorics Difficulty 6.8 National Olympiad Prove it Soviet Union

Problem:
A tourist arrives in Moscow by train and wanders randomly through the streets on foot. After supper he decides to return to the station along sections of street that he has traversed an odd number of times. Prove that this is always possible. [In other words, given a path over a graph from AA to BB, find a path from BB to AA consisting of edges that are used an odd number of times in the first path.]

Solution

Solution:
Disregard all edges except those used in the path from AA to BB, and for each of those let the multiplicity be the number of times it was traversed. Let the degree of a vertex be the sum of the multiplicities of its edges. The key is to notice that the degree of every vertex except AA and BB must be even. For as we traverse the path from AA to BB we increase the degree by 22 each time we pass through a vertex. But at the start of the path, as we leave AA, we only increase its degree by 11. Similarly as we arrive at BB for the last time.

Now construct a path from BB as follows. Since BB has odd degree it must have an edge of odd multiplicity. Suppose the edge connects BB to CC. Follow that edge and reduce its multiplicity by one, so that BB's degree and CC's degree are each reduced by one. Now CC has odd degree, so it must have an edge of odd multiplicity. Repeat. Since there are only finitely many edges we must eventually be unable to continue the path. But the only way that can happen is if we reach AA.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.