Problem

Source: Norwegian Mathematical Olympiad 1994 - Abel Competition p4b

Tags: combinatorics



Finitely many cities are connected by one-way roads. For any two cities it is possible to come from one of them to the other (with possible transfers), but not necessarily both ways. Prove that there is a city which can be reached from any other city, and that there is a city from which any other city can be reached.