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
=========================================================================
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI
CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE
Fields Medal(John Charles Fields)