Q15 Matemática  (Baltic Way 2016)

O Mar Báltico tem portos de $2016$. Há conexões de balsa de duas vias entre alguns deles. É impossível fazer uma seqüência de viagens diretas $C_1-C_2-...-C_{1062}$ onde todos os portos $C_1,...,C_{1062}$ são distintos. Prove que existem dois conjuntos disjuntos $A$ e $B$ de $477$ portos cada, de modo que não há porto em $A$ com uma conexão direta de balsa para um porto em $B.$