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