[obm-l] movendo pe�as em linha

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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