MathDB
Problems
Contests
International Contests
Baltic Way
2016 Baltic Way
15
15
Part of
2016 Baltic Way
Problems
(1)
Connections between harbours
Source: Baltic Way 2016, Problem 15
11/5/2016
The Baltic Sea has
2016
2016
2016
harbours. There are two-way ferry connections between some of them. It is impossible to make a sequence of direct voyages
C
1
−
C
2
−
.
.
.
−
C
1062
C_1 - C_2 - ... - C_{1062}
C
1
−
C
2
−
...
−
C
1062
where all the harbours
C
1
,
.
.
.
,
C
1062
C_1, . . . , C_{1062}
C
1
,
...
,
C
1062
are distinct. Prove that there exist two disjoint sets
A
A
A
and
B
B
B
of
477
477
477
harbours each, such that there is no harbour in
A
A
A
with a direct ferry connection to a harbour in
B
.
B.
B
.
combinatorics