Q11 Matemática  (Balkan MO Shortlist 2007)

Três empresas de viagens fornecem transporte entre $n$ cidades, de modo que cada conexão entre um par de cidades é coberta por apenas uma empresa. Prove que, para $n\ge 11$, deve existir uma viagem de ida e volta por cerca de quatro cidades, utilizando os serviços de uma mesma empresa, enquanto que para $n<11$ isso não é mais necessariamente verdade. Dan Schwarz