Olympiad Maths Prep

Track / Stage 6 / 355 of 400 #1355 of 2000

Problem 1355

National olympiad, first round
Combinatorics Difficulty 6.8 Prove it

In a country, there are 100 cities. Each of these cities is connected to exactly three other cities by direct two-way roads. Prove that there exists a city AA from which one can travel from city to city and return to AA, without ever using the same road twice, and using a total number of roads that is not divisible by 3 (it is not required that all cities in the country be visited during this journey).

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Since there is only a finite number of cities, we can consider a path C of maximum length. Let v0v_{0} be one of the cities at the ends of C and traverse C starting from v0v_{0}, numbering the cities as we go. The maximality of C ensures that the three cities connected to v0v_{0} by a road are in C. These are v1,νiv_{1}, \nu_{i}, and vjv_{j} with 1<i<j1<i<j. We have thus identified three cycles:

v0,v1,⋯ ,vi,v0, of length i+1,v0,v1,⋯ ,vj,v0, of length j+1v0,vi,vi+1,⋯ ,vj,v0, of length j−i+2 \begin{gathered} v_{0}, v_{1}, \cdots, v_{i}, v_{0} \text {, of length } \mathfrak{i}+1, \\ v_{0}, v 1, \cdots, v_{j}, v_{0} \text {, of length } \mathfrak{j}+1 \\ v_{0}, v_{i}, v_{i+1}, \cdots, v_{j}, v_{0}, \text { of length } \mathfrak{j}-\mathfrak{i}+2 \end{gathered}

If i+1i+1 or j+1j+1 is not divisible by 3, one of the first two cycles will do. Otherwise, it means i=j=−1 mod 3,d′\boldsymbol{i}=\mathbf{j}=-1 \bmod 3, d^{\prime} where j−i+2=2 mod 3\boldsymbol{j}-\mathfrak{i}+2=2 \bmod 3 and the third cycle allows us to conclude.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.