Baltic Way 1992 · Problem 15
Combinatorics
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.
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Colorings and configurations · Pigeonhole and extremal arguments · Games and strategies
Solutions
Solution
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.
Contest context
Results from Baltic Way 1992
8 teams
- Mean score
- 3.9 / 5
- Scores of 4 or 5
- 6 / 8
- Estonia
- 5 / 5
Score distribution
00
12
20
30
41
55
All team scores
| Team | Score |
|---|---|
| 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 |