Re: [obm-l] OBM 2003- Alguem fez esse?

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

> Olá pessoal, esqueceram de fazer este problema...
> 
> 
> Há N cidades em Tumbólia. Cada duas cidades desse país são
> ligadas por uma rodovia ou uma ferrovia, não existindo nenhum
> par de cidades ligadas por ambos os meios.
> 
> Um turista deseja viajar por toda a Tumbólia, visitando cada cidade
> exatamente uma vez, e retornar a cidade onde ele começou sua jornada.
> 
> Prove que é possível escolher a ordem na qual as cidades serão visitadas
> de modo que o turista mude o meio de transporte no máximo uma vez.

Esse é um problema de grafos.
Veja que para N = 2 o problema é trivial.
Vamos mostrar que para N + 1 também conseguimos resolver o problema.
Agora Tumbólia tem N + 1 cidades e já montamos um circuito (um 
itinerário onde visitamos cada cidade uma única vez) de tamanho N onde 
trocamos de transporte no máximo 1 vez. Suponha que X seja a cidade que 
ficou de fora deste circuito.

Se o circuito formado só possui um meio de transporte, podemos adicionar 
X ao circuito e trocar de meio de transporte no máximo 1 vez (faça um 
desenho...).

Se o circuito formado já troca de transporte ao passar pela cidade Y 
teremos cuidados extras. Podemos assumir (sem perda de generalidade) que 
o circuito de N cidades começa em Y e chega até Z através de rodovia e 
de Z até Y utiliza ferrovia.

Se X se liga a Y através de ferrovia, insira X logo após Y no circuito e 
veja que isso dá uma solução.
Analogamente, se X se liga a Z através de ferrovia, então coloque X 
imediatamente antes de Z no circuito.

Sobrou apenas o caso em que X se liga a Y e Z através de rodovias.
Neste caso forme um circuito começando Z, passando por X, depois Y, 
depois siga o circuito original a partir de Y até encontrar o 
predecessor de Z, Z' (no circuito original), vá de Z' até o antecessor 
de Y, Y' (também no circuito original) e depois siga até Z pela direção 
contrária ao circuito original.

Por texto fica confuso, mas se você desenhar, vai ver que essa 
construção funciona.

[ ]'s
=========================================================================
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
=========================================================================