O tabuleiro pode ser IMAGINADO como uma matriz quadrada de ordem 10. Adotemos esta imagem
com a seguinte modificacao : as linhas e colunas estarao numeradas de 0 a 9. Fixado isso e notando
que um movimento nao interfere no outro, e facil perceber que :
1) Se Ci e a Coluna Inicial do objeto ( Ci = 0,1,...,9 ) entao apos N movimentos a Coluna Final Cf
sera tal que : Ci + 7*N = 10*q + Cf, para algum inteiro " q ".
2) Se Li e a Linha Inicial do objeto ( Li = 0,1,...,9 ) entao apos N movimentos a Linha Final Lf
sera tal que : Li + 3*N = 10*q' + Lf, para algum inteiro " q' ".
O enunciado informa que N=2004 e que a "casa" final deve ser um verfice, isto e :
Ci + 7*2004 = 10*q + Cf => Ci + 14028 = 10*q + Cf onde Cf=0 ou Cf=9. Claramente que
se Ci=2 entao Cf=0 ou se Ci=1 entao Cf = 9. Assim, o objeto devera estar nas colunas 1 ou 2.
Mas, em qual linha ?
Li + 3*2004=10*q' + Lf => Li + 6012 = 10*q' + Lf onde Lf=0 ou Lf=9. Claramente que
se Li=7 entao Lf=9 ou se Li=8 entao Lf=0. Assim, o objeto devera estar nas linhas 7 ou 8.
Portanto, as valores validos para (Li,Ci) sao (7,1), (7,2), (8,1) e (8,2). Exemplificando, se ele partir
de (7,1) terminara em (9,9).
Observe que as equacoes Ci + 7*N=10*q + Cf e Li + 3*N = 10*q' + Lf sao equivalentes a
7*N - 10*q = Cf - Ci e 3*N - 10*q' = Lf - Li. Como MDC(7,10)=MDC(3,10)=1 entao qualquer
posicao final e "ATINGIVEL" seja qual for a posicao inicial de onde partirmos, bastando tomarmos
um N ( numero de movimentos ) conveniente, pois, conforme nos sabemos, uma equacao
diofantina da forma a*x + b*y = c tem solucao (x,y) no anel dos inteiros se, e somente se,
MDC(a,b) divide c.
PROBLEMA : Se, no problema do Benedito, os movimentos fossem 5 para a direita e 2 para baixo,
partindo de uma posicao inicial (Li,Ci) seriam ATINGIVEIS, apos um numero conveniente de
movimentos, qualquer posicao final ?
Um Abraco a Todos Paulo Santa Rita 4,0955,250204
From: "benedito" <[EMAIL PROTECTED]> Reply-To: [EMAIL PROTECTED] To: <[EMAIL PROTECTED]> Subject: [obm-l] Outro Problema Legal Date: Tue, 24 Feb 2004 19:38:32 -0300
PROBLEMA 24
Considere um tabuleiro 10 × 10. Um "movimento" no tabuleiro se faz avançando 7 quadros para a direita e 3 quadros para baixo. No caso de se sair por uma linha se continua pelo começo (à esquerda) da mesma linha e no caso de acabar uma coluna se continua pelo começo da mesma coluna (acima).
Onde se deve começar para que depois de 2004 movimentos terminemos num vértice?
Benedito
_________________________________________________________________ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.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 =========================================================================
