Q17 Matemática  (Tournament Of Towns 2009)

Um país tem duas capitais e várias cidades. Alguns deles estão ligados por estradas. Algumas das estradas são estradas com portagem onde é cobrada uma taxa pela condução ao longo delas. Sabe-se que qualquer rota da capital sul para a capital norte contém pelo menos dez rodovias com pedágio. Prove que todos os pedágios podem ser distribuídos entre dez empresas para que qualquer pessoa que dirija da capital sul para a capital norte pague cada uma dessas empresas. (5 pontos)