Balti Tee 1993 · Ülesanne 12
Kombinatoorika
There are 13 cities in a certain kingdom. Between some pairs of cities two-way direct bus, train or plane connections are established. What is the least possible number of connections to be established in order that choosing any two means of transportation one can go from any city to any other without using the third kind of vehicle?
Kui oled valmis
Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.
Ülevaade
Teemad
Värvimised ja konfiguratsioonid · Dirichlet’ printsiip ja ekstremaalargumendid · Loendamine
Lahendused
Lahendus
Solution:
An example for 18 connections is shown in Figure 1 (where single, double and dashed lines denote the three different kinds of transportation). On the other hand, a connected graph with 13 vertices has at least 12 edges, so the total number of connections for any two kinds of vehicle is at least 12. Thus, twice the total number of all connections is at least .
Figure 1
Võistluse kontekst
Balti Tee tulemused 1993
8 võistkonda
- Keskmine tulemus
- 1,1 / 5
- 4 või 5 punkti
- 2 / 8
- Eesti
- 5 / 5
Punktijaotus
Kõigi võistkondade punktid
| Võistkond | Punktid |
|---|---|
| Poland | 0 / 5 |
| Latvia | 0 / 5 |
| Estonia | 5 / 5 |
| Sweden | 4 / 5 |
| Lithuania | 0 / 5 |
| Finland | 0 / 5 |
| Iceland | 0 / 5 |
| Denmark | 0 / 5 |