[obm-l] Re: [obm-l] Problema 6 - OBM 3a. fase - Nível 2

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

Para N=2 e N=3 é simples ver que sempre é possível visitar todas as cidades
mudando o transporte no máximo 1 vez.
Agora suponha que isso seja verdade para todo 1 <= k <= N-1.
Então esqueça uma cidade de Tumbólia e resolva o problema para as N-1
cidades restantes, sua solução deve  ser um ciclo com no máximo 1 troca de
transporte, se não houver troca de transporte, é muito simples ver que basta
inserir a N'ésima cidade em qualquer posição do ciclo que o ciclo novo terá
no máximo 1 troca.
Suponha que há exatamente 1 troca de transporte e esta ocorra na cidade
C[i], a cidade C[N] liga-se com C[i] ou de Ferrovia ou de Rodovia (F ou R),
se a cidade do ciclo que liga-se a C[i] com o mesmo meio de transporte com o
qual C[N] liga-se com C[i] é C[j], insira C[N] entre C[j] e C[i] e você tem
um ciclo por todas as cidades só mudando o meio de transporte 1 vez!

Basta ver que saímos de um ponto de origem, vamos até C[j] usando o mesmo
meio de transporte, de C[j] para C[N] pode ou não ocorrer mudança de
transporte, tanto faz, se não ocorrer, a mudança ocorre de C[N] para C[i],
se ocorrer, temos certeza que o meio de transporte de C[N] até C[i] é o
mesmo de C[i] até o ponto de origem.

Fica bem mais fácil com desenhos!

[ ]'s


----- Original Message ----- 
From: "Cesar Ryudi Kawakami" <cesarkawakami@uol.com.br>
To: "obm-l" <obm-l@mat.puc-rio.br>
Sent: Tuesday, October 21, 2003 1:45 PM
Subject: [obm-l] Problema 6 - OBM 3a. fase - Nível 2


Sei que a solução envolve conhecimento do princípio indutivo e da
interpretação de gráficos, mas...

Como resolver?

"PROBLEMA 6:
Há N cidades na 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 meios.
Um turista deseja viajar por toda 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."

Eu sinceramente não fazia a mínima noção de como resolver esse problema...
No segundo dia de prova, resolvi as questões 4 e 5 em pouco tempo, mas
empaquei nesta... =(

Um abraço,

Cesar Ryudi Kawakami

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

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