Re: [obm-l] RE: [obm-l] movendo peças emlinha

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 10.11.04 16:03, João Gilberto Ponciano Pereira at jopereira@vesper.com.br
wrote:

> Claudio
> 
> Vamos ver se entendi direito. Vamos supor N peças de cada cor. Peças da
> mesma cor não se ultrapassam, correto?
Sim.

> logo, supondo peças B1, B2, B2, BN
> irão sempre ter a mesma ordem.
Concordo. Alias, isso faz com que a hipotese de pecas indistinguiveis seja
irrelevante.

> Logo, partindo da configuração inicial até a
> final, serão necessários N+1 movimentos com cada peça para que ela saia da
> posição inicial e chegue na final. O total de movimentos seria (N+1)*2N.
> 
> Entretanto, podemos chamar de movimento do pulo quando uma pedra se
> movimenta por cima da outra. Este movimento vale como 2 movimentos normais.
> Como uma peça tem que ultrapassar N outras peças, teremos um total de N^2
> pulos.
> 
> Logo, Não existe um "caminho certo". Pelo que entendi, qualquer sequencia
> válida é ótima, com um número de movimentos igual a N^2 + 2N. rs... para 1,
> minha lógica vale... agora para o resto, tem que testar.
O seu raciocinio estah perfeito.
Soh falta provar que o objetivo eh atingido para cada N.

[]s,
Claudio.

> SDS
> JG
> 
> 
> -----Original Message-----
> From: Claudio Buffara [mailto:claudio.buffara@terra.com.br]
> Sent: Tuesday, November 09, 2004 10:31 PM
> To: Lista OBM
> Subject: [obm-l] movendo peças em linha
> 
> 
> Um tabuleiro 1 x (2n+1) contem n peças brancas ocupando as casas 1, 2, ...,
> n  e  n peças pretas ocupando as casas n+2, n+3, ..., 2n+1. A casa n+1 estah
> inicialmente vazia.
> 
> O objetivo eh colocar as n peças pretas nas casas 1, 2, ..., n e as n peças
> brancas nas casas n+2, n+3, ..., 2n+1.
> 
> Os movimentos permitidos sao os seguintes:
> 1) Para as peças brancas:
> 1a) Deslocamento da casa k para a casa k+1, se esta estiver vazia;
> 1b) Deslocamento da casa k para a casa k+2, se esta estiver vazia e a casa
> k+1 contiver uma peça preta.
> 
> 2) Para as peças pretas:
> 2a) Deslocamento da casa k para a casa k-1, se esta estiver vazia;
> 2b) Deslocamento da casa k para a casa k-2, se esta estiver vazia e a casa
> k-1 contiver uma peça branca.
> 
> Supondo que duas peças duma mesma cor sao indistinguiveis, qual o menor
> numero de movimentos necessarios para que o objetivo pode ser atingido?
> 
> Por exemplo, para n = 1, a resposta eh 3:
> 1  2  3
> [B][ ][P]
> [B][P][ ]
> [ ][P][B]
> [P][ ][B]
> 
> []s,
> Claudio.
> 
> 
> =========================================================================
> 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
=========================================================================