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

[Cesar Ryudi Kawakami <cesarkawakami@xxxxxxxxxx>]

Não entendi direito com que tipo de hipótese foi trabalhada...

Mais especificamente, não entendi como provar que tal suposição de que é 
possível mudar de meio de transporte apenas uma vez para todo 1 <= k <= N - 
1...

Haha, sou burro mesmo... =P

Um abraço,

Cesar Ryudi Kawakami


At 19:35 21/10/2003, you wrote:
>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
>=========================================================================

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