Duas companhias aéreas, CONTI e TRACE, conectam 10 capitais da América do Sul. O diagrama apresenta alguns voos realizados pelas companhias, sendo CONTI representada por uma linha contínua vermelha e TRACE por uma linha tracejada azul.
Os voos estão planejados do seguinte modo:
dadas duas capitais quaisquer, apenas uma das companhias realiza voos diretos entre elas, em ambos os sentidos;
entre Brasília e La Paz não é possível fazer viagens usando apenas a CONTI, mesmo fazendo conexões em outras capitais.
a) Qual das companhias faz voos diretos entre Santiago e Brasília? Justifique sua resposta.
b) Explique por que é possível viajar entre Buenos Aires e Brasília usando apenas a empresa TRACE.
c) Dadas duas capitais quaisquer, explique por que sempre é possível viajar entre elas usando apenas a companhia TRACE, fazendo no máximo uma conexão em La Paz ou Brasília.
Reportar erro na questãoResolução comentada
Resolução comentada
a) Santiago está ligada a Bogotá pela CONTI, e Bogotá está ligada a La Paz também pela CONTI. Então já dá para ir de La Paz a Santiago usando só a CONTI (La Paz → Bogotá → Santiago).
Se o voo direto Santiago–Brasília fosse da CONTI, teríamos o caminho La Paz → Bogotá → Santiago → Brasília só com a CONTI. Isso contradiz a condição de que não se vai de Brasília a La Paz só com a CONTI.
Como cada par de capitais é atendido por exatamente uma companhia, o voo Santiago–Brasília é da TRACE.
Resposta: a TRACE.
b) Olhe os voos Buenos Aires–Brasília e Buenos Aires–La Paz. Há dois casos:
Se Buenos Aires–Brasília é da TRACE, o voo direto já resolve.
Se Buenos Aires–Brasília é da CONTI, então Buenos Aires–La Paz não pode ser da CONTI. Se fosse, La Paz → Buenos Aires → Brasília seria um caminho só da CONTI, o que é proibido. Logo Buenos Aires–La Paz é da TRACE. Como La Paz–Brasília também é da TRACE (está no diagrama), a viagem Buenos Aires → La Paz → Brasília usa só a TRACE.
Nos dois casos é possível viajar só com a TRACE.
Resposta: sempre existe um trajeto só com a TRACE, direto ou com conexão em La Paz.
c) Chame La Paz de L e Brasília de B. O voo L–B é da TRACE.
Passo 1. Toda outra capital X tem voo da TRACE com L ou com B. Se X–L e X–B fossem ambos da CONTI, o caminho L \to X \to B seria só da CONTI, o que é proibido.
Passo 2. Sejam X e Y duas capitais quaisquer.
Se uma delas é L ou B, por exemplo X=L: se Y=B, o voo é direto. Se Y é outra capital, ela tem voo da TRACE com L (direto) ou com B (e então L \to B \to Y, com conexão em B).
Se nenhuma é L nem B e as duas têm voo da TRACE com a mesma cidade (L ou B), basta uma conexão nela.
Se não há cidade comum, então X tem TRACE só com L (e CONTI com B) e Y tem TRACE só com B (e CONTI com L), ou o contrário. Então X–Y não pode ser da CONTI. Se fosse, B \to X \to Y \to L seria um caminho só da CONTI, o que é proibido. Logo X–Y é da TRACE e o voo é direto.
Em todos os casos há viagem só com a TRACE, com no máximo uma conexão em La Paz ou Brasília.
