One-Way Highways Puzzle: The Town Reachable from All Others

Μια παράξενη χώρα και οι μονόδρομοι: Υπάρχει «κεντρική» πόλη;

Σε μια παράξενη χώρα ισχύει ο εξής νόμος για τους αυτοκινητόδρομους:

Ανάμεσα σε κάθε ζεύγος πόλεων πρέπει να υπάρχει ένας αυτοκινητόδρομος μονής κατεύθυνσης: από τη μία πόλη προς την άλλη, αλλά ποτέ και προς τις δύο κατευθύνσεις.

Δηλαδή, για κάθε δύο πόλεις A και B, υπάρχει είτε δρόμος από την A προς τη B είτε από τη B προς την A, αλλά όχι και τα δύο.

Ζητείται να αποδείξετε ότι:

Υπάρχει τουλάχιστον μία πόλη της χώρας, στην οποία μπορεί κανείς να φτάσει από κάθε άλλη πόλη είτε

• με άμεσο αυτοκινητόδρομο, ή
• με διαδρομή που περνάει από ακριβώς μία ενδιάμεση πόλη.

Με άλλα λόγια, υπάρχει μια πόλη που είναι προσβάσιμη από κάθε άλλη με διαδρομή μήκους το πολύ δύο (δηλαδή με μία ή δύο κινήσεις κατά μήκος των μονόδρομων αυτοκινητοδρόμων).

A Strange Country of One-Way Roads: Is There a “Central” Town?

In a strange country, the highway system follows this rule:

Between every pair of towns there is exactly one one-way highway: from one town to the other, but never in both directions.

In other words, for any two towns A and B, there is either a road from A to B or from B to A, but not both.

Task – Prove that:

There exists at least one town in this country that can be reached from any other town either

• by a direct highway, or
• by a route that passes through exactly one intermediate town.

In other words, there is a town that is reachable from every other town by a path of length at most two (that is, in one or two one-way steps).