Balti Tee 1992 · Ülesanne 15
Kombinatoorika
Noah has to fit 8 species of animals into 4 cages of the ark. He plans to put species in each cage. It turns out that, for each species, there are at most 3 other species with which it cannot share the accommodation. Prove that there is a way to assign the animals to their cages so that each species shares a cage with compatible species.
Kui oled valmis
Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.
Ülevaade
Teemad
Värvimised ja konfiguratsioonid · Dirichlet’ printsiip ja ekstremaalargumendid · Mängud ja strateegiad
Lahendused
Lahendus
Solution:
Start assigning the species to cages in an arbitrary order. Since for each species there are at most three species incompatible with it, we can always add it to one of the four cages.
Võistluse kontekst
Balti Tee tulemused 1992
8 võistkonda
- Keskmine tulemus
- 3,9 / 5
- 4 või 5 punkti
- 6 / 8
- Eesti
- 5 / 5
Punktijaotus
Kõigi võistkondade punktid
| Võistkond | Punktid |
|---|---|
| Denmark | 5 / 5 |
| St. Petersburg | 5 / 5 |
| Poland | 1 / 5 |
| Latvia | 5 / 5 |
| Iceland | 4 / 5 |
| Lithuania | 1 / 5 |
| Estonia | 5 / 5 |
| Sweden | 5 / 5 |