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

["Otávio Menezes" <ommenezes@xxxxxxxxx>]

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 <victor__araujo@xxxxxxxxxxx> 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. ========================================================================= 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 =========================================================================