Minha solução não tem quase nenhum rigor matemático, é muito intuitiva, mas dá o resultado correto.
O enunciado diz "independentemente de como as estradas forem construídas". Na pior das hipóteses, teríamos 20 cidades 3 a 3 não colineares. Construindo todas as estradas possíveis entre essas 20 cidades, faríamos 190 estradas. A 21ª cidade estaria "isolada". A próxima estrada invarialvelmente conectará essa cidade à rede, cumprindo as condições do enunciado. Logo, o menor valor de n é 191. Acham que consigo faturar alguns pontinhos com essa solução? Em 19/09/07, Victor Araújo <[EMAIL PROTECTED]> escreveu: > > O enunciado diz ''independentemente de como sejam construídas'', e desse > jeito você está afirmando que as estradas tem que ser contruídas de uma > certa maneira. Com 20 estradas, eu poderia fazer alguns triangulos, com ABC > / DEF / GHI / JKL / MNO / PQR e ligar S a T e U. Todas as cidades estariam > ligadas? Não. > > ---- > >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 > >========================================================================= > > > ------------------------------ > MSN Busca: fácil, rápido, direto ao ponto. Encontre o que você quiser. > Clique aqui. > <http://g.msn.com/8HMABR/2740??PS=47575>========================================================================= > 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=========================================================================
