Balti Tee 1992 · Ülesanne 14
Kombinatoorika
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.
Kui oled valmis
Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.
Ülevaade
Teemad
Graafiteooria
Lahendused
Lahendus
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.
Võistluse kontekst
Balti Tee tulemused 1992
8 võistkonda
- Keskmine tulemus
- 3,1 / 5
- 4 või 5 punkti
- 4 / 8
- Eesti
- 3 / 5
Punktijaotus
02
10
20
32
41
53
Kõigi võistkondade punktid
| Võistkond | Punktid |
|---|---|
| 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 |