[obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] Dúvida de vestibular

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

Este é um problema interessante! Mas acho que faltou dizer que as cidades em
questão fazem parte do mesmo país, ou seja, a cidade A pertence a um país C
se existe pelo menos uma estrada que vá de A para alguma cidade pertencente
a C.

Acho que a solução é mais ou menos assim:

A "pegadinha" é provar que se existe um caminho que vai de Cn para Cm, então
existe o caminho de volta de Cm para Cn. Prova: seja Pi o "peso" do número
de estradas da cidade Ci, que é o número de estradas que entram mais o
número de estradas que saem. Supondo que o viajante pega o carro de Cm e vai
para Cn passando por algumas cidades. Como ele saiu de Cm, o peso Pm será 1.
Para as outras cidades, o peso é 2i, pois ele chegou e saiu. Para Cn, o peso
é 2i+1, pois ele chegou.

Veja que as cidades devem ter Pi par, pois o número de estradas que chegam é
o mesmo das que saem. Logo, o ciclo de volta sempre terminará em Cm.

Suponha agora um país com 2 cidades A e B. Se A chega a B, temos que B chega
a A, e o número de mapas é igual. Acrescentando uma cidade C no país, ela
será ligada em A, sem perda de generalidade. Ora, se A chega em C e B chega
em A, então B chega em C e, pela volta, C chega em B. Logo, por indução, vc
consegue chegar em qualquer cidade de um determinado país com N cidades, o
número de mapas possíveis é N-1.

-----Original Message-----
From: Nicolau C. Saldanha [mailto:nicolau@sucuri.mat.puc-rio.br]
Sent: Thursday, February 27, 2003 1:41 PM
To: obm-l@mat.puc-rio.br
Subject: [obm-l] Re: [obm-l] Re: [obm-l] Dúvida de vestibular


Eu [ainda] não sei resolver o problema do Okakome mas...

On Wed, Feb 26, 2003 at 04:39:33PM -0300, Domingos Jr. wrote:
> >     Oi Pessoal,
> >   Estava estudando análise combinatória por uma
> > apostila de um curso pré-vestibular, e encontrei o
> > seguinte problema, que achei interessante, mas minha
> > solução foi muito longa, e não sei se está certa,
> > porque tinha muitos casos. Se estivesse num
> > vestibular, o que faria?
> >   Num país, as estradas ligam duas cidades e são de
> > mão única (pode haver mais de uma estrada entre duas
> > cidades). O número de estradas que partem de cada
> > cidade é igual ao número de estradas que chegam nessa
> > cidade. Um mapa da cidade C é um conjunto de rotas
> > que: 1) levam C a cada uma das outras cidades do país,
> > sem passar por uma cidade mais de uma vez. 2) Se uma
> > rota parte de C a D passando por E, então a rota que
> > vai de C a E coincide com o começo da rota de C a D.
> > Prove que o número de mapas da cidade C é igual ao
> > número de mapas de qualquer outra cidade.
> 
> Acho que esse enunciado não está completo:
> - se existe uma cidade com nenhuma estrada partindo ou chegando possui um
> número de rotas 0 e não vai ser igual as demais, até aí é um caso idiota
que
> pode ser excluído do problema.

Neste caso não existe nenhum mapa pois é impossível ligar C a X,
a cidade sem estradas. O problema fica correto pois o número
de mapas é sempre 0.

> - se existem conjuntos de cidades "disjuntos" ou seja cidades de um
conjunto
> A não possuem rota nenhuma para as cidades do conjunto B e vice-versa:
> 
> C1 <-------> C2 ( 1 estrada de C1 -> C2 e outra de C2 -> C1  )
> C3 <======> C4 ( 2 estradas de C3 -> C4 e duas de C4 -> C3 )
> 
> neste caso temos que o número de rotas de N(C1) = N(C2) = 1, mas N(C3) =
> N(C4) = 2.

Também neste caso o número de mapas é sempre 0.

> além disso, há um trecho que eu considero confuso:
> 
> "2) Se uma rota parte de C a D passando por E, então a rota que vai de C a
E
> coincide com o começo da rota de C a D"
> nessa situação parece que a rota de C a E deve ser única, mas podem haver
> outras rotas de C até E sem que uma cidade seja visitada mais de uma
vez...
> mesmo que sempre fossem escolhidos os caminhos que passem por menos
cidades
> isso poderia ocorrer já que é permitido haver mais de uma estrada ligando
> duas cidades.

Acho que ajuda considerar o caso em que todas as estradas são de mão dupla:
neste caso um mapa nada mais é do que uma árvore maximal e o problema
fica trivial.

[]s, N.
=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================
=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================