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