Nao entendi! Foi voce mesmo que mandou a mensagem original com esse problema e disse que foi da olimpiada polonesa de 1983.
on 26.04.04 12:59, Johann Peter Gustav Lejeune Dirichlet at peterdirichlet2002@yahoo.com.br wrote:
Com o profundo conhecedor de questoes eu digo que isso e da IMO de Istanbul
"Domingos Jr." <dopikas@uol.com.br> wrote:
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 fin! al:
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.
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI
CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE
Fields Medal(John Charles Fields)