Re:[obm-l] Problema Interessante

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Cada nova peça colocada causa um número de mudanças de cor igual ao número de peças adjacentes a ela.

 

Como, ao final do jogo, o tabuleiro está totalmente preenchido, o número total de mudanças de cor ocorridas é igual ao número total de pares de peças adjacentes, o qual, por sua vez, é igual ao número total de arestas (entre duas casas adjacentes) do tabuleiro, ou seja, 2n(n-1), um número par  (pois temos n-1 linhas verticais e n-1 linhas horizontais, cada uma com n arestas).

 

Como o jogo começa com 1 peça preta e termina após um número par de mudanças de cor, o número de peças pretas ao final será ímpar e, portanto, não nulo.

 

[]s,

Claudio.

 

De:	owner-obm-l@mat.puc-rio.br

Para:

obm-l@mat.puc-rio.br

Cópia:

Data:

Sat, 2 Dec 2006 10:39:31 -0300

Assunto:

[obm-l] Problema Interessante

> 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