on 10.11.04 16:03, João Gilberto Ponciano Pereira at [EMAIL PROTECTED] 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:[EMAIL PROTECTED] > 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 =========================================================================
