Competition problem — Combinatorics

Library / /60 of 158

Combinatorics Difficulty 5.5 AIME, harder Prove it Estonia

Some cities of a country are connected with roads. We say that a city $A$ belongs to a cycle of length $n$ if one can travel from $A$ through exactly $n-1$ other cities and return back to $A$ . It is known that each city of the country belongs to a cycle of length 4 and also to a cycle of length 5.
Is it sure that
a) at least one city belongs to a cycle of length 3?
b) each city belongs to a cycle of length 3?

Solution

Let there be 10 cities and let cities be connected as in the Fig. 19. Then every city belongs to a cycle of length 5 and also to a cycle of length 4. On the other hand, no cycles of length 3 exist.

Fig. 19

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.