MathDB
Connections between harbours

Source: Baltic Way 2016, Problem 15

November 5, 2016
combinatorics

Problem Statement

The Baltic Sea has 20162016 harbours. There are two-way ferry connections between some of them. It is impossible to make a sequence of direct voyages C1−C2−...−C1062C_1 - C_2 - ... - C_{1062} where all the harbours C1,...,C1062C_1, . . . , C_{1062} are distinct. Prove that there exist two disjoint sets AA and BB of 477477 harbours each, such that there is no harbour in AA with a direct ferry connection to a harbour in B.B.
Back to ProblemsView on AoPS