[obm-l] RE: [obm-l] movendo peças em linha

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

Claudio

Vamos ver se entendi direito. Vamos supor N peças de cada cor. Peças da
mesma cor não se ultrapassam, correto? logo, supondo peças B1, B2, B2, BN
irão sempre ter a mesma ordem. 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.

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