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:[EMAIL PROTECTED]
Sent: Thursday, February 27, 2003 1:41 PM
To: [EMAIL PROTECTED]
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 é [EMAIL PROTECTED]
=
=
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 é [EMAIL PROTECTED]
=
