Re: [obm-l] Problema Interessante

[Marcelo Cruz <marcelocruz@xxxxxxxxx>]

Podemos fazer o seguinte. Primeiro inserimos as peças,
anotando com um lápis ou giz em cada casa quantas inversões
aquela casa deve sofrer, no estilo prisioneiro contando os
dias na parede da cela. Depois de colocadas todas as peças,
fazem-se as inversões. Após ter colocado todas as peças,
antes de por em prática a segunda parte do plano, teremos
n2-1 peças brancas e 1 preta no tabuleiro. Existe uma
correspondência biunívoca entre o número de arestas e o
número de inversões previstas, pois cada aresta implicará
exatamente uma inversão, quando for colocada a segunda peça
ao redor dela, afetando a primeira. Teremos portanto número
total de inversões = número de arestas =  2.n.(n-1) = par.
Ora, cada inversão vai alterar a paridade do número de
peças de cada cor no tabuleiro. Como serão 2k inversões, a
paridade final do número de peças de cada cor, em
particular da cor preta, será igual à inicial, portanto
teremos um número ímpar de pretas.



--- benedito <benedito@digizap.com.br> escreveu:

> Problema
> Um tabuleiro  n x n  é preenchido com peças brancas e
> pretas, de acordo com as seguintes regras:
> 
> (i) Inicialmente (i. e. tabuleiro vazio) uma peça preta é
> colocada sobre uma casa qualquer; 
> (ii) nos movimentos posteriores, uma peça branca é
> colocada em uma casa vazia e todas as peças, se houver
> alguma, situadas em casas vizinhas (i. e. com aresta
> comum) são trocadas por peças de cor oposta.
> 
> Este processo se prolonga até o tabuleiro estar
> completamente preenchido.
> 
> Prove que, ao final do processo, restará pelo menos uma
> peça preta sobre o tabuleiro.
> 
> Benedito



		
_______________________________________________________ 
O Yahoo! está de cara nova. Venha conferir! 
http://br.yahoo.com
=========================================================================
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
=========================================================================