Baltic Way 1992 · Problem 14
Combinatorics
There is a finite number of towns in a country. They are connected by one direction roads. It is known that, for any two towns, one of them can be reached from the other one. Prove that there is a town such that all the remaining towns can be reached from it.
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Graph theory
Solutions
Solution
Solution:
Consider a town from which a maximal number of towns can be reached. Suppose there is a town which cannot be reached from . Then can be reached from and so one can reach more towns from than from , a contradiction.
Contest context
Results from Baltic Way 1992
8 teams
- Mean score
- 3.1 / 5
- Scores of 4 or 5
- 4 / 8
- Estonia
- 3 / 5
Score distribution
02
10
20
32
41
53
All team scores
| Team | Score |
|---|---|
| Denmark | 4 / 5 |
| St. Petersburg | 5 / 5 |
| Poland | 3 / 5 |
| Latvia | 5 / 5 |
| Iceland | 5 / 5 |
| Lithuania | 0 / 5 |
| Estonia | 3 / 5 |
| Sweden | 0 / 5 |