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

["Domingos Jr." <dopikas@xxxxxxxxxx>]

>     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.
- 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.

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.


>   Obs.: Tenho certeza que o problema da desigualdade,
> discutido por Dirichlet, é trivialmente equivalente a
> um problema da lista de preparação da IMO!!! Assim
> como um outro problema de geometria já discutido. Acho
> isso desleal com os candidatos a participarem destas
> olimpíadas!!! Por favor professor Johan e demais
> companheiros da lista, mantenha a discrição para não
> prejudicar nossos colegas.

hahaha, sem comentários!

=========================================================================
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>
=========================================================================