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