[obm-l] [obm-l] OBM, fase 2, nível 3, última questão

["Pedro Cardoso" <pedrolazera@xxxxxxxxxxx>]

Olá.

Eu tenho uma dúvida em relação à última questão do nível 3 da segunda fase 
da obm:

O enunciado:

"Em um certo país há 21 cidades e o governo pretende construir n estradas 
(todas de mão dupla),
sendo que cada estrada liga exatamente duas das cidades do país. Qual o 
menor valor de n para que,
independente de como as estradas sejam construídas, seja possível viajar 
entre quaisquer duas
cidades (passando, possivelmente, por cidades intermediárias)?"

Ora, por que ligar uma cidade a todas as outras vinte, construindo assim 20 
estradas, não satisfaz todas as condições do problema? Seria possível viajar 
entre quaisquer duas cidades, desde que fosse possível passar pela cidade à 
qual todas as outras estão ligadas (o que o enunciado permite fazer).

Pedro Lazéra Cardoso

_________________________________________________________________
Descubra como mandar Torpedos do Messenger para o celular! 
http://mobile.msn.com/

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================