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