Re: [obm-l] Olimpiada Polonesa 1983

["Domingos Jr." <dopikas@xxxxxxxxxx>]

B2.  There is a piece in each square of an m x n rectangle on an infinite
chessboard. An allowed move is to remove two pieces which are adjacent
horizontally or vertically and to place a piece in an empty square adjacent
to the two removed and in line with them (as shown below)
X X . to . . X, or  . to X                    X    .                    X
.
Show that if mn is a multiple of 3, then it is not possible to end up with
only one piece after a sequence of moves.

--- x ---

Ok, vou re-escrever a regra pois como texto puro não saiu.
Você tem um tabuleiro m x n com peças e você pode fazer uma peça comer outra
adjacente na horizontal ou vertical desde que haja um espaço para a peça que
está pulando...
por exemplo X X . -> . . X

Lendo o livro do Engel (Problem Solving Strategies) eu reconheci
imediatamente que este é um problema que pede a existência de um invariante.

Imagine que estamos associando a cada quadrado do tabuleiro uma cor, vamos
utilizar 3 cores, digamos {0, 1, 2} da seguinte forma: primeiramente fixamos
um quadrado (0, 0) no tabuleiro e para todo quadrado (i, j) associamos a cor
i - j mod 3.

Utilizando tal coloração é possível ver que num retângulo m x n (3|m) o
número quadrados de cada cor é o mesmo:
Suponha que o retângulo seja formado por (0,0) a (m-1, n-1)
Considere S_k = {(i, j) : 0 <= i < m, 0 <= j < n, i - j ~ k (mod 3)}.
Tome o mapa f(i, j) = (i + 1 mod m, j).
Como m é múltiplo de 3 o mapa é uma bijeção f: S_k -> S_{k+1 mod 3}, logo
|S_1| = |S_2| = |S_3|.
É simples ver que f é injetora, para mostrar que f(S_k) = S_{k+1 mod 3},
basta ver que se i < m - 1, então f(i, j) = (i + 1, j) e i + 1 - j = (i-j) +
1 (mod 3)
se i = m - 1, f(i, j) = f(m-1, j) = (0, j) e -j = [(m - 1) - j] + 1 (mod 3)
pois m = 0 (mod 3).

Agora a sacada final:
no início temos |S_1| = |S_2| = |S_3| (mod 2)
a cada passo, quando uma peça é comida, dois quadrados de cores distintas
perdem peças e um quadrado com a terceira cor recebe uma peça, ou seja, ao
final de um passo, o invariante |S_1| = |S_2| = |S_3| (mod 2) continua
válido.

Note que a situação de apenas 1 peça no tabuleiro implica que existe uma cor
que é 1 mod 2 e as demais são 0, o que é absurdo.

O que provamos acima mostra ainda que se é possível chegar a uma redução de
duas peças elas devem estar em quadrados de mesma cor!

A propósito, no livro que eu mencionei tem um problema similar, ele mostra
que se tivermos um quadrado n x n com n não múltiplo de 3 é possível restar
apenas 1 peça com as mesmas regras de jogo... tentem mostrar isso.

[ ]'s

Domingos.

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